實現二進制搜索猜謎遊戲

我試圖編寫一個程序，其中計算機試圖猜測用戶選擇的數字（1 - 100）。我寫了大部分的程序，並且還製作了一個隨機數生成器。我現在唯一需要的是一種基於用戶的HIGH或LOW輸入將二進制搜索算法實現到我的程序中的方法。我讀過一些關於二分查找算法的知識，但我不確定如何在程序中使用它。有人能指出我正確的方向嗎？實現二進制搜索猜謎遊戲

34行和42行有一個空格，應該有一個函數。這就是我想要輸入某種方式來將二進制搜索算法實現到我的程序中的地方。

下面是我的代碼，截至目前：

#include <iostream> 
#include <ctime>//A user stated that using this piece of code would make a true randomization process. 
#include <cstdlib> 
#include <windows.h> 
using namespace std; 

int main() 
{ 
    int highLow; 
    int yesNo; 
    int ranNum; 
    srand(time(0)); 


    ranNum = rand() % 100 + 1; 

    cout << "Please think of a number between 1-100. I'm going to try to guess it.\n"; 
    _sleep(3000); 

    cout << "I'm going to make a guess. Is it "<< ranNum <<" (1 for yes and 2 for no)?\n"; 
    cin >> yesNo; 


    while (yesNo == 2) 
     { 
      cout << "Please tell me if my guess was higher or lower than your number\n"; 
      cout << "by inputting 3 for HIGHER and 4 for LOWER.\n"; 
      cin >> highLow; 

      if (highLow == 3) 
       { 
        cout << "Okay, so my guess was higher than your number. Let me try again.\n"; 
        _sleep (1500); 
        cout << "Was your number " << <<"? If yes, input 1. If not, input 2.\n";// I would like to find a way to implement the 
       //binary search algorithm in this line of code. 
        cin >> yesNo; 
       } 
      if (highLow == 4) 
       { 
        cout << "Okay, so my guess was lower than your number. Let me try again.\n"; 
        _sleep (1500); 
        cout << "Was your number " << <<"? If yes, input 1. If not, input 2.\n";// I would like to find a way to implement the 
       //binary search algorithm in this line of code. 
        cin >> yesNo; 
       } 
     } 
     if (yesNo == 1) 
     { 
      cout << "My guess was correct!\n"; 
     } 
}

來源

2015-12-24 Bill Fisher

您是否有二進制搜索功能？如果不是，你應該做的第一件事就是創建一個並在硬編碼輸入上測試它。一旦它正確測試出來，然後將其應用於更大的程序。 – PaulMcKenzie

歡迎來到StackOverflow。雖然你的問題無疑是有趣的，但SO不是一種代碼編寫服務。例如，您可以查詢現有的有缺陷的二分法搜索算法，以及各種各樣的API，但不能提出有爭論或長時間討論的問題。 SO也不是博客。 – SwiftArchitect

保持兩個整數bottom和top。 loop invariant是用戶的號碼在[bottom;最佳]。

現在我們要儘量減少猜測次數。爲此，我們希望儘可能地從[底部;頂部]一組數字（如果我們猜錯了）。

要儘可能多地扔掉我們總能猜到的floor((bottom + top)/2)。

爲了實現我們可以根據我們的新信息調整bottom或top。如果它太高，我們將top設置爲guess - 1。如果它太低，我們將bottom設置爲guess + 1。

在最壞的情況下使用此策略，您只能猜測floor(log2(100)) = 6次。有1000個號碼可供選擇 - 9個猜測就足夠了。我們假設：50（高），25（高），12（高），6（高），3（高），1（低）。我們不會猜/要求用戶2，因爲我們已經100％確定它是2.

來源

2015-12-24 19:50:46

實現二進制搜索猜謎遊戲

回答

相關問題