经典游戏--24点--c++代码实现和总体思路（简单暴力向）

24点

　　24点是一个非常经典的游戏，从扑克牌里抽4张牌，其中J=11，Q=12,K=13，然后经过+，-，*，/，（），的计算后，使得计算得值为24，例如抽到1,2,2,5四张牌，那么

　　（1+5）*（2+2）=24；

　　这就是可以凑成24点的一种情况，作为一个经典题目，在leetcode上也有对应的题目进行练习

　　PS　看见知乎大佬有一种必24点的算法，但是要用到阶乘和次方 式子为（a⁰+b⁰+c⁰+d⁰）! =24

一、总体思路

　　1.因为是简单暴力向的，所以我们的做法就是直接穷举出所有可能的情况，首先是考虑四个数a,b,c,d的排列情况

　　　　如b,a,c,d等等，通过排列组合可以得到 4*3*2*1 = 24 种情况

　　2.然后考虑a,b,c,d中的三个运算符的情况设一个自定义的运算符为$,$可以是+,-,*,/中的任意一个

　　　　则有 a$b$c$d 这个式子，同样，运算符的可能性有 3*4 = 12 种

　　3.最后考虑（）的情况，我们规定，每次一对（）只框住两个数，比如a+b+c+d =(((a+b)+c)+d) = ((r1+c)+d)=(r2+d)=r3（其中r1=a+b,r2=r1+c,r3=r2+d)

　　　　（）的情况其实就是运算优先级的问题，无论运算符是什么，都一定是先运算括号里的内容

　　　　所以我们可以穷举出情况

　　　　第一种r1=a$b,r2=r1$c,r3=r2$d;

　　　　第二种r1=b$c,r2=a$r1,r3=r2$d;

　　　　第三种r1=b$c,r2=r1$d,r3=a$r2;

　　　　第四种r1=c$d,r2=b$r1,r3=a$r2;

　　　　第五种r1=a$b,r2=c$d,r3=r1$r2;

　　仔细观察不难发现，我们控制了运算符和数字的绝对顺序从左到右的顺序严格是a$b$c$d,不论任何情况都不会改变abcd的顺序，是因为我们在上面已经排出来了所有的24种情况，所以我们这就可以严格控制abcd的顺序了

二、代码实现

 #include <iostream>
 #include <string>
 using namespace std;
 int mark_int[] = { ,,, };
 string mark_char = "+-*/";
 double cal(double a, int m, double b)
 {
     switch (m)
     {
     case :    return a + b;
     case :    return a - b;
     case :    return a * b;
     case :    return a / b;
     }
 }

 bool cal1(double a, double b, double c, double d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(a, m1, b);
     r2 = cal(r1, m2, c);
     r3 = cal(r2, m3, d);
     if (r3 == )
     {
         cout << "(((" << a << mark_char[m1 - ] << b << ")" << mark_char[m2 - ] << c << ")" << mark_char[m3 - ] << d << ")" << endl;
         return ;
     }
     return ;
 }

 bool cal2(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(b, m1, c);
     r2 = cal(a, m2, r1);
     r3 = cal(r2, m3, d);
     if (r3 == )
     {
         cout << "((" << a << mark_char[m1 - ] << "(" << b << mark_char[m2 - ] << c << "))" << mark_char[m3 - ] << d << ")" << endl;
         return ;
     }
     return ;
 }

 bool cal3(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(b, m1, c);
     r2 = cal(r1, m2, d);
     r3 = cal(a, m3, r2);
     if (r3 == )
     {
         cout << "(" << a << mark_char[m1 - ] << "((" << b << mark_char[m2 - ] << c << ")" << mark_char[m3 - ] << d << "))" << endl;
         return ;
     }
     return ;
 }

 bool cal4(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(c, m1, d);
     r2 = cal(b, m2, r1);
     r3 = cal(a, m3, r2);
     if (r3 == )
     {
         cout << "(" << a << mark_char[m1 - ] << "(" << b << mark_char[m2 - ] << "(" << c << mark_char[m3 - ] << d << ")))" << endl;
         return ;
     }
     return ;
 }

 bool cal5(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(a, m1, b);
     r2 = cal(c, m3, d);
     r3 = cal(r1, m2, r2);
     if (r3 == )
     {
         cout << "((" << a << mark_char[m1 - ] << b << ")" << mark_char[m2 - ] << "(" << c << mark_char[m3 - ] << d << "))" << endl;
         return ;
     }
     return ;
 }

 bool all_cal(int a, int b, int c, int d)
 {
     for (int i = ; i <= ; i++)
         for (int j = ; j <= ; j++)
             for (int k = ; k <= ; k++)
             {
                 if (cal1(a, b, c, d, i, j, k) == true || cal2(a, b, c, d, i, j, k) == true || cal3(a, b, c, d, i, j, k) == true || cal4(a, b, c, d, i, j, k) == true || cal5(a, b, c, d, i, j, k) == true)
                     return ;
             }
     return ;
 }

 bool judge(int a, int b, int c, int d)
 {
     int all[][] = {
         {a,b,c,d},{a,b,d,c},{a,c,b,d},{a,c,d,b},{a,d,b,c},{a,d,c,b},
         {b,a,c,d},{b,a,d,c},{b,c,a,d},{b,c,d,a},{b,d,a,c},{b,d,c,a},
         {c,a,b,d},{c,a,d,b},{c,b,a,d},{c,b,d,a},{c,d,a,b},{c,d,b,a},
         {d,a,b,d},{d,a,d,b},{d,b,a,c},{d,b,c,a},{d,c,a,b},{d,c,b,a},
     };
     for (int i = ; i < ; i++)
     {
         if (all_cal(all[i][], all[i][], all[i][], all[i][]))
             return ;
     }
     return ;
 }

 int main()
 {
     int a, b, c, d;
     cin >> a >> b >> c >> d;
     if (!judge(a, b, c, d))
         cout << "凑不成24点" << endl;

 }

