首页 > 试题广场 >

24点游戏算法

[编程题]24点游戏算法
  • 热度指数：138907 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出4个1-10的数字，通过加减乘除运算，得到数字为24就算胜利，除法指实数除法运算，运算符仅允许出现在两个数字之间，本题对数字选取顺序无要求，但每个数字仅允许使用一次，且需考虑括号运算。
此题允许数字重复，如3 3 4 4为合法输入，此输入一共有两个3，但是每个数字只允许使用一次，则运算过程中两个3都被选取并进行对应的计算操作。

输入描述:
读入4个[1,10]的整数，数字允许重复，测试用例保证无异常数字。


输出描述:
对于每组案例，输出一行表示能否得到24点，能输出true，不能输出false
示例1

输入

7 2 1 10

输出

true
算法知识视频讲解
添加回答
C
牛客687960318号头像 牛客687960318号
本题目中没有说明是否必须把四个数全部用完，这里姑且按照不必用完来解答。
大体思路就是先在数组中随便找俩个数加减乘除，将结果与剩下的数字组成新的数组，重复这一过程，知道数组中出现24这个数。
注意：本题目有两个坑！
1.需要用浮点数来存储和运算，不然对于类似7/9/9/10这样的输入会导致因为整型除法丢弃小数导致算出24
2.一定要将结果与剩下的数字重新组合，不可以直接用上一步计算出的结果进行加减乘除计算，可以试试2/3/3/10这组数据，很明显10*3-2*3=24，感觉有一半的题解都会报false。 
#include <stdint.h>
#include <stdio.h>
int dfs(float* a, int len) {
    for (int i = 1; i <= 4; i++)
        if (a[i] == 24)
            return 1;
    if (len == 1)return 0;
    for (int i = 1; i <= 4; i++)
        if (a[i] != -999)
            for (int j = 1; j <= 4; j++)
                if (i != j && a[j] != -999) {
                    float x, y;
                    x = a[i], y = a[j];
                    a[i] = x + y, a[j] = -999;
                    if (dfs(a, len - 1))return 1;
                    a[i] = x - y, a[j] = -999;
                    if (dfs(a, len - 1))return 1;
                    a[i] = x * y, a[j] = -999;
                    if (dfs(a, len - 1))return 1;
                    if (y != 0) {
                        a[i] = x / y, a[j] = -999;
                        if (dfs(a, len - 1))return 1;
                    }
                    a[i] = x, a[j] = y;
                }
    return 0;
}
int main() {
    float a[10] = {0};
    int n;
    scanf("%f%f%f%f", &a[1], &a[2], &a[3], &a[4]);
    if (dfs(a, 4))
        printf("true");
    else
        printf("false");
    return 0;
}

发表于 2024-09-05 16:30:02 回复(0)
C
ezdoes头像 ezdoes
#include <stdio.h>

char sign[3];
float number[4];
float input[4];
char allsign[4] = {'+', '-', '*', '/'};
/*
穷举计算式
*/

float cal(char s, float n1, float n2) {
    switch (s) {
        case '+':
            n1 += n2;
            break;
        case '-':
            n1 -= n2;
            break;
        case '*':
            n1 *= n2;
            break;
        case '/':
            n1 /= n2;
            break;

    }
    return n1;
}
/**
考虑括号，有两种计算方式
*/
float calculate22() {
    return cal(sign[1], cal(sign[0], number[0], number[1]), cal(sign[2], number[2],
               number[3]));
}

float calculate13() {
    return cal(sign[2], cal(sign[1], cal(sign[0], number[0], number[1]), number[2]),
               number[3]);
}

