通常、数字当てゲームのアルゴリズムは、秘密の数字が与えられた場合、推測が秘密の数字よりも大きいか小さいかがわかっていれば、二分探索アルゴリズムを修正したものにすぎません。秘密の番号が 13 だったとします。アルゴリズムは、1 (13 より小さい)、2 (13 より小さい)、4 (13 より小さい)、8 (13 より小さい)、16 (13 より大きい、バックトラック)、10 ( 13 より小さい)、13(シークレットに等しい、停止します。)
しかし、推測が秘密の数字よりも小さいか大きいかがわからず、唯一のステータスが等しいか等しくないかがわからない場合はどうなるでしょうか。どのアルゴリズムが最も効率的でしょうか? 確かにブルートフォースではありません...
編集: どちらの状況でも、数値の上限と下限があります。
このような問題に対して期待されるパフォーマンスの向上の種類はよくわかりません。ほとんどの人が示唆しているように、O(n) から最悪のケースを改善する重要な方法はありません。また、バイナリ検索アプローチを引き続き使用することもできます。このアプローチでは、最初はすべての不等な推測が「<」より小さい操作と見なされ、このリストが使い尽くされたら、すべての不等な推測が操作 > より大きいと見なすことができます。「数当てゲーム」をプレイするときの実際のシナリオでは、これはブルート フォース シーケンシャルよりも優れていると思います。
一般的に、確実に最小の推測で数を推測するアルゴリズムを見つけることができれば、世界中でプレイされている多くのゲームがすぐに冗長になると確信しています:)
さて、あなたが持っている情報は、答えが正しくないということです。入手可能な唯一の情報であるため、力ずくが唯一のアプローチになると思います。ゼロから始めて上昇することもできます。
等しい/等しくないという情報しか得られない場合、総当たりよりも優れた平均ケースまたは最悪ケースのパフォーマンスを提供するアルゴリズムはありません (つまり、下限から開始して上限まで作業します)。
平均的なケースのパフォーマンスを少しでも向上させるには、何らかの追加情報が必要になります。少なくとも、「秘密の数字の 10% だけが 20 を下回らない」などのような統計情報を使用して、より良い平均ケース パフォーマンスを引き出すことができます (この例では、おそらく 21 で検索を開始することによって)。
それでも、最悪の場合のパフォーマンスは力ずくで勝るものではありません。
必要になるまで実際に番号について決心しない敵対者を想像すると、順番にすべての番号を尋ねなければならない可能性があることがわかります。あなたが考えられるすべての数字を推測するまで、彼らは単純に「間違った答え」と言うことができます。あなたが最後に推測した数字が何であれ、最初の選択に基づいて、彼らの答えは本物である可能性があります。