#include <stdlib.h>
#include <math.h>
char op[3], o[5]="+-*/"
float n[4], on[10]
int used[4] = {0}, top=0, tp=0, x
void chk(float k)
void search24(int d)
float calc(float n1, float n2, char o)
void make(int i, float p, float q, char o, int d)
int main( void )
{
printf("please input 4 card number:\n")
scanf("%f%f%f%f", &n[0], &n[1], &n[2], &n[3])
search24(0)
printf("No answer.\n")
return 0
}
void chk(float k)
{
if( (tp != 3) || ( fabs(k-24.0) >0.000001 )) //没有用完3个运算符或者结果不为24就退出.
return
for(x=0x<5x+=2) //这样设计是为了使3个选中的符号都可以得到输出.
printf("%g%c%g=%g\n", on[x], op[x/2], on[x+1], //分析得到的.
calc(on[x], on[x+1], op[x/2]))
system("pause")
exit(0)
}
float calc(float n1, float n2, char o)
{
switch(o){
case '+': return (n1+n2)
case '-': return (n1-n2)
case '*': return (n1*n2)
case '/': return (n1/n2)
default: exit(0)
}
}
void make(int i, float p, float q, char o, int d)
{
if(fabs(q)>0.000001 || o!='/') //除数不为0,或者为0的时候不能为除数.
n[i] = calc(p, q, o)
op[tp++] = o
chk(n[i])
search24(d+1)
tp-- //因为是全是全局变量,所以在做试验性的循环递归问题时,如果失败,要在递归函数后面重新恢复回原来的值
}
void search24(int d)
{
int i, j, k
float p, q
if(d>=3) //控制递归深度,就是运算符的输出个数.
return
for(i=0i<4i++)
for(j=0j<4j++)
if( (i!=j)&&(used[i]+used[j] == 0) ) //i!=j是防止重复,(used[i]+used[j] == 0)是防止又再匹配已经用过的j,
//但是i可以新来.
{
used[j] = 1 //j得到匹配之后,赋值为1,表示已经使用
p=n[i]
q=n[j]
on[top++] = p
on[top++] = q
for(k=0k<4k++) //运算符的循环试用.
make(i, p, q, o[k], d)
n[i] = p //因为是全是全局变量,所以在做试验性的循环递归问题时,
used[j] = 0 //如果失败,要在递归函数后面重新恢复回原来的值
top -= 2 //
}
}
出处:http://blog.sina.com.cn/s/blog_491de9d60100d5er.html
下面是我自己写的一个程序:我的解法是把这个问题分解成了两个子问题，首先求出4个数字的无重复全排列，放到一个数组里面，再对没一个排列情况，从头到尾穷举所有的四则运算情况。注意到除法是特殊的，我用x/y表示x除以y，用x|y表示x分之y。注意到，如果穷举的解得到-24的话，只需要把有减法的地方调换一下顺序就可以了，代码如下
/***********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int index[4]={0,1,2,3}//used to generate subscription collection
int sub[4] //used in p() only
float f[4]={8.0f,3.0f,3.0f,8.0f}//the 24 point numbers
float fs[24][4]//all possible permutaions of f
float tmp[4] //used for buf
int g_number=0//number of permutations
float RES[4]
char op[3]
void p(int idx){//求全排列的函数
if(idx==4){
for(int i=0i<4++i){tmp[i]=f[sub[i]]}
for(int g=0g<g_number++g){if(memcmp(fs[g],tmp,sizeof(float)*4)==0)return}
for(int i=0i<4++i){fs[g_number][i]=f[sub[i]]}
g_number++
return
}
for(int i=0i<4++i){//make subscription collections
bool dupflag=false
for(int j=0j<idx++j){if(sub[j]==i)dupflag=true}
if(dupflag==true)continue
sub[idx]=index[i]
p(idx+1)
}
}
void solve(int L){//对某个排列，递归求所有四则运算的结果，找到就退出
if(L==3){
if(fabs(fabs(RES[L])-24.0f)<0.01f){
printf("Found solution,RES=%f,((%d%c%d)%c%d)%c%d\n",RES[L],
(int)f[0],op[0],
(int)f[1],op[1],
(int)f[2],op[2],
(int)f[3])
exit(0)
}
return
}
for(int j=0j<5++j){//j judges for operators
if(j==0){RES[L+1]=RES[L]+tmp[L+1]op[L]='+'solve(L+1)}
if(j==1){RES[L+1]=RES[L]-tmp[L+1]op[L]='-'solve(L+1)}
if(j==2){RES[L+1]=RES[L]*tmp[L+1]op[L]='*'solve(L+1)}
if(j==3&&tmp[L+1]!=0)
{RES[L+1]=RES[L]/tmp[L+1]op[L]='/'solve(L+1)}
if(j==4&&RES[L+1]!=0)
{RES[L+1]=tmp[L+1]/RES[L]op[L]='|'solve(L+1)}
}
}
int main(int argc,char* argv[]){//should avoid 0
f[0]=atoi(argv[1])
f[1]=atoi(argv[2])
f[2]=atoi(argv[3])
f[3]=atoi(argv[4])
p(0)
for(int i=0i<g_number++i){
memcpy(tmp,fs[i],sizeof(float)*4)
RES[0]=tmp[0]
for(int t=0t<4++t){ printf("%d,",(int)tmp[t])}
printf("\n")
solve(0)
}
printf("Found no solution :( \n")
return 0
}
----------编译运行，运行时的参数就是4个数字
g++ p.cpp &&./a.out 1 5 5 5
1,5,5,5,
Found solution,RES=-24.000000,((1/5)-5)*5
g++ p.cpp &&./a.out 8 3 3 8
8,3,3,8,
Found solution,RES=-24.000006,((8/3)-3)|8
上面这个解写出来就是
8
--------- = 24
3-(8/3)
主程序为了简化，省去了对输入的检查，楼主可以自己添加。
