相信大家都玩过一种游戏,大概最早在文曲星那些电子词典上的,名字叫猜数字:
规则大概是这样的:
0-9中随即抽选4个数,组成4位数,(这十个数字可以重复也可以不重复,我们这次仅仅讨论他们不重复的情况,也就是8854,4154这样的数值是不行的.1234,5678这样的数值是合法的.)
然后你猜这个数值,计算机给出你猜的结果,用xAyB表示,A表示你猜对,并且这个数值的位置也正确的有X个,B表示你猜对,但是位置的错误的数值有Y个.
引用
举一个例子,比如这次要猜的数值是1357:
你输入2468,则计算机返回"0A0B",说明你一个也没猜对.连位置不正确的也没有.
你输入1234,则计算机返回"1A1B",说明你猜对了一个数值,并且这个数值的位置也正确(1),你猜对了一个数值,但是这个数值的位置错误(3).
你输入7351,则计算机返回"2A2B".....
然后一步步的根据返回的信息判断,进而猜出正确的答案.
应该很好理解,如果谁想试试的,QQ上面也有这个游戏"互动空间->小I机器人,输入?,点击智力游戏的猜数字."
当上上面说的是机器出题目,人来猜..
这次的挑战呢,就反了过来,人来设计一种算法来猜人出的题目,看谁用最短的时间猜出这个答案.
也就是写一个软件,替人猜测出这个数字,看谁用的次数最少.
这里给出这个问题的通用算法(筛选法):
代码
0000-9999中不重复的数值有5040个.
1.随即抽选一个数字,输出给人,人给出计算机此次猜测的结果(比如是xAyB).
2.计算机根据这次猜测的结果对所有的剩下的数字进行筛选,出去不符合的数值.
3.从剩下的数值从随即挑选1个,重复1-2的步骤.
最终得到结果.这样的算法效率如下:
一步就猜出的数值有: 1
二步就猜出的数值有: 13
三步就猜出的数值有: 108
四步就猜出的数值有: 596
五步就猜出的数值有: 1668
六步就猜出的数值有: 1768
七步就猜出的数值有: 752
八步就猜出的数值有: 129
九步就猜出的数值有: 5
总数5040个.
算法我就不给出了,显然,这不是最佳的算法,目前最好的算法是6步以内就可以得到全部的答案(可惜我没找到这个算法,这是种信息摘要算法,先用几步取得大量的信息,然后分析之后用剩下的几步确定答案).
下面就欢迎大家参加这个编程挑战
所有写出算法,或者有相关算法理论的朋友都帖出自己的咚咚吧.
一起试试吧..just do it
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdlib.h>
using namespace std;
//全局VECTOR,用于存储数字集合
list<string> number;
void init(void)
{/////////////初始化VECTOR///////////////
for(int a=0;a<=9;a++){
for(int b=0;b<=9;b++){
if(a==b)continue;
for(int c=0;c<=9;c++){
if(c==a || c==b)continue;
for(int d=0;d<=9;d++){
if(d!=a && d!=b && d!=c){
char sa[4]={a+'0',b+'0',c+'0',d+'0'};
string temp(sa,sa+4);
number.push_back(temp);
}
} }//c end
} }//a end
}//fun end
bool comp(string ss,string sd,string input)
{//比较!!如果两个数不符合条件input,则返回false
//num_s为vector中的数,num_d为猜测数,input为串
int s[4],d[4];
if(ss == sd)return false;
//分解
s[0]=ss[0]-'0';s[1]=ss[1]-'0';s[2]=ss[2]-'0';s[3]=ss[3]-'0';
d[0]=sd[0]-'0';d[1]=sd[1]-'0';d[2]=sd[2]-'0';d[3]=sd[3]-'0';
//xAyB
int x=input[0]-'0';
int y=input[2]-'0';
//comp........
do{
int xy=x+y;//共匹配的数
int sum=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(s[i]==d[j])sum++;
}
}
if(sum!=xy)return false;
//
}while(0);
do{
//绝对匹配x
if(x){
int sum=0;
for(int i=0;i<4;i++){
if(s[i]==d[i])sum++;
}
if(sum!=x)return false;
}
}while(0);
do{//仅数字匹配,位置不匹配
if(y){
int sum=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(s[i]==d[j] && i!=j)sum++;
}
}
if(sum!=y)return false;
}
}while(0);
return true;
}
void filt(string num,string input)
{//过滤!! num为猜测数,input为人输入的串
list<string>::iterator iter=number.begin();
while(iter!=number.end()){
list<string>::iterator temp=iter;
iter++;
//
if( comp(*temp,num,input)==false )number.erase(temp);
}
}
string sui_ji(void)
{//在vector中随机选个数
vector<string> temp(number.begin(),number.end());
random_shuffle(temp.begin(),temp.end());
return *(temp.begin());
}
int main(void)
{
string quit;
do{
init();
do{
string input;
string num;
cout<<"输入avalon或者AVALON或者4a4b或者4A4B结束!"<<endl;
while( 1){
num=sui_ji();
cout<<num<<'\t'<<"数据集还有"<<number.size()<<"个数"<<endl;
cin>>input;
if( input=="avalon" || input=="AVALON"){
list<string>::iterator iter=number.begin();
int enter=0;
for(;iter!=number.end();iter++){
if(enter++%8==0)cout<<endl;
cout<<*iter<<" ";
}
cout<<endl;
break;
}
if( input == "4a0b" || input =="4A0B"){
cout<<"ok"<<endl;
break;
}
filt(num,input);
}
}while(0);
//清空vector
number.erase(number.begin(),number.end());
cout<<"继续吗?";
cin>>quit;
}while(quit=="y" || quit=="Y");
cout<<"bye~~~~~~~~~~~~~~~~~"<<endl;
system("PAUSE");
return 0;
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/jyk/archive/2006/03/04/615153.aspx
分享到:
相关推荐
求由初始状态到达目标状态步数最少的解。 解决八数码问题的常用方法A*算法实现,其中A*算法又因估价函数的不同而有着不同的搜索时间。 程序说明: 在本程序中A*算法分别实现了八数码问题,其中A*算法的估价函数...
是:给出一个初始状态和一个目标状态,找出一一种从初始转变成目标状态的移动棋子步数 最少的移动步骤。下图展示了其中一种可能的初始及目标状态(仅作示例)。要求: 2 3 1 2 5 8 4 4 6 7 6 初始状态 目标状态 1.能处理...
用c++实现md5算法. 开发平台 Ubuntu14.04 运行 sudo get-apt install g++ make ./md5_test md5简介 消息摘要算法第五版(英语:Message-Digest Algorithm 5,缩写为MD5),是当前计算机领域用于确保信息传输...
生成随机数,看选中的次数最少的"个数"数字放到"排除号码里" 第一步:机选若干注号码; 第二步:将机选出的号码逐注输入到筛选器中进行筛选; 第三步:筛选结束后,系统记录了选定号码,再从这些号 码中...
问题描述:有n级台阶,一个人每次上一级或者两级,问有多少种走完n级台阶的方法。 实际情况:给定一个矩阵m,从左上角开始每次只能向右走或者向下走,最后达到右下角的位置,路径中所有数字累加起来就是路径和,返回...
有一个正整数,我要计算最少的步数将其更改为 1。 步骤的意思: 如果这个数是偶数,就除以2。这是一步。 如果这个数字是奇数,减一或加一。这是一步。 ##day3 问题是:有n个球和m个篮子,我想把球放进篮子里。 该...
1006 Do the Untwist 字符可加密成数字,指定数字可再加密。给出密文求原文 1007 Numerical Summation of a Series 求一公式的累加(浮点数) math 1008 Gnome Tetravex 移动正方型,使相邻的三角形的值相等 ...
AES 的基本要求是,采用对称分组密码体制,密钥长度的最少支持为 128、192、256,分组长度 128 位,算法应易于各种硬件和软件实现。 AES 加密数据块分组长度必须为 128 比特,密钥长度可以是 128 比特、 192 比特、...
3、经第二步处理后,SY(i, j)为空,说明前面的步骤出错,SY(i, j)值为一位数字,就说明该点的值是唯一的,可以确定了。重复第2步。 4、剩余的SY(i, j)中字符串长度最少也是两位,或更多位数。随机从这些两位数的SY...
<1> mklv -y lvinformix -c 2 rootvg 64 //在卷组rootvg上创建逻辑卷lvinformix, 大小为64(LP)×16M=1G, 磁盘镜像需用-c参数指定副本数 <2> crfs -v jfs -d lvinformix -m /opt/informix //在lvinformix上创建文件...
至于在进行除法运算时,面对无法除尽的数用户只需要保留小数点后一位数字即可。 1.6 设计心得: 设计制作类似的程序已经不是第一次了,但这次却是比以前各次都下了大功夫。虽然整个题目并不是很难,出题函数也比较...
4、剩余的SY(i, j)值最少也是二个数字的,或更多位数。随机从这些两位数的SY(i, j)中选取一个点。取其中的一位确定为该点的值后,重复第2步。如果错误遇错,则重复执行第4步。直到所有点都被确定。 注意:第2步是...