C#でつくる素数大富豪、完成品はこんな感じです。
この記事内でやろうとしていることはコンピュータが出すカードを決めるアルゴリズムの研究です。人間であるプレーヤーが出したカードであれば実際に計算をして素数なのか、適切な合成数出しなのかを比較的簡単に調べることができますが、コンピュータのターンである場合は適切なカードをアルゴリズムで探し出さなければなりません。
前回のコンピュータが出せるカードを調べる C#で素数大富豪をつくる(2)ではおおざっぱな方法で出すことができる合成数を調べました。しかし前回示したコードでは本当に出すことができるカードなのか正確にはわかりません。
ある合成数を手持ちの素数で割り続けて1になるかどうかでは「合成数出しが可能であるかもしれないカード」ということはできても、本当に出せるカードであると断定はできません。
たとえばすべてのカードが、3, 5, 5, 5, 6, 6, 6, 6, 7, 10, 10, 11, 11のとき、3, 10, 7, 5を使って合成数31075をつくることができ、しかも素因数分解可能 5 5 11 113に素因数分解することができます。ところが31075をつくることによって残るカードは5, 5, 6, 6, 6, 6, 10, 11, 11であり、素因数113をつくることができません。そこで手持ちのカードで素因数分解できても合成数を作ったり他の素因数をつくるためにカードが足りなくなっていないか検証が必要なのです。
2段階戦術でコンピュータが出せる合成数を求める
そこで手持ちのカードの数すべてと出さなければならない枚数をわたして本当に出せるカードを取得するメソッドをつくります。戻り値はResultCardsオブジェクトのリストです。
ResultCardsクラス
以下はResultCardsクラスです。
|
1 2 3 4 5 6 7 8 |
public class ResultCards { public bool IsPrimeNumber = true; // 素数として出せるか合成数として出せるか public long Number = 0; // 出せる場合の整数値 public List<int> Cards1 = new List<int>(); // 場に出すカードの番号のリスト public List<int> Cards2 = new List<int>(); // 素因数場に出すカードの番号のリスト public List<long> PrimeNumbers = new List<long>(); // 合成数出しの場合、素因数分解の結果 } |
それから素数とカードの番号の関係がわかるように以下のクラスも作成します。
|
1 2 3 4 5 6 7 8 9 10 11 |
public class PrimeNumberCards { public PrimeNumberCards(long primeNumber, List<int> cards) { PrimeNumber = primeNumber; Cards = cards; } public long PrimeNumber = 0; // 素数の値 public List<int> Cards = new List<int>(); // 素数をつくるカードの番号のリスト } |
GetCardsCanPutメソッド
それでは手持ちのカードから出すことができるカードを返すGetCardsCanPutメソッドを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
List<ResultCards> GetCardsCanPut(int[] allCards, int cardCount) { List<ResultCards> ret = new List<ResultCards>(); List<ResultCards> notPrimeNumbers = new List<ResultCards>(); Permutation permutation = new Permutation(); // n枚でつくることができるカードの順列をつくる // ここから生成される数を素数と合成数にわける List<int[]> arrayList1 = permutation.GetPermutations(allCards, cardCount).ToList(); foreach (int[] array1 in arrayList1) { long num = GetNumber(array1); if (IsPrimeNumber(num)) ret.Add( new ResultCards() { IsPrimeNumber = true, Number = num, Cards1 = array1.ToList() } ); else notPrimeNumbers.Add(new ResultCards() { IsPrimeNumber = false, Number = num, Cards1 = array1.ToList() }); } // 合成数は「合成数出し」ができるか調べる // 素因数分解に使うための手持ちのカードで作れる素数を取得する List<PrimeNumberCards> primeNumbers = new List<PrimeNumberCards>(); for (int i = 1; i <= 4; i++) { List<int[]> arrayList = permutation.GetPermutations(allCards, i).ToList(); foreach (int[] array in arrayList) { long num = GetNumber(array); if (IsPrimeNumber(num)) primeNumbers.Add(new PrimeNumberCards(num, array.ToList())); } } // 素因数分解は可能か？ foreach (ResultCards notPrimeNumber in notPrimeNumbers) { long notPrimeNumber1 = notPrimeNumber.Number; // 1は素因数分解できない if (notPrimeNumber1 == 1) continue; foreach (PrimeNumberCards primeNumberCard in primeNumbers) { if (notPrimeNumber1 % primeNumberCard.PrimeNumber == 0) { notPrimeNumber1 /= primeNumberCard.PrimeNumber; notPrimeNumber.PrimeNumbers.Add(primeNumberCard.PrimeNumber); notPrimeNumber.Cards2.AddRange(primeNumberCard.Cards); if (notPrimeNumber1 == 1) break; } } if (notPrimeNumber1 != 1) continue; // 取得した素数すべてを使った割り算で1にすることができればとりあえず素因数分解は可能である。 // 素因数分解をするために必要なカードは手持ちのカードで足りているか？ // 手持ちのカードのなかから合成数と素因数分解に必要な数をつくるために必要なカードをRemoveメソッドで取り除く // 処理がすべて成功したら素因数分解をするために必要なカードはすべて存在すると判断する bool CanPrimeFactorization = true; List<int> allCardsCopy = new List<int>(allCards); // 手持ちのカードのコピーを作る foreach (int num in notPrimeNumber.Cards1) { if (!allCardsCopy.Remove(num)) { CanPrimeFactorization = false; break; } } if (!CanPrimeFactorization) continue; foreach (int num in notPrimeNumber.Cards2) { if (!allCardsCopy.Remove(num)) { CanPrimeFactorization = false; break; } } if (!CanPrimeFactorization) continue; ret.Add(notPrimeNumber); } return ret; } |
試運転
実際に処理を行なってみましょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void DoProcessing() { Random random = new Random(); random.Next(13); List<int> cards = new List<int>(); for (int i = 0; i < 13; i++) { cards.Add(random.Next(13) + 1); } List<ResultCards> ret = GetCardsCanPut(cards.ToArray(), 4); ResultCards first = ret.FirstOrDefault(x => !x.IsPrimeNumber); if (first != null) { Console.WriteLine("配布されたカード：" + String.Join(", ", cards.OrderBy(x => x).Select(x => x.ToString()))); Console.WriteLine("場に出すカード：" + String.Join(", ", first.Cards1.Select(x => x.ToString()))); Console.WriteLine("場に出された数：" + first.Number.ToString()); Console.WriteLine("素因数場に出すカード：" + String.Join(", ", first.Cards2.Select(x => x.ToString()))); Console.WriteLine("素因数の積：" + String.Join(", ", first.PrimeNumbers.Select(x => x.ToString()))); } } |
一番最初に取得された合成数を表示させています。以下は実行結果の一例です。
|
1 2 3 4 5 6 7 |
# 実行結果 配布されたカード：3, 3, 4, 5, 7, 7, 8, 8, 11, 11, 11, 11, 13 場に出すカード：8, 3, 4, 13 場に出された数：83413 素因数場に出すカード：11, 7, 5, 8, 3 素因数の積：11, 7583 |
たしかに合成数として場に出すカードと素因数場に出されるカードはすべて配布されたカードのなかにあり、11×7583の計算結果は83,413であり、11と7583はそれぞれ素数です。GetCardsCanPutメソッドは正しく動作しているといえます。
