主题:做了个算24点牌的C程序,另求算“猜数字”思想
upday
[专家分:0] 发布于 2003-10-30 18:22:00
先说“猜数字”,是不是最少7步?
//以下为24点程序//
// + - * / -- -/
// 0 1 2 3 4 5
#include<stdio.h>
#include<math.h>
int treat(float a,float b,float c,float d);
float myF(int flag,float m,float n);
void myPrint(int type,int i,int j,int k,float a,float b,float c,float d);
int time,temp=0;
void main()
{
int i,j,k,t,again,res,flag;
float num[4];
again=1;
while(again==1)
{
printf ("\nPlease Enter 4 nums(1~13):\n");
i=0;
flag=0;
while (flag==0)
{
i++;
// printf ("Input num-%d\n",i);
for(i=0;i<4;i++)
{
scanf("%f",&num[i]);
if (num[i]<1 || num[i]>13 || num[i]!=int(num[i]))
flag++;
}
if(flag!=0)
{
printf ("Error input again\n",i);
flag=0;
}
else
flag=1;
}
for (i=0;i<4;i++)
for (j=0;j<4;j++)
if (j!=i)
for (k=0;k<4;k++)
if (k!=j && k!=i)
for (t=0;t<4;t++)
if (t!=i && t!=j && t!=k)
{
res=treat(num[i],num[j],num[k],num[t]);
}
if (res==0)
printf ("\nNo answer\n");
else ;
// printf ("time=%d\n\n",time);
printf ("\n1: Go on\n2: Quit\n");
scanf ("%d",&again);
}
}
int treat(float a,float b,float c,float d)
{
int i,j,k;
float sum1,sum2,sum3;
for (i=0;i<4;i++)
for (j=0;j<6;j++)
for (k=0;k<6;k++)
{
if ((!(i==3 && b==0)) && (!(j==3 && c==0)) && (!(k==3 && d==0)))
{
sum1=myF(i,a,b);
sum2=myF(j,sum1,c);
sum3=myF(k,sum2,d);
if (fabs(sum3-24)<0.1)
{
temp++;
myPrint(1,i,j,k,a,b,c,d);
// printf ("sum1:myF(%d,%2.0f,%2.0f) sum1=%f\n",i,a,b,sum1);
// printf ("sum2:myF(%d,%2.0f,%2.0f) sum2=%f\n",j,c,d,sum2);
// printf ("1:myF(%d,myF(%d,myF(%d,%2.0f,%2.0f),%2.0f),%2.0f) sum3=%f\n\n",k,j,i,a,b,c,d,sum3);
}
}
if (k==2)
{
sum1=myF(i,a,b);
sum2=myF(j,c,d);
sum3=sum1*sum2;
if (fabs(sum3-24)<0.1)
{
temp++;
myPrint(2,i,j,k,a,b,c,d);
// printf ("sum1:myF(%d,%2.0f,%2.0f) sum1=%f\n",i,a,b,sum1);
// printf ("sum2:myF(%d,%2.0f,%2.0f) sum2=%f\n",j,c,d,sum2);
// printf ("2:myF(%d,myF(%d,%2.0f,%2.0f),myF(%d,%2.0f,%2.0f)) sum3=%f\n\n",k,i,a,b,j,c,d,sum3);
}
}
if (k==3)
{
sum1=myF(i,a,b);
sum2=myF(j,c,d);
if (sum2!=0)
{
sum3=sum1/sum2;
if (fabs(sum3-24)<0.1)
{
temp++;
myPrint(3,i,j,k,a,b,c,d);
// printf ("sum1:myF(%d,%2.0f,%2.0f) sum1=%f\n",i,a,b,sum1);
// printf ("sum2:myF(%d,%2.0f,%2.0f) sum2=%f\n",j,c,d,sum2);
// printf ("3:myF(%d,myF(%d,%2.0f,%2.0f),myF(%d,%2.0f,%2.0f)) sum3=%f\n\n",k,i,a,b,j,c,d,sum3);
}
}
}
}
if (temp==0)
return 0;
else
return 1;
}
float myF(int flag,float m,float n)
{
// time++;
if (flag==0)
return (m+n);
if (flag==1)
return (m-n);
if (flag==2)
return (m*n);
if (flag==3)
if (n==0)
return 30000;
else
return (m/n);
if (flag==4)
return (n-m);
if (flag==5)
if (m==0)
return 30000;
else
return (n/m);
return 0;
}
void myPrint(int type,int i,int j,int k,float a,float b,float c,float d)
{
char sigle[6];
sigle[0]='+';
sigle[1]='-';
sigle[2]='*';
sigle[3]='/';
sigle[4]='-';
sigle[5]='/';
if (type==1){
if(j==4 || j==5)
{
if (k==4 || k==5)
printf("%2.0f %c (%2.0f %c (%2.0f %c %2.0f)) =24\n",d,sigle[k],c,sigle[j],a,sigle[i],b);
else
printf("(%2.0f %c (%2.0f %c %2.0f)) %c %2.0f =24\n",c,sigle[j],a,sigle[i],b,sigle[k],d);
}
else if (k==4 || k==5)
{
printf("%2.0f %c ((%2.0f %c %2.0f) %c %2.0f) =24\n",d,sigle[k],a,sigle[i],b,sigle[j],c);
}
else
printf("((%2.0f %c %2.0f) %c %2.0f) %c %2.0f =24\n",a,sigle[i],b,sigle[j],c,sigle[k],d);
}
if (type==2 || type==3)
{
// if (k==4 || k==5)
// printf("(%2.0f %c %2.0f) %c (%2.0f %c %2.0f)=24\n",c,sigle[j],d,sigle[k],a,sigle[i],b);
// else
printf("(%2.0f %c %2.0f) %c (%2.0f %c %2.0f) =24\n",a,sigle[i],b,sigle[k],c,sigle[j],d);
}
}
16 楼
yczni [专家分:340] 发布于 2004-05-28 19:40:00
我做了一个猜数字的程序确实所有的为都可以用7次之内(包括7次)猜出
虽然没有7楼说的那么高的比例,但也是很高了有88%的数6步即可.
不过我是用pascal之的思想有些笨,程序还有可改进的地方,可使6步之内的比例更高.
但我想所有的数都6 次之内有些不现实,
思想如下:
把被猜的数称为甲数
四个位上的数都不同可取0,1,2,3,4,5,6,7,8,9共有5040个数.
可以把它们放在一个数组里从小到大排列;也可以放在4个数组里每个数组存四位数的一位,这样可省去取每一位上的数的麻烦。在5040个数中随意给出一个数(称为乙数),和甲数对比可给出mAnB,把乙数和5040个数进行对比可得出mAnB的留下,得不出mAnB的数从数组中删除,也可另其值为0,如果是用四个数组存数的话,可以再开一个bool数组,用于跟踪这5040个数(我就是这样作的).再从留下的数中任选一个数,一般是选最小的(实践证明最小的数不一定是最好的),再和甲数对比出一个mAnB,再和数组中上次选剩下的数进行对比可得出mAnB的留下,其余的删除。依次进行下去最后数组中剩下一个数(或者m=4,n=0)就是甲数,如果数组为空说明在报信息的时候有错(人来报mn毕竟没有文曲星准确)
但是向上面的作法并不能保证每个数都在7次猜中,有几个数还需要9次。这说明从留下的数中任选一个最小的数作为乙数并不是最好的(最好的乙数有可能是上次选时被删掉的数,这个要自己去体会了,我也是作了这个程序才知道还有这等怪事)。但是我还是找到了一些特殊的数可以使得每个数都会在7次被猜中,那么这些特殊的数是怎么找到的呢,方法如下。
假设5040个数的数组为a0第一个乙数(我叫b1)我选0123对比剩下的数我叫a1我在选b2时不是从a1中选而是从a0中选看哪个数可以让有最少的数需要8次来猜(b3,b4…还是在a中选,并选最小),就选那个数作为b2,如果所有的b2都不能使得有0个数需要8次来猜就在第一次选时按产生的具体的m1,n1来搜索最好的b2,依次下去在不同的分类下搜索该类的就好的b.直到所有的数都在7次被猜中为止。
方法很笨,尤其是分类寻找每一次试猜中最佳的b时最辛苦,我最开始的算法找一个最佳的b要10个多小时(因为要循环的层太多了),你要知道我的机器可是AMD2500+的也不差了。也就在这时候我才深深的体会到一个算法是多么的重要,我改进了搜b的算法问题才得以解决。在分类时分的越细,并对每一类都找b可以使整体在7次之内的同时使每个数都以最快的次数被猜中,但我并没有把类分的很细,只是所有的数都在7次之内,我就没在继续分了.
如果是用c做的话最好能用队列,可以使数删除和查找快好多.
第二个思想就是递归了给一个评价函数,我没有这样作。
我的程序如下大家有兴趣可以试一试
program aaa(input,output);
label 10,20,30;
const chsh=5040;
var AA1,AA2,AA3,AA4:array [1..chsh] of 0..9;
boo:array [1..chsh] of boolean;
CC:array [1..4] of 0..9;
i,p,oo,t:integer;
m,n:array [1..15] of 0..4;
procedure pd2;
var BB:array [1..4] of integer;
j,k,l:integer;
begin for i:=1 to chsh do
if boo[i]=true then begin BB[1]:=AA1[i];
BB[2]:=AA2[i];
BB[3]:=AA3[i];
BB[4]:=AA4[i];
j:=0;
k:=0;
for l:=1 to 4 do
begin if BB[l]=CC[1] then if l=1 then j:=j+1
else k:=k+1;
if BB[l]=CC[2] then if l=2 then j:=j+1
else k:=k+1;
if BB[l]=CC[3] then if l=3 then j:=j+1
else k:=k+1;
if BB[l]=CC[4] then if l=4 then j:=j+1
else k:=k+1
end;
if (j<>m[p-1])or(k<>n[p-1]) then boo[i]:=false;
end;
end;
procedure AA;
var j,k,l:integer;
begin p:=0;
for i:=0 to 9 do
for j:=0 to 9 do
if i<>j then
for k:=0 to 9 do
if (j<>k)and(i<>k) then
for l:=0 to 9 do
if (k<>l)and(j<>l)and(i<>l) then
begin p:=p+1;
AA1[p]:=i;
AA2[p]:=j;
AA3[p]:=k;
AA4[p]:=l;
end;
end;
begin writeln;
AA;
t:=1;
while t<>0 do
begin
for i:=1 to chsh do boo[i]:=true;
oo:=0;
p:=1;
while oo<>1 do
begin for i:=1 to chsh do
if boo[i]=true then goto 10;
10:CC[1]:=AA1[i];
CC[2]:=AA2[i];
CC[3]:=AA3[i];
CC[4]:=AA4[i];
case p of
1:begin CC[1]:=0;
CC[2]:=1;
CC[3]:=2;
CC[4]:=3;
write('0123 ');
end;
2:begin CC[1]:=4;
CC[2]:=5;
CC[3]:=6;
CC[4]:=7;
if m[1]+n[1]=0 then
begin CC[1]:=8;
CC[2]:=5;
CC[3]:=9;
CC[4]:=6;
end;
if m[1]+n[1]=4 then
begin CC[1]:=1;
CC[2]:=2;
CC[3]:=3;
CC[4]:=4;
end;
write(CC[1],CC[2],CC[3],CC[4],' ');
end;
3:begin if (m[1]=0)and
(n[1]=1) then
begin if (m[2]=1)and
(n[2]=0) then
begin CC[1]:=9;
CC[2]:=0;
CC[3]:=7;
CC[4]:=8;
end;
if (m[2]=0)and
(n[2]=1) then
begin CC[1]:=9;
CC[2]:=7;
CC[3]:=8;
CC[4]:=1;
end;
end;
if (m[1]+n[1]=2)and(m[2]+n[2]=2) then
begin CC[1]:=2;
CC[2]:=7;
CC[3]:=1;
CC[4]:=3;
end;
if (m[1]+n[1]=2)and(m[2]+n[2]=1) then
begin if (m[1]=0)and
(m[2]=0) then
begin CC[1]:=2;
CC[2]:=3;
CC[3]:=1;
CC[4]:=7;
end;
if (m[1]=1)and
(m[2]=0) then
begin CC[1]:=0;
CC[2]:=9;
CC[3]:=5;
CC[4]:=6;
end;
end;
if (m[1]+n[1]=1)and(m[2]+n[2]=2) then
begin if (m[1]=0)and
(n[1]=1)and
(m[2]=0)and
(n[2]=2) then
begin CC[1]:=2;
CC[2]:=7;
CC[3]:=8;
CC[4]:=0;
end;
if (m[1]=0)and
(n[1]=1)and
(m[2]=1)and
(n[2]=1) then
begin CC[1]:=0;
CC[2]:=8;
CC[3]:=6;
CC[4]:=7;
end;
end;
write(CC[1],CC[2],CC[3],CC[4],' ');
end;
4:begin if (m[1]=0)and
(n[1]=2)and
(m[2]=0)and
(n[2]=1) then
begin if (m[3]=0)and
(n[3]=2) then
begin CC[1]:=3;
CC[2]:=4;
CC[3]:=5;
CC[4]:=1;
end;
if (m[3]=0)and
(n[3]=1) then
begin CC[1]:=8;
CC[2]:=4;
CC[3]:=3;
CC[4]:=0;
end;
if (m[3]=1)and
(n[3]=1) then
begin CC[1]:=1;
CC[2]:=6;
CC[3]:=5;
CC[4]:=2;
end;
end;
if (m[1]=0)and
(n[1]=1)and
(m[2]=0)and
(n[2]=2) then
begin if (m[3]=0)and
(n[3]=2) then
begin CC[1]:=9;
CC[2]:=4;
CC[3]:=7;
CC[4]:=2;
end;
if (m[3]=0)and
(n[3]=1) then
begin CC[1]:=2;
CC[2]:=9;
CC[3]:=7;
CC[4]:=4;
end;
if (m[3]=1)and
(n[3]=0) then
begin CC[1]:=3;
CC[2]:=7;
CC[3]:=9;
CC[4]:=5;
end;
end;
write(CC[1],CC[2],CC[3],CC[4],' ');
end;
5:begin if (m[1]=0)and
(n[1]=2)and
(m[2]=0)and
(n[2]=1)and
(m[3]=0)and
(n[3]=2)and
(m[4]=0)and
(n[4]=1) then
begin CC[1]:=1;
CC[2]:=0;
CC[3]:=7;
CC[4]:=2;
end;
write(CC[1],CC[2],CC[3],CC[4],' ');
end;
else write(CC[1],CC[2],CC[3],CC[4],' ');
end;
read(m[p],n[p]);
writeln;
if (m[p]=4)and(n[p]=0) then goto 20
else p:=p+1;
pd2;
oo:=0;
for i:=1 to chsh do if boo[i]=true then oo:=oo+1;
if oo=0 then
begin writeln('ni bao cuo shu le,an 1 chong xin kai shi');
goto 30;
end;
if oo=1 then
for i:=1 to chsh do if boo[i]=true then
begin writeln(AA1[i],AA2[i],AA3[i],AA4[i]);
goto 20;
end;
end;
20:writeln('hehe,bei wo ',p,' ci jiu cai zhong le');
writeln('an 1 ji xu wan er,an 0 tui chu you xi');
30:readln(t);
end;
end.
运得后输两个数例如"2 1"表示2A1B
程序中出现了好多实在的四位数都是通过程序硬算出来的比较好的结果,就是为了让0个数需要8次来猜.
这个程序虽然笨了点但运行一下很好用,用bp7编译一个exe文件很不错.
有哪位高人有更好的算法,请拿出来与大家赏.
我在这里多谢了!!!
20 楼
ychzh2000 [专家分:1750] 发布于 2004-05-30 11:01:00
首先,我们称最终的答案是目标数,计算机每次猜测的为猜测数。
计算机最擅长的是比较、判断。解决这个问题需要倒过来思考(不是头朝下拿大顶!)。在猜数时,是如何算出mAnB的?显然,是通过目标数和猜测数比较得出的,那么将目标数和猜测数的地位互换后比较呢,自然A和B的值还是前面的那个,这正我们解决问题的关键。如果允许目标数的第一位是0,那么共有10×9×8×7=5040种(否则有9×9×8×7=4536种)可能,这必包含在0000~9999共10000种之中,我们只需将这10000个数依次测试,首先去掉各位有重复的,然后将选出的可能组合与以前的猜测数比较,如果结果与对应的AB值相等,则说明该数可能就是目标数。或者说,假设此次要测试的数就是目标数,然后用以前的测试数与这次的数做比较,如果得到的AB值与当时用户输入的一样,则说明假设可能就是成立的,随着猜测次数的增加,待比较的条件也越苛刻,最终可以将目标数算出。
据说该游戏猜8次就可以得出结果,也许你认为这个程序需要猜很多次,但事实上一般4~7次就可以算出,目前我没发现需要猜8次的。以下是源程序,由于采用的是标准的C语言,应该适应于各种编译器(实测环境:Win98+VC6和Linux+gcc环境下调试通过),但奇怪的是在TC2下无法正常运行。
#include <stdio.h>
char table[8][6], /*二维数组,用于保存以前的猜测数和结果*/
table_n=0, /*二维数组的长度*/
A,B; /*用于接收用户输入的AB值*/
/*TC2必须将AB定义成整型,否则程序无法正常运行,其他编译器可以定义成char*/
void ask(char n1,char n2,char n3,char n4)
{/*计算机生成一个猜测数,询问用户结果*/
printf("%d%d%d%d\n",n1,n2,n3,n4);
printf("A=");
scanf("%d",&A);
printf("B=");
scanf("%d",&B);
if ((B>A)||(A>4)||(A<0)||(B<0))
{printf("Error!");
exit(0);
}
/*将猜测数和AB值写入二维数组*/
table[table_n][0]=A;
table[table_n][1]=n1;
table[table_n][2]=n2;
table[table_n][3]=n3;
table[table_n][4]=n4;
table[table_n][5]=B;
table_n++;
}
char test1(char n1,char n2,char n3,char n4)
{/*判断各位是否重复,有重复返回0,无重复返回1*/
if ((n1==n2)||(n1==n3)||(n1==n4)||(n2==n3)||(n2==n4)||(n3==n4))
return 0;
else return 1;
}
char test2(char n1,char n2,char n3,char n4)
/*将生成的待测数与以前全部的测试数比较,与原AB值不符合返回0,否则返回1*/
{char x,y,a=0,b=0;
for (x=0;x<table_n;x++) /*比较并检查B值*/
{b=0;
if (n1==table[x][1]) b++;
if (n2==table[x][2]) b++;
if (n3==table[x][3]) b++;
if (n4==table[x][4]) b++;
if (b !=table[x][5]) return 0;
}
for (x=0;x<table_n;x++) /*比较并检查A值*/
{a=0;
for(y=1;y<=4;y++)
{if(n1==table[x][y]) a++;
if(n2==table[x][y]) a++;
if(n3==table[x][y]) a++;
if(n4==table[x][y]) a++;
if(a > table[x][0]) return 0;
}
if (a!=table[x][0]) return 0;
}
return 1;
}
int main()
{char n1,n2,n3,n4,counter=0;
table_n=0;
for(n1=1;n1<=9;n1++)/*如果第一位运行是0,则应从你n1=0开始*/
for(n2=0;n2<=9;n2++)
for(n3=0;n3<=9;n3++)
for(n4=0;n4<=9;n4++)
{if(!test1(n1,n2,n3,n4)) continue;
if(!test2(n1,n2,n3,n4)) continue;
printf("%d: ",++counter);
ask(n1,n2,n3,n4);
if (B==4)/*猜出结果,退出程序*/
{printf("Haha!");
exit(0);
}
}
/*遍历了0000~9999所有的可能,没有满足条件的,说明用户输入的信息有错*/
printf("Error!");
}