今天上verycd看见一帮人在玩24点游戏,突然想研究下24点的算法问题,24点游戏几乎在任何的机器上都能找到身影,我想不应该是用穷举算法,穷举算法严格上来说不能称为一个算法.

http://www.pcvc.net/category/content.asp?sendid=238 的  天上人间(iskyflying@163.com) 发了如下的思路:
4个数计算24，最后无非出现2种情形：1对3，2对2，即：
          24＝f(a,g(b,c,d)      或者
          24＝f(g(a,b),h(c,d))
其中a,b,c,d地位相同，因此可以用一个循环遍历即可。
f,g,h为某种四则运算方法，而对g(b,c,d)又可以分解
为1对2：
          g(b,c,d)＝i(b,k(c,d))
同样i,k也是某种四则运算方法，b,c,d地位相同，可遍
历。所以最终都会化归到2个数之间的四则运算，设为
          r＝p(x,y)
显然x,y地位相同，而四则运算方法p是有限的，且对于
+和*是x,y是无序的，只需要计算一次。

这个算法对穷举遍历做了很大的改进.算法不错.我只能对之做些改进(不支持小数):

1\ 1,2,3,4,6,8,12 是24的约数,做* /的可能性更大一点,在linux下编程时对if 语句做选择优化;而其他的数字,非24的约数,不可能做* / 运算,直接运行+ -  运算

2\ 同样的道理,对 g(b,c,d)  同样可以进行 24/a 的约数处理,同理针对h(),i(),p() 运算

希望有兴趣的提点意见

附:

穷举法遍历解答树的解法 :

#include <math.h>
#include <stdio.h>
#include <dos.h>
typedef struct node { int a;
int b;
int s;
int n;
float num[5];
}NODE;
NODE WorkSpace[4];
float OrgNum[4]={0};
void init()
{ int i;
//system("cls");
printf("Please input 4 number([0,9]),use \",\" to seperate:");
scanf("%f,%f,%f,%f",&OrgNum[0],&OrgNum[1],&OrgNum[2],&OrgNum[3]);
for(i=1;i<=4;i++)
{ WorkSpace[0].num[i] = OrgNum[i-1];
}
WorkSpace[0].n=4;
}

void PushIn(int a,int b,int s,int level)
{ float newnum=-999.0;
int i,j;
switch(s)
{ case 1 : newnum = WorkSpace[level-1].num[a] + WorkSpace[level-1].num[b];break;
case 2 : newnum = WorkSpace[level-1].num[a] - WorkSpace[level-1].num[b];break;
case 3 : newnum = WorkSpace[level-1].num[a] * WorkSpace[level-1].num[b];break;
case 4 : if(WorkSpace[level-1].num[b]!=0)
{newnum = WorkSpace[level-1].num[a] / WorkSpace[level-1].num[b];
break;}
}

WorkSpace[level].a = a;
WorkSpace[level].b = b;
WorkSpace[level].s = s;
WorkSpace[level].n = (WorkSpace[level-1].n)-1;
for(i=1,j=1;i<=WorkSpace[level-1].n;i++)
{ if(i==a) {WorkSpace[level].num[j] = newnum;j++;}
if(i==b) continue;
if(i!=a&&i!=b) {
WorkSpace[level].num[j] = WorkSpace[level-1].num[i];
j++;
}
}
}

void Judge()
{ int i,a,b,s;
if(fabs(WorkSpace[3].num[1]-24)<0.00001)
{printf("\n One solution : ");
for(i=1;i<=3;i++)
{ a=WorkSpace[i].a;
b=WorkSpace[i].b;
s=WorkSpace[i].s;
printf("%3.3f",WorkSpace[i-1].num[a]);
switch(s)
{ case 1: printf("+");break;
case 2: printf("-");break;
case 3: printf("*");break;
case 4: printf("/");break;
}
printf("%3.3f",WorkSpace[i-1].num[b]);
printf(" | ");
}
// getch();
}
}

main()
{ int a,b,s,a1,b1,s1,a2,b2,s2;
init();
for(a=1;a<=4;a++)
for(b=1;b<=4;b++)
for(s=1;s<=4;s++)
if(a!=b)
{ PushIn(a,b,s,1);
for(a1=1;a1<=3;a1++)
for(b1=1;b1<=3;b1++)
for(s1=1;s1<=4;s1++)
if(a1!=b1)
{
PushIn(a1,b1,s1,2);
for(a2=1;a2<=2;a2++)
for(b2=1;b2<=2;b2++)
for(s2=1;s2<=4;s2++)
if(a2!=b2)
{
PushIn(a2,b2,s2,3);
Judge();
}
}
}
}

Trackback: http://tb.donews.net/TrackBack.aspx?PostId=327574