题解 P1236 【算24点】

Y_B_Y · 2019-09-02 23:49:29 · 题解

搜索思路一定要清晰 (不然之后都不知道自己怎么错的)

注意点:

1.数字不一定要相邻,随便那两个就可以进行运算了(顺序也不要管)

2.2-3是不可以的

所以这一题就一开始先确定最先运算的两个数,然后将得出来的数再和剩下的数进行运算,因为a-b!=b-a,所以剩下的数与得出来的数也要反过来进行计算,全部运算只要枚举运算符与参与运算的数就可以了,期间还要记录计算的步骤

有的同学可能会发现,为什么一定用得出来的数再和剩下的数进行运算,而不用另两个数进行运算呢,因为用这种方法和用其他方法的步骤可能不一样,但最后的结果应该都是一样的 (这种做法貌似就是楼上某一位dalao做法的简单版)

举个栗子吧

然后将10和其他数进行运算

然后再将3与其他数进行运算

具体的步骤就在代码里讲吧

#include<bits/stdc++.h>
using namespace std;
int a[500],f[500][500];//a存储输入的数字,f存储步骤,这里500都是随便开的(不要学我偷懒)
bool b[500];//数字是否用过
char c[500]={'@','+','-','*','/'};/输出的时候用
int jsq(int k,int k1,int k2)//k为运算符,1,2,3,4对应加减乘除,k1前,k2后
{
    if(k==1) return k1+k2;//这个没有风险直接返回
    if(k==2)
    {
        if(k1>=k2) return k1-k2;//一定要k1大于等于k2
        else return -888;//否则,报错
    }
    if(k==3) return k1*k2;
    if(k==4)
    {
        if(k2!=0&&k1%k2==0) return k1/k2;//一定要整除,还有k2!=0要放在前面
        else return -888;//否则,报错
    }
}
void print()//输出步骤
{
    for(int p=1;p<=3;p++)
    {
        cout<<max(f[p][1],f[p][3])/*输出较大值*/<<c[f[p][2]]/*输出运算符*/<<min(f[p][1],f[p][3])/*输出较小*/<<'='<<f[p][4]<<endl;
    }
    exit(0);//直接退出整个程序
}
void dfs(int k,int num)//k为第k-1次计算结束(只要计算3次),num为得出的数
{
    if(k==4)//搜完了
    {
        if(num==24) print();//如果最后得出的数为24,输出
        return;//结束
    }
    for(int i=1;i<=4;i++)//枚举数字
    {
        if(b[i]==0)//没用过
        for(int l=1;l<=4;l++)//枚举运算符
        {
            int n=jsq(l,num,a[i]);//计算
            if(n!=-888)//如果没有报错(就是返回-888)
            {
                b[i]=1;//记录为用过
                f[k][1]=num;//记录步骤
                f[k][2]=l;
                f[k][3]=a[i];
                f[k][4]=n;
                dfs(k+1,n);//下一次计算,更新得出的数为n
                b[i]=0;//回溯
            }
            n=jsq(l,a[i],num);//反过来
            if(n!=-888)//下面都是和前面一样的
            {
                b[i]=1;
                f[k][1]=num;
                f[k][2]=l;
                f[k][3]=a[i];
                f[k][4]=n;
                dfs(k+1,n);
                b[i]=0;
            }
        }
    }
}
int main()
{
    cin>>a[1]>>a[2]>>a[3]>>a[4];//输入
    for(int i=1;i<=4;i++)//一开始将两个数先运算,这里是枚举第一个数
    {
        for(int j=1;j<=4;j++)//枚举第二个数
        {
            if(i==j) continue;//不能是同一个数,continue就是跳过后面内容的作用
            for(int l=1;l<=4;l++)//枚举运算符
            {
                int n=jsq(l,a[i],a[j]);//计算
                if(n!=-888)//如果没报错
                {
                    f[1][1]=a[i];//记录步骤
                    f[1][2]=l;
                    f[1][3]=a[j];
                    f[1][4]=n;
                    b[i]=1;//记录为用过
                    b[j]=1;
                    dfs(2,n);//n为得出的数
                    b[i]=0;//回溯
                    b[j]=0;
                }
            }
        }
    }
    cout<<"No answer!";//前面都没有得出过,输出不可以
    return 0;
}