程序实现24点游戏
本帖最后由 LeonSmith123 于 2023-7-23 05:47 编辑逛论坛的时候，突然看到有人用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++，编译的时候需要注意。
下面把我对该帖子中的代码里面的注释贴出来：
#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;
if (n == 1) { //递归的终止条件。即原始输入数的个数为1，且运算结果（对应40行的t，在n=1时为a）为24
if (a == 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（外层多个循环仅表示覆盖多种运算组合）
int f = 0;
for (k = 0; k < n; k++) {
if (a != a && a != a) {
t = a; //t数组的每个位置的数为原始输入数中非a或a的其他数字。
f++;
}
}
t = ys(a, a, i); //t数组的最后一个位置的数为a与a的运算结果
//这一步为递归调用自身，由此使得最终任务不断简化为子任务的多次递归调用
if (guiyi(t, n - 1))
return true;
}
}
}
//如果到达递归终点后仍不能达到24点，则该输入无法进行24点，返回false
return false;
}
int main() {
doublea;
scanf("%lf %lf %lf %lf", &a, &a, &a, &a); //用户原始输入数字，以空格分隔
if (guiyi(a, 4)) //调用递归函数并输出结果
printf("y");
else
printf("n");
}
第二个则更为复杂，因为它完成了对4个数字的24点计算以及打印计算结果。具体原帖中也写的比较清楚了，这里对部分代码进行了修改和注释：
/* 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=='+')||(operators=='-'))
#define MD(x) ((operators=='*')||(operators=='/'))
#define MEMBERS (int)source,operators,(int)source,operators,(int)source,operators,(int)source
#define Input(); input=(float)atoi(argv);\
input=(float)atoi(argv);\
input=(float)atoi(argv);\
input=(float)atoi(argv);
//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={'+','-','*','/'}; //example为四则运算符号
int amounts=9999;
int times=0;
float input={0}; //感觉无用，之后的Input()会进行重新赋值
_Bool state={0}; //state为排列组合时记录的递归情况用的数组，初始各值均为0
float array; //Arrange函数所用，定义数组长度
float source; //source为各种排列组合的情况
char operators={'\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);
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=='/')){
ret=CountParticular(lines,0);
if((ret<24+EPS)&&(ret>24-EPS)){
times++;
if(times<=amounts)
Print(lines,2);
}
}
if((AS(1)||AS(2))||(operators=='/')){
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=example; //设定运算符
Solve(position+1,lines); //递归调用自身
}
return 0;
}
//表示从左到右逐一进行四则运算的方式，返回这样的计算结果
float Count(int lines){
int i=0;
float ret=0;
ret+=source;
for(i=0;i<NUM-1;i++){
calculate(operators,ret,source);
}
return ret;
}
//表示先两头再中间进行四则运算的方式，返回这样的计算结果
float CountSpecial(int lines){
float ret=0;
float result1=0,result2=0;
result1+=source;
calculate(operators,result1,source);
result2+=source;
calculate(operators,result2,source);
ret+=result1;
calculate(operators,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;
calculate(operators,result1,source);
calculate(operators,result1,source);
ret+=source;
calculate(operators,ret,result1);
return ret;
}
if(mode==1){
result1+=source;
calculate(operators,result1,source);
buf=source;
calculate(operators,buf,result1);
result1=buf;
ret+=source;
calculate(operators,ret,result1);
return ret;
}
return ret;
}
//对4个数进行排列组合
void Arrange(int position){
int i=0;
for(i=0;i<NUM;i++){
if(state==0){
state=1;
array=input;
if(position==3){
//去重步骤
Store(array);
state=0;
return;
}
Arrange(position+1);
state=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==source)
repetition++;
if(repetition==4)
return;
}
repetition=0;
}
for(i=0;i<NUM;i++){
source=array;
}
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=='/')){
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=='/')){
printf("%d%c((%d%c%d)%c%d)\n",MEMBERS);
break;
}
if((operators=='/')&&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=='-')&&(AS(2))))&&MD(0)){
printf("%d%c(%d%c(%d%c%d))\n",MEMBERS);
break;
}
if((operators=='/')&&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 于 2023-7-23 13:30 编辑
#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 于 2023-7-23 23:03 编辑
backaxe 发表于 2023-7-23 13:29
#include
int main() {
int num1, num2, num3, num4, sum, result;
没看懂，大佬你的意思是如果输入的4个数的和能写成4个范围为1～6的数的和，并且这4个范围为1～6的数的乘积如果为24，那么输入的4个数就能进行24点？这里面有数学上的证明吗？ 大神，膜拜学习了 这里的牛人太多了 看出来了，第二个的代码逻辑更复杂，不过越简单越好 卧槽 大神 看不懂 有机会学习一下，递归算法确实蛮绕的 wan23 发表于 2023-7-23 10:50
看出来了，第二个的代码逻辑更复杂，不过越简单越好
对的，不过两者完成的事儿还是挺不一样的 第一个算法代码量不大 但是很绕
学习一下