学步园

这是求解24点问题的一个解法，考虑到可移植性，我只用了C的标准库函数。
程序是我根据《编程之美》里面的算法写的，使用的基本算法是递归。基本思想是4个数中取两个，
计算后变为3个数，再取2个计算，直到结果为1个数为止，若其值为24就输出该组表达式。
依次遍历所有表达式组合，可以找出所有满足条件的解。
题中规定方案不能重复，加法乘法交换律算不同方案。但如果四个数中有重复的，那么结果就会出现完全重复的情况。
例如：输入2 4 4 5 就会出现2个(5-2)x(4+4)的表达式
虽然这也是交换律导致的，但貌似不符合要求，不知道该怎么解决

这绝对是个C程序，不知道为什么CSDN歧视C.......只好选C++了

 #include<stdio.h><br /> #include<string.h><br /> #include<stdlib.h><br /> #include<math.h></p> <p>#define Threshold 1e-6 //浮点数精度<br /> #define CardsNumber 4 //纸牌数目<br /> #define ResultValue 24 //最终结果</p> <p>typedef char string[20];<br /> string result[CardsNumber]; //用于存储表达式<br /> double number[CardsNumber]; //用于存储初始数字及中间运算值<br /> int success=0; //标志位，1表示有解</p> <p>/************************************************<br /> 函数名:PointGame<br /> 参数：类型int 表示纸牌数目<br /> 返回值：类型int 表示是否有解，有解返回1,否则返回0<br /> 作用：输出任意个数字通过+、-、X、/、()<br /> 运算符组成的表达式的值等于指定结果的表达式<br /> *************************************************/<br /> int PointGame(int n)<br /> {<br /> int i,j,len;<br /> if(n == 1)<br /> {<br /> if(fabs(number[0] - ResultValue) < Threshold) //比较最终结果是否等于24，结果为浮点数<br /> {<br /> //输出最终表达式，去掉外层括号<br /> len=strlen(result[0]);<br /> result[0][len-1]='/0';<br /> printf("%s/n",&result[0][1]);<br /> success=1;<br /> return 1;<br /> }<br /> else<br /> {<br /> return 0;<br /> }</p> <p> }</p> <p> for(i = 0; i < n; i++)<br /> {<br /> for(j = i +1 ; j < n; j++)<br /> {<br /> double a, b;<br /> string expa, expb;</p> <p> a = number[i];<br /> b = number[j];<br /> number[j] = number[n - 1];</p> <p> strcpy(expa,result[i]);<br /> strcpy(expb,result[j]);<br /> strcpy(result[j],result[n-1]);</p> <p> //加法操作 a+b<br /> number[i] = a + b;<br /> strcpy(result[i],"(");<br /> strcat(result[i],expa);<br /> strcat(result[i],"+");<br /> strcat(result[i],expb);<br /> strcat(result[i],")");</p> <p> PointGame(n-1);</p> <p> //减法操作 a-b<br /> number[i] = a - b;<br /> strcpy(result[i],"(");<br /> strcat(result[i],expa);<br /> strcat(result[i],"-");<br /> strcat(result[i],expb);<br /> strcat(result[i],")");</p> <p> PointGame(n-1);</p> <p> //减法操作 b-a<br /> number[i] = b - a;<br /> strcpy(result[i],"(");<br /> strcat(result[i],expb);<br /> strcat(result[i],"-");<br /> strcat(result[i],expa);<br /> strcat(result[i],")");</p> <p> PointGame(n-1);</p> <p> //乘法操作 a*b<br /> number[i] = a * b;<br /> strcpy(result[i],"(");<br /> strcat(result[i],expa);<br /> strcat(result[i],"x");<br /> strcat(result[i],expb);<br /> strcat(result[i],")");</p> <p> PointGame(n-1);</p> <p> //除法操作 a/b, 如果除数不为0<br /> if(b != 0)<br /> {<br /> number[i] = a / b;<br /> strcpy(result[i],"(");<br /> strcat(result[i],expa);<br /> strcat(result[i],"/");<br /> strcat(result[i],expb);<br /> strcat(result[i],")");</p> <p> PointGame(n-1);</p> <p> } </p> <p> //除法操作 b/a , 如果除数不为0<br /> if(a != 0)<br /> {<br /> number[i] = b / a;<br /> strcpy(result[i],"(");<br /> strcat(result[i],expb);<br /> strcat(result[i],"/");<br /> strcat(result[i],expa);<br /> strcat(result[i],")");</p> <p> PointGame(n-1);</p> <p> }</p> <p> //将a,b放回数组<br /> number[i] = a;<br /> number[j] = b;<br /> strcpy(result[i],expa);<br /> strcpy(result[j],expb);</p> <p> }<br /> }<br /> return success;</p> <p>}</p> <p>void main()<br /> {<br /> int x,i;<br /> for(i =0; i< CardsNumber; i++)<br /> {<br /> printf("the %dth number:",i);<br /> scanf("%d",&x);<br /> number[i] = x;<br /> itoa(x,result[i],10);<br /> }</p> <p> printf("/n");<br /> if(0==PointGame(CardsNumber))<br /> {<br /> printf("无解！/n");</p> <p> }</p> <p> system("pause"); </p> <p>}<br />