我的解法是把这个问题分解成了两个子问题，首先求出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)
主程序为了简化，省去了对输入的检查，楼主可以自己添加。
#include<iostream>#include<math.h>
using namespace std
const double MIN=1E-6
void Print(int *Rank,double *FourNum)
{
for(int i=0i<4i++)
cout<<FourNum[Rank[i]]<<" "
cout<<endl
}
void Calculate_24(int *Rank,int *FourNum,char *Oper,int i,int j,int k,bool def)
{
double res=0
switch(i)
{
case 0:
res=FourNum[Rank[0]]+FourNum[Rank[1]]
break
case 1:
res=FourNum[Rank[0]]-FourNum[Rank[1]]
break
case 2:
res=FourNum[Rank[0]]*FourNum[Rank[1]]
break
case 3:
res=FourNum[Rank[0]]/FourNum[Rank[1]]
break
}
switch(j)
{
case 0:
res=res+FourNum[Rank[2]]
break
case 1:
res=res-FourNum[Rank[2]]
break
case 2:
res=res*FourNum[Rank[2]]
break
case 3:
res=res/FourNum[Rank[2]]
break
}
switch(k)
{
case 0:
res=res+FourNum[Rank[3]]
break
case 1:
res=res-FourNum[Rank[3]]
break
case 2:
res=res*FourNum[Rank[3]]
break
case 3:
res=res/FourNum[Rank[3]]
break
}
if(fabs(res-24)>MIN)
return
else
{
def=true
for(int num=1num<=7num++)
{
switch(num)
{
case 1:
cout<<FourNum[Rank[0]]
break
case 3:
cout<<FourNum[Rank[1]]
break
case 5:
cout<<FourNum[Rank[2]]
break
case 7:
cout<<FourNum[Rank[3]]
break
case 2:
cout<<Oper[i]
break
case 4:
cout<<Oper[j]
break
case 6:
cout<<Oper[k]
break
}
}
cout<<endl
}
}
void SearchTree(int Depth,int *Rank,int *FourNum,char *Oper,bool def)
{
int i,j,k
if(Depth==4)
{
for(i=0i<4i++)
for(j=0j<4j++)
for(k=0k<4k++)
Calculate_24(Rank,FourNum,Oper,i,j,k,def)
}
else
{
for(i=0i<4i++)
{
int Remember=0
for(j=0j<Depthj++)
{
if(Rank[j]==i)
Remember=1
}
if(Remember)
continue
Rank[Depth]=i
SearchTree(Depth+1,Rank,FourNum,Oper,def)
}
}
}
int main()
{
int a[4],b[4],time
char c[4]={'+','-','*','/'}
bool def=false
cin>>time
while(time--)
{
for(int i=0i<4i++)//输入测试数据
cin>>a[i]
cout<<"所有可能的结果："<<endl
SearchTree(0,b,a,c,def)
if(def==false)
cout<<"No"<<endl
}
return 0
}
1、8除以4得2。2、2乘以8得16。
3、16加8得24。24点程序算法用加、减、乘、除以及适当的括号连接，无论顺序，使计算结果为24。以上则是8848算24点计算方式。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）