int main() {
    while (scanf("%f %f %f %f", &input[0], &input[1], &input[2],
                 &input[3]) != EOF) {
        int mark = 0;
        /*穷举4个数的顺序和3个符号的顺序*/
        for (int i1 = 0; i1 < 4; i1++) {
            number[0] = input[i1];
            for (int i2 = 0; i2 < 4; i2++) {
                if (i2 != i1) {
                    number[1] = input[i2];
                    for (int i3 = 0; i3 < 4; i3++) {
                        if (i3 != i2 && i3 != i1) {
                            number[2] = input[i3];
                            for (int i4 = 0; i4 < 4; i4++) {
                                if (i4 != i3 && i4 != i2 && i4 != i1) {
                                    number[3] = input[i4];
                                    for (int j1 = 0; j1 < 4; j1++) {
                                        sign[0] = allsign[j1];
                                        for (int j2 = 0; j2 < 4; j2++) {
                                            sign[1] = allsign[j2];
                                            for (int j3 = 0; j3 < 4; j3++) {
                                                sign[2] = allsign[j3];
                                                if (calculate13()==24 || calculate22()==24) {
                                                    mark = 1;
                                                    break;
                                                }
                                            }
                                            if (mark)
                                                break;
                                        }
                                        if (mark)
                                            break;

                                    }
                                    if (mark)
                                        break;
                                }
                            }
                            if (mark)
                                break;
                        }

                    }
                    if (mark)
                        break;
                }

            }
            if (mark)
                break;
        }
        if (mark) {
            printf("true");
       
        }else {
            printf("false");
        }

    }
    return 0;
}
发表于 2023-12-05 15:07:29 回复(0)
C
Jackn头像 Jackn 
#include <stdio.h>
float a[4],flag=0;
int use[4]={0};

