首页 > 试题广场 >

24点游戏算法

[编程题]24点游戏算法

热度指数：128405 时间限制：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

算法知识视频讲解

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)

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 回复(0)

初牛小客

#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)

已注销

#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)

能不能暂时把你的勇气给我

数字允许重复，但每个数字仅允许使用一次

大佬们，这句话如何理解？

发表于 2021-10-17 11:27:47 回复(2)

牛客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)