程序实现24点游戏

LeonSmith123

逛论坛的时候，突然看到有人用C写了24点游戏代码：论坛上24点游戏帖子https://www.52pojie.cn//thread-1768220-1-1.html
不过比较可惜的是，该代码并不能实现24点游戏，甚至还有语法错误
这就让我去网上查了一下有没有相关代码，找到了以下两个。先贴原链接：
递归实现判断能否实现24点https://blog.csdn.net/weixin_65089713/article/details/123818760
输出4个数字的24点运算结果https://zhuanlan.zhihu.com/p/544523603
先说第一个，其实该代码实现的是一个判断某些数字是否能实现24点运算，是则输出y，不是则输出n。里面的算法原理其实讲的蛮清楚，概括来说就是每次递归视作调用当前步去掉一个数字的24点运算，其中去掉的数字其实是当前步所有2个数字组合的运算结果。不过原帖子里面写错了，该代码源码为C++，编译的时候需要注意。
下面把我对该帖子中的代码里面的注释贴出来：

[C++] 纯文本查看 复制代码

#include <stdio.h>
 
double ys(double a, double b, int n) {
        double c;
        if (n == 1)
                c = a * b;
        if (n == 2)
                c = a / b;
        if (n == 3)
                c = a + b;
        if (n == 4)
                c = a - b;
        if (n == 5)
                c = b - a;
        if (n == 6)
                c = b / a;
        return c;
}
 
//递归函数定义
bool guiyi(double a[], int n) { //a代表原始输入的n个数
        int i, b, c, k;
        double t[4];
        if (n == 1) { //递归的终止条件。即原始输入数的个数为1，且运算结果（对应40行的t[f]，在n=1时为a[0]）为24
                if (a[0] == 24) 
                        return true;
                else
                        return false;
        }
        for (i = 1; i < 7; i++) { //i代表6种运算
                for (b = 0; b < n - 1; b++) { //b代表原始输入数中第一个用于运算的数的索引
                        for (c = b + 1; c < n; c++) { //c代表原始输入数中第二个用于运算的数的索引
                                //这一步用于构建递归中每个子任务的输入。程序记作t[f]（外层多个循环仅表示覆盖多种运算组合）
                                int f = 0; 
                                for (k = 0; k < n; k++) {
                                        if (a[k] != a[b] && a[k] != a[c]) {
                                                t[f] = a[k]; //t数组的每个位置的数为原始输入数中非a[b]或a[c]的其他数字。
                                                f++;
                                        }
                                }
                                t[f] = ys(a[b], a[c], i); //t数组的最后一个位置的数为a[b]与a[c]的运算结果
                                //这一步为递归调用自身，由此使得最终任务不断简化为子任务的多次递归调用
                                if (guiyi(t, n - 1))
                                        return true;
                        }
                }
        }
        //如果到达递归终点后仍不能达到24点，则该输入无法进行24点，返回false
        return false;
}
 
int main() {
        double  a[4];
        scanf("%lf %lf %lf %lf", &a[0], &a[1], &a[2], &a[3]); //用户原始输入数字，以空格分隔
        if (guiyi(a, 4)) //调用递归函数并输出结果
                printf("y");
        else
                printf("n");
}

第二个则更为复杂，因为它完成了对4个数字的24点计算以及打印计算结果。具体原帖中也写的比较清楚了，这里对部分代码进行了修改和注释：

[C] 纯文本查看 复制代码