void f(float p ,int x){
    if(x==4) {
        if(p==24) flag=1;
        return;
    }
    for(int i=0; i<4 ;i++){
        if(use[i]) continue;
        else {
            use[i]=1;
            f(p+a[i],x+1);
            f(p-a[i],x+1);
            f(p*a[i],x+1);
            if(a[i]) f(p/a[i],x+1);
            f(a[i]-p,x+1);
            if(p)   f(a[i]/p,x+1);    
            use[i]=0;
        }
    }

}
int main() {
    scanf("%f %f %f %f",a,a+1,a+2,a+3);
    for(int i=0 ; i<4 ;i++){
        use[i]=1;
        f(a[i],1);
        use[i]=0;
    }

    if(flag)  printf("true\n");
    else printf("false\n");
    return 0;
递归
发表于 2023-05-04 17:28:38 回复(1)
C
初牛小客头像 初牛小客 
#include <stdio.h>
#include <math.h>
#define MAX 100000000.0

double calculate(double a, double b, int i) //a,b是操作数，与运算符+、-、*、/、结合共有6种情况
{
    double sum[6] = {0};
    sum[0] = a + b;
    sum[1] = a - b;
    sum[2] = b - a;
    if(b != 0.0)
        sum[3] = a / b;
    else
        sum[3] = MAX;
    if(a != 0.0)
        sum[4] = b / a;
    else
        sum[4] = MAX;
    sum[5] = a * b;
    return sum[i]; 
}

int dfs(double a[], int len)
{
    if(len == 1 && fabs(a[0]-24) < 1e-6)
        return 1;
    double b[4] = {0};
    for(int i=0; i<len-1; i++)    //在长度为len的数组里任取两个数计算放入b[0]中，剩下的数字填入b[1]-b[3]里
    {
        for(int j=i+1; j<len; j++)
        {
            for(int k=0; k<6; k++)  //计算有6种组合
            {
                int b_len = 0;
                b[b_len++] = calculate(a[i], a[j], k);    //计算结果放入b[0]中
                for(int p=0; p<len; p++)                         //处理剩下未参与计算的数字
                {
                    if(p != i && p != j)
                        b[b_len++] = a[p];
                }
                if(dfs(b,b_len))
                    return 1;
                memset(b, 0, sizeof(b));
            }
        }
    }
    return 0;
}

int main() {
    double a[4];
    for(int i=0; i<4; i++)
    {
        int temp;
        scanf("%d",&temp);
        a[i] = temp*1.0;
    }
    if(dfs(a,4))
        printf("true");
    else
        printf("false");
    return 0;
}

发表于 2023-03-04 22:30:32 回复(0)
C
已注销头像 已注销 
#include <stdio.h>
#include <math.h>
#define    MAX    10001
int dfs(double num[])
{
    int i,j,k,t=0,cnt=0;
    double a,b;
    for(i=0;i<4;i++)
    {
        if(num[i]!=MAX)
            cnt++;
    }
    if(cnt==1)
    {
        for(i=0;i<4;i++)
        {
            if(num[i]!=MAX)
                if(fabs(num[i]-24)<=1e-6)
                    return 1;
                else
                    return 0;
        }
    }
    else
    {
        for(i=0;i<4;i++)
        {
            if(num[i]!=MAX)
            {
                for(j=0;j<4;j++)
                {
                    if(i==j||num[j]==MAX)
                        continue;
                    a=num[i];
                    b=num[j];
                    
                    num[i]=a+b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                
                    num[i]=a-b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                
                    if(b!=0)
                    {
                        num[i]=a/b;
                        num[j]=MAX;
                        if(dfs(num))
                            return 1;
                        num[i]=a;
                        num[j]=b;
                    }
                
                    num[i]=a*b;
                    num[j]=MAX;
                    if(dfs(num))
                        return 1;
                    num[i]=a;
                    num[j]=b;
                }  
            }

        }
    }
    return 0;
}
int main()
{
    int i,temp;
    double num[4];
    for(i=0;i<4;i++)
    {
        scanf("%d",&temp);
        num[i]=temp*1.0;
    }
    if(dfs(num))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}
只会笨方法
发表于 2022-05-06 17:40:47 回复(1)
C
能不能暂时把你的勇气给我头像 能不能暂时把你的勇气给我
数字允许重复，但每个数字仅允许使用一次
大佬们，这句话如何理解？
发表于 2021-10-17 11:27:47 回复(2)
C
牛客415544593号头像 牛客415544593号 
#include <stdio.h>

int flag=0;

// double n[4] = {0};
// double buf[4] = {0};
// 归的方式，每次只取两个数做加减乘除运算，并放回数组中,直到数据中只剩下一个数，判断这个数是否等于24*/



void is24( double *in, double sum, int step)
{
    double a[3]={0};
    if(flag==1)
        return ;
    else if(step==3)
    {
        if(sum==24)
            flag =1;
        return ;
    }
    else
    {
        step++;
        for(int i=0;i<=4-step;i++)
        {
            for(int j=0;j<=4-step;j++)
            {
                if(i!=j)
                {
                        int cnt = 1;
                        for(int z=0;z<=4-step;z++)
                        {
                            if(z!=i&&z!=j)
                            {
                                a[cnt] = in[z];
                                cnt++;
                            }
                        }
                        a[0] = in[i]+in[j];
                        is24(a,a[0],step);
                        a[0] = in[i]-in[j];
                        is24(a,a[0],step);
                        a[0] = in[i]*in[j];
                        is24(a,a[0],step);
                        a[0] = in[i]/in[j];
                        is24(a,a[0],step);
                    }
                }
            }
        }
}


int main()
{
    double n[4]= {0};
    while(scanf("%lf %lf %lf %lf",&n[0],&n[1],&n[2],&n[3])!=EOF)
    {
//         double input[4];
//         for(int i=0;i<4;i++)
//             input[i] = n[i];
//         int res = 0;
        is24(n,0,0);
        if(flag==1)
            printf("true\n");
        else
            printf("false\n");
        flag=0;
    }
    return 0;
    
}

发表于 2021-08-30 22:39:35 回复(0)
提交观点

问题信息

搜索 dfs
难度：
10条回答 40970浏览

热门推荐

通过挑战的用户

查看代码

相关试题

24点游戏算法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号