题解 | #24点游戏算法#
24点游戏算法
https://www.nowcoder.com/practice/fbc417f314f745b1978fc751a54ac8cb
#include<stdio.h>
#include<string.h>
float num[4] ;
int his[4] = { 0 };
int v[4]={0};
float b[4]={0};
int ans;
float sum;
int flag=0;
int dfs(int x, float sum)
{
if (x == 3)
{
if (sum == 24.0)
{
return 1;
}
else { return 0; }
}
int tx;
tx = x + 1;
if (tx >= 0 && tx <= 3 && his[tx] == 0)
{
his[tx] = 1;
//sum += b[tx];
if (dfs(tx, sum+b[tx])||dfs(tx, sum-b[tx])||dfs(tx, sum*b[tx])||dfs(tx, sum/b[tx]))
{
return 1;
}
else { his[tx] = 0; }
}
return 0;
}
void dfs2(int i)
{
if(i>=4)
{
ans++;
sum=b[0];
his[0]=1;
if(dfs(0,sum)==1){
flag=1;
//printf("%f %f %f %f",b[0],b[1],b[2],b[3]);
}
return;
}
for(int k=0;k<4;k++)
{
if(k>0&&num[k]==num[k-1]&&v[k-1]==0){continue;}
if(v[k]==0)
{
v[k]=1;
b[i]=num[k];
dfs2(i+1);
v[k]=0;
}
}
return;
}
int main(void)
{
for (int i = 0; i < 4; i++)
{
scanf("%f", &num[i]);
}//输入完成
//求全排列
//先冒泡排序，为的是将相同元素移动到相邻位置，便于后续去重
for(int i=0;i<4;i++)
{
for(int j=0;j<4-1-i;j++)
{
if(num[j]>num[j+1])
{
float temp;
temp=num[j+1];
num[j+1]=num[j];
num[j]=temp;
}
}
}
dfs2(0);
if(flag==0){printf("false");}
else{printf("true");}
// float test=5.0/2.0;
//printf("%f",test);
return 0;
}
