题解 | #24点游戏算法#

#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;
}