C语言实训求:编程实现24点游戏算法

发布网友发布时间：2022-04-23 23:05

共2个回答

热心网友时间：2023-07-09 19:08

#include<iostream>
#include<math.h>
using namespace std;
const double MIN=1E-6;
void Print(int *Rank,double *FourNum)
{
for(int i=0;i<4;i++)
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=1;num<=7;num++)
{
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=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
Calculate_24(Rank,FourNum,Oper,i,j,k,def);
}
else
{
for(i=0;i<4;i++)
{
int Remember=0;
for(j=0;j<Depth;j++)
{
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=0;i<4;i++)//输入测试数据
cin>>a[i];
cout<<"所有可能的结果："<<endl;
SearchTree(0,b,a,c,def);
if(def==false)
cout<<"No"<<endl;
}
return 0;
}

热心网友时间：2023-07-09 19:09

上面的程序是正确的，这题的解法用到的基本思想就是回溯，树的深度为最深为4，树的判断分支为加减乘除，对不满足条件的解进行剪枝（即当前结果>=24）,当到达递归边界（即树的深度为四时）时，即判断当前的结果是否符合条件（=24），符合即找到解，否则继续进行。