/* tf */
/* Written By GoogleChen on 2022/7/7 */
/* Modified By LeonSmith123 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define NUM 4
#define MAX 24
#define EPS 0.001
#define AS(x) ((operators[x]=='+')||(operators[x]=='-'))
#define MD(x) ((operators[x]=='*')||(operators[x]=='/'))
#define MEMBERS (int)source[lines][0],operators[0],(int)source[lines][1],operators[1],(int)source[lines][2],operators[2],(int)source[lines][3]
#define Input(); input[0]=(float)atoi(argv[1]);\
input[1]=(float)atoi(argv[2]);\
input[2]=(float)atoi(argv[3]);\
input[3]=(float)atoi(argv[4]);
//calculate定义四则运算
#define calculate(a,b,c); \
switch(a){\
    case '+':\
        b+=c;\
        break;\
    case '-':\
        b-=c;\
        break;\
    case '*':\
        b*=c;\
        break;\
    case '/':\
        b/=c;\
        break;\
    default:\
        break;\
}

float Count(int lines);
float CountSpecial(int lines);
float CountParticular(int lines,int mode);
int Solve(int position,int lines);
void Arrange(int position);
void Print(int lines,int mode);
void Store(float *array);

char example[NUM]={'+','-','*','/'}; //example为四则运算符号
int amounts=9999;
int times=0;
float input[NUM]={0}; //感觉无用，之后的Input()会进行重新赋值
_Bool state[NUM]={0}; //state为排列组合时记录的递归情况用的数组，初始各值均为0
float array[NUM]; //Arrange函数所用，定义数组长度
float source[MAX][NUM]; //source为各种排列组合的情况
char operators[NUM-1]={'\0'};
int lines=0; //lines为4个数可能的排列组合数目，最大为4*3*2*1=24种

int main(int argc, const char * argv[]) {
    int i=0;
    if(argc<5){
        printf("Too few arguments!\n");
        printf("Usage: tf number1 number2 number3 number4 [-amounts| ]\n");
        return 0;
    }
    Input(); //赋值input数组为用户输入的4个数
    if(argc==6)
        amounts=atoi(argv[5]);
    Arrange(0); 
    for(;i<lines;i++){ //排列组合（Arrange）后得到了lines值
        Solve(0,i);
    }
    printf("--END--\n");
    return 0;
}

int Solve(int position,int lines){
    int i=0;
    float ret=0;
    if(position==3){ //递归终止条件，
        //Count方式得到的结果ret
        ret=Count(lines);
        if((ret<24+EPS)&&(ret>24-EPS)){ //判断是否结果为24周围，是则输出结果，后同
            times++;
            if(times<=amounts)
                Print(lines,0);
        }
        //CountSpecial方式得到的结果ret
        if(MD(1)){
            ret=CountSpecial(lines);
            if((ret<24+EPS)&&(ret>24-EPS)){
                times++;
                if(times<=amounts)
                    Print(lines,1);
            }
        }
        //CountParticular方式得到的结果ret
        if(MD(0)){
            if((AS(1)||AS(2))||(operators[0]=='/')){
                ret=CountParticular(lines,0);
                if((ret<24+EPS)&&(ret>24-EPS)){
                    times++;
                    if(times<=amounts)
                        Print(lines,2);
                }
            }
            if((AS(1)||AS(2))||(operators[0]=='/')){
                ret=CountParticular(lines,1);
                if((ret<24+EPS)&&(ret>24-EPS)){
                    times++;
                    if(times<=amounts)
                        Print(lines,3);
                }
            }
        }
        return 0;
    }
    for(i=0;i<NUM;i++){
        operators[position]=example[i]; //设定运算符
        Solve(position+1,lines); //递归调用自身
    }
    return 0;
}

//表示从左到右逐一进行四则运算的方式，返回这样的计算结果
float Count(int lines){
    int i=0;
    float ret=0;
    ret+=source[lines][0];
    for(i=0;i<NUM-1;i++){
        calculate(operators[i],ret,source[lines][i+1]);
    }
    return ret;
}

//表示先两头再中间进行四则运算的方式，返回这样的计算结果
float CountSpecial(int lines){
    float ret=0;
    float result1=0,result2=0;
    result1+=source[lines][0];
    calculate(operators[0],result1,source[lines][1]);
    result2+=source[lines][2];
    calculate(operators[2],result2,source[lines][3]);
    ret+=result1;
    calculate(operators[1],ret,result2);
    return ret;
}

//mode1为先中间二位，再与第四位运算，然后第一位进行四则运算的方式；
//mode2为先后二位，再与第二位运算，然后第一位进行四则运算的方式。返回这样的计算结果
float CountParticular(int lines,int mode){
    float ret=0;
    float result1=0;
    float buf=0;
    if(mode==0){
        result1+=source[lines][1];
        calculate(operators[1],result1,source[lines][2]);
        calculate(operators[2],result1,source[lines][3]);
        ret+=source[lines][0];
        calculate(operators[0],ret,result1);
        return ret;
    }
    if(mode==1){
        result1+=source[lines][2];
        calculate(operators[2],result1,source[lines][3]);
        buf=source[lines][1];
        calculate(operators[1],buf,result1);
        result1=buf;
        ret+=source[lines][0];
        calculate(operators[0],ret,result1);
        return ret;
    }
    return ret;
}

//对4个数进行排列组合
void Arrange(int position){
    int i=0;
    for(i=0;i<NUM;i++){
        if(state[i]==0){
            state[i]=1;
            array[position]=input[i];
            if(position==3){
                //去重步骤
                Store(array);
                state[i]=0;
                return;
            }
            Arrange(position+1);
            state[i]=0;
        }
    }
}

//对所有排列组合的情况进行去重
void Store(float *array){
    int j=0;
    int i=0;
    int repetition=0;
    for(i=0;i<lines;i++){
        for(j=0;j<NUM;j++){
            if(array[j]==source[i][j])
                repetition++;
            if(repetition==4)
               return;
        }
        repetition=0;
    }
    for(i=0;i<NUM;i++){
        source[lines][i]=array[i];
    }
    lines++;
}

//根据计算方式打印计算24点的结果
void Print(int lines,int mode){
    switch(mode){
        case 0:
            if((!MD(1))&&(!MD(2)))
                printf("%d%c%d%c%d%c%d\n",MEMBERS);
            if(AS(0)&&(MD(1))){
                printf("(%d%c%d)%c%d%c%d\n",MEMBERS);
                break;
            }
            if((AS(0)||AS(1))&&(MD(2)))
                printf("(%d%c%d%c%d)%c%d\n",MEMBERS);
            break;
        case 1:
            if((AS(0)&&AS(2))||(operators[1]=='/')){
                printf("(%d%c%d)%c(%d%c%d)\n",MEMBERS);
                break;
            }
            if(AS(0)){
                printf("(%d%c%d)%c%d%c%d\n",MEMBERS);
                break;
            }
            if(AS(2))
                printf("%d%c%d%c(%d%c%d)\n",MEMBERS);
            break;
        case 2:
            if((AS(1)&&MD(2))&&(operators[0]=='/')){
                printf("%d%c((%d%c%d)%c%d)\n",MEMBERS);
                break;
            }
            if((operators[0]=='/')&&MD(1)&&(MD(2))){
                printf("%d%c((%d%c%d)%c%d)\n",MEMBERS);
                break;
            }
            if(AS(1)&&MD(2)){
                printf("%d%c(%d%c%d)%c%d\n",MEMBERS);
                break;
            }
            if(MD(0))
               printf("%d%c(%d%c%d%c%d)\n",MEMBERS);
            break;
        case 3:
            if((AS(2)&&(MD(1))||((operators[1]=='-')&&(AS(2))))&&MD(0)){
                printf("%d%c(%d%c(%d%c%d))\n",MEMBERS);
                break;
            }
            if((operators[0]=='/')&&MD(1)&&(MD(2))){
                printf("%d%c(%d%c(%d%c%d))\n",MEMBERS);
                break;
            }
            if(MD(0))
                printf("%d%c(%d%c%d%c%d)\n",MEMBERS);
            break;
        default:break;
    }
}

虽然根据原作者的说法，Store函数会去掉重复输出的结果，但是程序在实际运行时候，还是发现了重复的结果，如图所示：

可以看出，该程序有可以优化的地方。不知道有没有大佬能够不吝赐教呀，小白在此多谢啦！


之后有时间可以再思考以下问题：
1. 两种方法递归算法的时间复杂度如何？
2. 两种方法所用的递归搜索方法分别是什么？
3. 对第二个方法中的代码进行进一步注释，毕竟Arrange和Solve函数所用的递归的算法还是比较难以理解（小白一枚，见谅！）

backaxe

[C] 纯文本查看 复制代码

#include <stdio.h>
int main() {    
   int num1, num2, num3, num4, sum, result;    
   printf("请输入四个数字，用空格隔开：");    
   scanf("%d %d %d %d", &num1, &num2, &num3, &num4);
   sum = num1 + num2 + num3 + num4;    
   result = calculate24(sum);  
   if (result == 24) {    
       printf("Y\n");    
   } else {    
       printf("N\n");    
   }
   return 0;    
}
int calculate24(int num) {    
   int result = 0;    
   for (int i = 1; i <= 6; i++) {    
       for (int j = 1; j <= 6; j++) {    
           for (int k = 1; k <= 6; k++) {    
               for (int l = 1; l <= 6; l++) {    
                   if (i + j + k + l == num) {    
                       result = i * j * k * l;    
                       break;    
                   }    
               }    
           }    
       }    
   }    
   return result;    
}

LeonSmith123

backaxe 发表于 2023-7-23 13:29
[mw_shl_code=c,true]#include
int main() {   
   int num1, num2, num3, num4, sum, result;   

没看懂，大佬你的意思是如果输入的4个数的和能写成4个范围为1～6的数的和，并且这4个范围为1～6的数的乘积如果为24，那么输入的4个数就能进行24点？这里面有数学上的证明吗？

good7801

大神，膜拜学习了

laoyehuamao

这里的牛人太多了

wan23

看出来了，第二个的代码逻辑更复杂，不过越简单越好

viking1998

卧槽 大神 看不懂

LeonSmith153

有机会学习一下，递归算法确实蛮绕的

LeonSmith123

wan23 发表于 2023-7-23 10:50
看出来了，第二个的代码逻辑更复杂，不过越简单越好

对的，不过两者完成的事儿还是挺不一样的

FZC

第一个算法代码量不大 但是很绕

zp820710

学习一下