猜数字游戏－人出题，电脑猜(转贴)
/*
* 文件名称: GuessNum.h
* 程序描述:
* 常见的小游戏【猜数字】的智能解法：
* 猜数字游戏: 即有四位十进制数字，一般可猜8次
* 每次返回aAbB（A表示数字正确并且位置正确，B表示数字正确但位置不正确）
* 如：假设要猜的数字是1234，如果游戏者猜0134即返回2A1B（3、4为A，1为B）
*
* 算法：每次选取熵最大的数字进行猜测，即：贪心算法
*
* 还有一个程序使用决策树的方法，参见GuessNumAll.cpp
* 另外还有一个程序GuessNumGame.cpp用来模拟猜数字游戏
*/
#include <vector>
#include <list>
#include <string>
using namespace std;
class GuessNum
{
/* */
public:
GuessNum(void);
void Guess(void);
void PrintStack(void);
/* */
private:
bool ConfirmAB(string first, string second, string ab);
bool GuessNext(void);
int GetABValue(string first, string second);
const static int m_base[5];
string m_lastGuess;
list<string> m_setAll;
list<string> m_setCurr;
vector<string> m_stack;
int m_times;
};
/*
[01/19-21:54:50]
猜数字游戏:
? 即有四位十进制数字，一般可猜8次
? 每次返回aAbB（A表示数字正确并且位置正确，B表示数字正确但位置不正确）
? 如：假设要猜的数字是1234，如果游戏者猜0134即返回2A1B（3、4为A，1为B）
思路：
? 模拟人猜数字的过程，先构造一个集合包括所有可能的数字（10*9*8*7=5040种），先乱猜一个，根据返回xAxB来把原来集合里面的不符合的都删掉，然后根据选取下一个。选下一个的原则是：选最能区分剩下的集合的那个数，即：被选择的那个数得到的返回值为xAxB中任意一种的概率差不多。
? 我使用信息量的方法，即：
?? 对集合set（size个）中每一个数字n，用n的每一种返回值（从0a0b到4a0b，共有15种）做删减，看各剩下多少个，用pi表示第i种返回值得情况，然后根据信息量公式：info(n) = ∑(pi/size) * log(pi/size)计算，然后取max(info(i)) i=0..size;最大的那个info(n)对应的数字就是被选择的数字。
下面是一个由电脑猜数字的程序 猜(0-9)中4个全排列中的一个 现在我想修改成(1-9)中选4个全排列中一个.
-------------------
我修改的思路是:缩小全集范围 把带0的4位数字排除 下面红色为我修改的部分
修改第一次随机猜过滤带0的随机数
但修改结果:随机数仍然有0出现.全集也仍然有0 这里我想惭愧我之前没有学C++有些看不懂 但对C比较熟悉点.谁能帮小弟弟 指点迷津 或提出你修改的方法 小弟不胜感谢.因为急需这个程序.请帮我修改下
/*
* 文件名称: GuessNum.cpp
* 程序描述: 实现GuessNum类
*/
#pragma warning(disable : 4786)
#include <iostream>
#include <algorithm>
#include <ctime>
#include <strstream>
#include <cmath>
#include "GuessNum.h"
const int GuessNum:: m_base[5]={ 0, 5, 9, 12, 14 };
/* */
GuessNum::GuessNum(void)
{
m_times=0;
//产生m_setAll
unsigned int num=123;
char a[10];
while(num < 10000)
{
bool valid=true; //表示数字没有重复
sprintf(a, "%04u", num);
for(int i=0; i < 4; i++)
{
for(int j=i + 1; j < 4; j++)
if(a[i] == a[j]) valid=false;
}
for(int q=0; q < 4; q++)
if(a[q] == '0') valid=false; //红色部分为我添加的内容想缩小全集范围排除带0的数字
if(valid) m_setAll.push_back(a);
num++;
} //#while(num)
} //#GuessNum()
/* */
void GuessNum::Guess(void)
{
//重置数据集
m_setCurr.clear();
list<string>::iterator itCopy=m_setAll.begin();
while(itCopy != m_setAll.end()) m_setCurr.push_back(*itCopy++);
m_stack.clear();
m_times=0;
//随机产生第一次猜测
srand((unsigned)time(NULL)); //随机数种子
bool valid=false;
unsigned int iCode;
while(!valid)
{
iCode=rand();
while(iCode > 9999) iCode/=10;
char a[10];
sprintf(a, "%04u", iCode);
valid=true;
for(int i=0; i < 4; i++)
for(int j=i + 1; j < 4; j++)
if(a[i] == a[j]) valid=false;
for(int q=0; q < 4; q++)
if(a[q] == '0') valid=false; //红色部分为我添加的内容想排除带0的随机4位数
if(valid) m_lastGuess=a;
}
while(!GuessNext());
} //#Guess()
/* */
bool GuessNum::GuessNext(void)
{
m_times++;
//进行猜测，获取猜测结果
string result;
cout << "\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
PrintStack();
cout << "第 " << m_times << " 次猜测: " << m_lastGuess << endl;
cout << "请输入结果[?A?B]:";
bool valid=false;
while(!valid)
{
cin >> result;
//判断输入是否合法
if(result.length() == 4 &&
result[0] >= '0' &&
result[0] <= '4' &&
result[2] >= '0' &&
result[2] <= '4' &&
(result[0] + result[2]) <= ('0' + '4') &&
toupper(result[1]) == 'A' &&
toupper(result[3]) == 'B')
{
valid=true;
}
if(!valid) cout << "输入不合法，请重新输入:";
} //#while
//将结果入栈
strstream strm;
strm << "第 " << m_times << "次: " << m_lastGuess << " -> " << result << endl;
string strTemp;
getline(strm, strTemp);
m_stack.push_back(strTemp);
if(result[0] != '4')
{
//尚未猜对, 进行数据集的约简
list<string>::iterator itRemove;
itRemove=m_setCurr.begin();
while(itRemove != m_setCurr.end())
{
if(!ConfirmAB(m_lastGuess, *itRemove, result))
itRemove=m_setCurr.erase(itRemove);
else
itRemove++;
}
//@@
if(m_setCurr.size() == 0)
{
cerr << "你检查一下，肯定是哪一步输入错误！" << endl;
cerr << "程序结束" << endl;
exit(1);
}
else if(m_setCurr.size() == 1)
{
m_lastGuess=m_setCurr.front();
return false;
}
//@@
cout << "m_setAll.size() = " << m_setAll.size() << endl;
cout << "m_setCurr.size() = " << m_setCurr.size() << endl;
//产生下一个猜测数据
double eMax=0; //max entropy, 最大信息量
string strMax; //提供最大信息量的那个数串
list<string>::iterator itEn=m_setCurr.begin();
//计算用每一个数来做区分时的信息量，取提供最大信息量的那个
double eCurr=0;
int abList[15]; //从0a0b到4a0b共15种情况
memset(abList, 0, 15 * sizeof(int) / sizeof(char));
while(itEn != m_setCurr.end())
{
list<string>::iterator itTemp=m_setCurr.begin();
while(itTemp != m_setCurr.end())
{
abList[GetABValue(*itEn, *itTemp)]++;
itTemp++;
}
//统计熵
//@@
// cout << "sigh.." << *itEn << endl;
double eTemp=0;
double eDiv=0;
for(int i=0; i < 15; i++)
{
if(abList[i] != 0) //避免0*log0
{
eDiv=double(abList[i]) / double(m_setCurr.size());
eTemp+= -eDiv * log(eDiv);
}
}
if(eTemp > eMax)
{
cout << "here eMax = " << eMax << endl;
eMax=eTemp;
strMax=*itEn;
}
itEn++;
} //#while(itEn)
m_lastGuess=strMax;
return false;
} //#if(result[0] != 4)
else // result[0] == 4
{
cout << "\n答案是: " << m_lastGuess << endl;
cout << "一共用了 " << m_times << "次" << endl;
PrintStack();
return true;
}
} //#GuessNext()
/* */
void GuessNum::PrintStack(void)
{
for(int i=0; i < m_stack.size(); i++) cout << m_stack[i] << endl;
} //#PrintStack()
/* */
inline bool GuessNum::ConfirmAB(string first, string second, string ab)
{
int a=0, b=0;
for(int i=0; i < 4; i++)
{
for(int j=0; j < 4; j++)
if(first[i] == second[j])
if(i == j)
a++;
else
b++;
}
if(ab[0] == char(a + '0') && ab[2] == char(b + '0'))
return true;
else
return false;
} //#ConfirmAB()
/* */
inline int GuessNum::GetABValue(string first, string second)
{
int a=0;
int b=0;
for(int i=0; i < 4; i++)
{
for(int j=0; j < 4; j++)
if(first[i] == second[j])
if(i == j)
a++;
else
b++;
}
return m_base[a] + b;
} //#GetABValue()
//测试程序
#include <iostream>
#include "GuessNum.h"
using namespace std;
int main()
{
GuessNum gn;
cout << "GuessNum object created..." << endl;
gn.Guess();
return 0;
}
