請(qǐng)人想一個(gè)四位的整數(shù)，計(jì)算機(jī)來(lái)猜，人給計(jì)算機(jī)提示信息，最終看計(jì)算機(jī)用幾次猜出一個(gè)人“想”的數(shù)。請(qǐng)編程實(shí)現(xiàn)。
問(wèn)題分析
解決這類問(wèn)題時(shí)，計(jì)算機(jī)的思考過(guò)程不可能象人一樣具完備的推理能力，關(guān)鍵在于要將推理和判斷的過(guò)程變成一種機(jī)械的過(guò)程，找出相應(yīng)的規(guī)則，否則計(jì)算機(jī)難以完成推理工作。
基于對(duì)問(wèn)題的分析和理解，將問(wèn)題進(jìn)行簡(jiǎn)化，求解分為兩個(gè)步聚來(lái)完成：首先確定四位數(shù)字的組成，然后再確定四位數(shù)字的排列順序。可以列出如下規(guī)則：
1)產(chǎn)生四位數(shù)字的全部排列產(chǎn)生四位數(shù)字的全部排列。
2)生成隨機(jī)數(shù),根據(jù)，根據(jù)人輸入的正確數(shù)字及正確位置的數(shù)目，進(jìn)行刷選。
3)再剩下的結(jié)果中，生成隨機(jī)數(shù)，重復(fù)步驟2，直至找到。
GetNextGuess()函數(shù)算法不知該如何理解？
我覺(jué)得這個(gè)函數(shù)算法不好，沒(méi)有充分利用先前的猜數(shù)以及結(jié)果進(jìn)行下一次的猜數(shù)。
程序代碼：
#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回合隨機(jī)猜數(shù)
int n, p; // 分別表示有幾個(gè)數(shù)字猜對(duì)，有幾個(gè)數(shù)字位置也對(duì)
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) // 如果沒(méi)有n個(gè)數(shù)字對(duì)
{
it = numList.erase(it); // 不可能是被猜數(shù)，篩掉
continue;
}
if (CountP(guess, *it) != p) // 如果沒(méi)有p個(gè)數(shù)字位置對(duì)
{
it = numList.erase(it); // 不可能是被猜數(shù)，篩掉
continue;
}
++it;
}
if (numList.empty()) // 沒(méi)有候選數(shù)了，人欺騙計(jì)算機(jī)
{
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; // 復(fù)制num，用于下面避免重復(fù)匹配的操作
int count = 0;
for (int i = 0; i < 4; i++) // 對(duì)guess中每一個(gè)數(shù)字
{
string::size_type pos = s.find(guess[i]);
if (pos != string::npos)
{
count++;
s[pos] = 'x'; // 為避免重復(fù)匹配，將它替換為字符’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; // 猜這個(gè)數(shù)
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++) // 位置對(duì)的數(shù)字個(gè)數(shù)不會(huì)超過(guò)猜對(duì)的數(shù)字個(gè)數(shù)
sum += a[i][j] * a[i][j];
if (sum < min)
{
sum = min;
guess = *it;
}
}
return guess;
}