秋に戻って、2年目、「オートマトンの理論」の実験室の仕事として、外出中の教師は私たちの課題を発明し、評価における私たちの希望に焦点を当てました。 これらは主にゲームでした。 誰かがホッケーをもらい、誰かがテニスをしましたが、あまり有名ではないロジックゲーム「Bulls and Cows」を手に入れました。
人とのゲームでは、コンピューターの少なくともある程度の合理的な動作を実現する必要がありました。 しかし、私はさらに進んで、1か月以内にほとんどの場合、コンピューターがクラスメートを簡単に倒しました。 そして、主題については自動的に得られました。 アルゴリズムの説明の後にプログラムを入手してください。
ゲームの本質
プレーヤーとコンピューターは、 0〜9の数字を使用して4桁の数字を作成します。 プレーヤーは、 「ブル」の数と「牛」の数という2つの数字を受け取る代わりに、可能な数字を送信することにより、相手の数字を解明しようとします。 これらはどのような数字ですか？
- 「雄牛」は正しい場所にある正しい数字です。 4つの「雄牛」が勝利の保証であり、すべての農家の夢です。
- 「牛」は間違った場所にある正しい数字です。
理解するために、例を挙げます。
番号1622が構成されています。 6112と仮定した場合、答えは次のとおりです。1頭の雄牛 （その場所の4桁目の「2」）、 2頭の牛 （6 頭と1 頭の外れ）。
敵の「牛」に関するデータを使用すると、敵よりも早く数字を推測する必要があります。
最初の自明なアルゴリズムは、完全なセットが受信されるまで「1111」、「2222」、「3333」セットを反復処理し、このセットの動きを生成することです。
たとえば、同じ番号1622が推測され、 「1111」と仮定して、 「ブル」が返され、 「2222」 -2つの「ブル」が返されます。 「3333」は空、 「4444」は空、 「5555」 -空、 「6666」 -1ブル 。
合計で4頭の雄牛がすでに蓄積されているため、これ以上は続行しません。 目的の組み合わせを見つけることは残っています。 Ta-daaamを取得するまで順列を生成します： "1226"、 "1262"、 "1226"、 "1262"、 "1622" それだけです
明らかに、アルゴリズムはあまり良くありませんが、明確であり、混乱しないようにしてください。 推測のための移動の最大数は、10（「7890」）+ 24の順列です。 34は最悪のシナリオです。 もちろん、可能な限りあらゆる方法で検索と並べ替えを最適化することができます。たとえば、 「1111」、「0000」、「2222」、「9999」の 2つの端から交互に繰り返します。同じことを聞いてください）。
しかし、これは行いません。 この戦略をコンピューターの複雑さの簡単なレベルにします。
私はペアでたくさん座って、自分で遊んで、自分のある種のクールなアルゴリズムを考え出そうとしました。 しかし、私は単一の戦略を立てることができなかった単一のアイデアのみが生まれました。 彼は文学を学び始めました。 ある種の「7ムーブで推測」という記事に出会いました。 多くの分岐があるので、彼らは私を引き付けませんでした。 しかし、私たちのキーロフ教授の本を読んだ後（しかし、私たちの大学からではない） S.M. Okulova "Programming in Algorithms"では、かなり単純でかなり効果的なアルゴリズムの説明を見つけました。 いわゆる「ふるい法」を使用します （例は、有名な「エラストフェンふるい」 -素数を見つける古典的な問題です）。 考えられるすべての数の有限セットを検討し、すべての動きは、対象ではないセットのすべての要素を除外します。
たとえば、予測数1234の場合、 5678を想定し、0頭の雄牛と0頭の牛 、つまり5、6、7、8を含むすべての数字を除外します。 10000からどれだけ取り出すかをすぐに把握できます。10000の要素のセットを怖がらないでください。 5〜6の動きの場合、残っている数字はわずかです。
データ構造から始めましょう。 パスカルコード：
Const Pmax=10000; Type Post=string[4]; Var A:array[1..Pmax] of Post; // B:array[1..Pmax] of boolean; // , 1 - , 0 -
初期化：
t:=1; for i:=0 to 9 do for j:=0 to 9 do for k:=0 to 9 do for l:=0 to 9 do begin a[t]:=inttostr(i)+inttostr(j)+inttostr(k)+inttostr(l); // inc(t); end; for i:=1 to pmax do b[i]:=true; //
変数の値（bk、kr-雄牛および雌牛）によるセットの要素の分析を実装する関数
function pr(a,b:post;bk,kr:integer):boolean; //b - , a- "" var i,x:integer; begin x:=0; for i:=1 to 4 do // if a[i]=b[i] then inc(x); if x<>bk then begin pr:=false; exit; end; x:=0; for i:=1 to 4 do // if (a[i]<>b[i]) and (pos(b[i],a)<>0) then inc(x); if x<kr then begin pr:=false; exit; end; pr:=true; end;
だから私たちはそれぞれの動きの後、ふるいを開始します
for i:=1 to Pmax do if b[i] and not pr(a[i],hod,bk,kr) then b[i]:=false;
結論として、このアルゴリズムはメモリ集約型であり、標準のアルゴリズムと比較して、「より長い」と考えられますが、どれほど簡単で最適化されていると考えられます。
まあ、それはすべて、それはまったく複雑ではありません。 私の最初の記事は厳密に判断することです。
約束どおり、自分自身で「ふるい」方法を感じるために、2年目からの私の小さなゲームへのリンク：
雄牛と牛