三、代码解释

先做一个计算两个数的函数，用数组int mark_int[4] = {1,2,3,4}的四个数表示+ - * /，string mark_char是用来最后显示的

 int mark_int[] = { ,,, };
 string mark_char = "+-*/";
 double cal(double a, int m, double b)
 {
     switch (m)//用switch来进行运算符的选择
     {
     case :    return a + b;
     case :    return a - b;
     case :    return a * b;
     case :    return a / b;
     }
 }

我们在实现五种括号的函数，并且我们规定运算一定是 a m1 b m2 c m3 d(m1,m2,m3是三个运算符的代号），如果成功返回运算的过程和true，否则返回false

 bool cal1(double a, double b, double c, double d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(a, m1, b);
     r2 = cal(r1, m2, c);
     r3 = cal(r2, m3, d);
     if (r3 == )
     {
         cout << "(((" << a << mark_char[m1 - ] << b << ")" << mark_char[m2 - ] << c << ")" << mark_char[m3 - ] << d << ")" << endl;
         return ;
     }
     return ;
 }//第一种r1=a$b,r2=r1$c,r3=r2$d;

 bool cal2(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(b, m1, c);
     r2 = cal(a, m2, r1);
     r3 = cal(r2, m3, d);
     if (r3 == )
     {
         cout << "((" << a << mark_char[m1 - ] << "(" << b << mark_char[m2 - ] << c << "))" << mark_char[m3 - ] << d << ")" << endl;
         return ;
     }
     return ;
 }//第二种r1=b$c,r2=a$r1,r3=r2$d;

 bool cal3(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(b, m1, c);
     r2 = cal(r1, m2, d);
     r3 = cal(a, m3, r2);
     if (r3 == )
     {
         cout << "(" << a << mark_char[m1 - ] << "((" << b << mark_char[m2 - ] << c << ")" << mark_char[m3 - ] << d << "))" << endl;
         return ;
     }
     return ;
 }//第三种r1=b$c,r2=r1$d,r3=a$r2;

 bool cal4(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(c, m1, d);
     r2 = cal(b, m2, r1);
     r3 = cal(a, m3, r2);
     if (r3 == )
     {
         cout << "(" << a << mark_char[m1 - ] << "(" << b << mark_char[m2 - ] << "(" << c << mark_char[m3 - ] << d << ")))" << endl;
         return ;
     }
     return ;
 }//第四种r1=c$d,r2=b$r1,r3=a$r2;

 bool cal5(int a, int b, int c, int d, int m1, int m2, int m3)
 {
     double r1;
     double r2;
     double r3;
     r1 = cal(a, m1, b);
     r2 = cal(c, m3, d);
     r3 = cal(r1, m2, r2);
     if (r3 == )
     {
         cout << "((" << a << mark_char[m1 - ] << b << ")" << mark_char[m2 - ] << "(" << c << mark_char[m3 - ] << d << "))" << endl;
         return ;
     }
     return ;
 }//第五种r1=a$b,r2=c$d,r3=r1$r2;

接下来是12种的符号的排列情况，如果有一种括号情况满足，我们就返回true，否则返回false

 bool all_cal(int a, int b, int c, int d)
 {
     for (int i = ; i <= ; i++)
         for (int j = ; j <= ; j++)
             for (int k = ; k <= ; k++)
             {
                 if (cal1(a, b, c, d, i, j, k) == true || cal2(a, b, c, d, i, j, k) == true || cal3(a, b, c, d, i, j, k) == true || cal4(a, b, c, d, i, j, k) == true || cal5(a, b, c, d, i, j, k) == true)
                     return ;
             }
     return ;
 }

最后是在总判断函数中写入24种的abcd排列情况

 bool judge(int a, int b, int c, int d)
 {
     int all[][] = {
         {a,b,c,d},{a,b,d,c},{a,c,b,d},{a,c,d,b},{a,d,b,c},{a,d,c,b},
         {b,a,c,d},{b,a,d,c},{b,c,a,d},{b,c,d,a},{b,d,a,c},{b,d,c,a},
         {c,a,b,d},{c,a,d,b},{c,b,a,d},{c,b,d,a},{c,d,a,b},{c,d,b,a},
         {d,a,b,d},{d,a,d,b},{d,b,a,c},{d,b,c,a},{d,c,a,b},{d,c,b,a},
     };
     for (int i = ; i < ; i++)
     {
         if (all_cal(all[i][], all[i][], all[i][], all[i][]))
             return ;
     }
     return ;
 }

主函数调用judge就完成整个算法了✿✿ヽ(°▽°)ノ✿

 int main()
 {
     int a, b, c, d;
     cin >> a >> b >> c >> d;
     if (!judge(a, b, c, d))
         cout << "凑不成24点" << endl;

 }

失败的话会显示“凑不成24点”

其实这个算法的话我写的可以说基本没有优化，就是枚举所有情况实现的，****上有大佬是有更好的思路的，这篇文章也是看了****的大佬的代码然后自己修修补补写出来的（我原来看的那篇有bug，大佬自己没发现好像。。。）

就酱

睡觉！