浪跡天涯

人機猜數游戲

問題分析
解決這類問題時，計算機的思考過程不可能象人一樣具完備的推理能力，關鍵在于要將推理和判斷的過程變成一種機械的過程，找出相應的規則，否則計算機難以完成推理工作。
基于對問題的分析和理解，將問題進行簡化，求解分為兩個步聚來完成：首先確定四位數字的組成，然后再確定四位數字的排列順序。可以列出如下規則：
1)產生四位數字的全部排列產生四位數字的全部排列。
2)生成隨機數,根據，根據人輸入的正確數字及正確位置的數目，進行刷選。
3)再剩下的結果中，生成隨機數，重復步驟2，直至找到。

GetNextGuess()函數算法不知該如何理解？
我覺得這個函數算法不好，沒有充分利用先前的猜數以及結果進行下一次的猜數。

程序代碼：
#include <iostream>
#include <time.h>
#include <string>
#include <list>
#include <limits>

using namespace std;
list<string> numList;

void   Initialize();
string RanddomNum();
string GetNextGuess();
int    CountN(const string &guess, const string &str);
int    CountP(const string &guess, const string &str);

int main()
{
 Initialize();   // 初始化
 string guess = RanddomNum(); // 第1回合隨機猜數
 int n, p;    // 分別表示有幾個數字猜對，有幾個數字位置也對
 
 while (1)
 {
  cout << guess << endl;
  cin >> n >> p;
  if (n == 4 && p == 4) // 猜中
   break;
  list<string>::iterator it;
  for (it = numList.begin();it != numList.end();)
  {
   if (CountN(guess, *it) != n) // 如果沒有n個數字對
   {
    it = numList.erase(it);  // 不可能是被猜數，篩掉
    continue;
   }
   if (CountP(guess, *it) != p) // 如果沒有p個數字位置對
   {
    it = numList.erase(it);  // 不可能是被猜數，篩掉
    continue;
   }
   ++it;
  }
  if (numList.empty()) // 沒有候選數了，人欺騙計算機
  {
   cout << 0 << endl;
   break;
  }
  guess = GetNextGuess();
 }
 return 0;
}

void Initialize()
{
 char buf[5] = {0};
 for (int i = '1'; i <= '9'; i++)
  for (int j = '0'; j <= '9'; j++)
   for (int k = '0'; k <= '9'; k++)
    for (int l = '0'; l <= '9'; l++)
    {
     buf[0] = i;
     buf[1] = j;
     buf[2] = k;
     buf[3] = l;
     numList.push_back(buf);
    }
}

string RanddomNum()
{
 srand(time(NULL));
 int i = rand() % 9000 + 1000;
 char buf[5] = {0};
 sprintf(buf, "%d", i);
 return buf;
}

int CountN(const string &guess, const string &num)
{
 string s = num;  // 復制num，用于下面避免重復匹配的操作
 int count = 0;
 for (int i = 0; i < 4; i++) // 對guess中每一個數字
 {
  string::size_type pos = s.find(guess[i]);
  if (pos != string::npos)
  {
   count++;
   s[pos] = 'x';  // 為避免重復匹配，將它替換為字符’x’
  }
 }
 return count;
}

int CountP(const string &guess, const string &str)
{
 int count = 0;
 for (int i = 0; i < 4; i++)
  count += (guess[i] == str[i]);
 return count;
}

string GetNextGuess()
{
 int min = numeric_limits<int>::max();
 string guess;   // 猜這個數
 list<string>::iterator it,it2;
 for (it = numList.begin();it != numList.end(); ++it)
 {
  int a[5][5] = {0};
  for (it2 = numList.begin();it2 != numList.end(); ++it2)
  {
   int x = CountN(*it, *it2);
   if (x == 0)
    a[0][0]++;    // 如果n=0，p一定=0
   else
    a[x][CountP(*it, *it2)]++;
  }
  int sum = 0;
  for (int i = 0; i < 5; i++)
   for (int j = 0; j <=i; j++) // 位置對的數字個數不會超過猜對的數字個數
    sum += a[i][j] * a[i][j];
  if (sum < min)
  {
   sum = min;
   guess = *it;
  }
 }
 return guess;
}

posted on 2008-01-04 09:22 浪跡天涯 閱讀(741) 評論(0)  編輯 收藏 引用 所屬分類: C++