C++ HOJ 24点

桃扇骨 2022-08-02 12:51 200阅读 0赞

【问题描述】

用4张扑克牌上的点数算24点是一个经典的游戏了。一般要求只允许使用加减乘除和括号进行四则运算。  
例如：1,2,3,4 可以用表达式（1+2+3）\*4 = 24 算出24。

要求计算出有多少种实现方法并输出全部实现方式。

【思路一】

基本原理是穷举4个整数所有可能的表达式，然后对表达式求值。  
表达式的定义： expression = (expression|number) operator (expression|number)  
因为能使用的4种运算符 + - \* / 都是2元运算符，所以本文中只考虑2元运算符。2元运算符接收两个参数，输出计算结果，输出的结果参与后续的计算。  
由上所述，构造所有可能的表达式的算法如下：  
　　(1) 将4个整数放入数组中  
　　(2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列，  
　　(2.1) 对 + - \* / 每一个运算符，  
　　(2.1.1) 根据此排列的两个数字和运算符，计算结果  
　　(2.1.2) 改表数组：将此排列的两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中  
　　(2.1.3) 对新的数组，重复步骤 2  
　　(2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉  
　　可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。  
　　在程序中，一定要注意递归的现场保护和恢复，也就是递归调用之前与之后，现场状态应该保持一致。在上述算法中，递归现场就是指数组，2.1.2 改变数组以进行下一层递归调用，2.1.3 则恢复数组，以确保当前递归调用获得下一个正确的排列。  
　　括号 () 的作用只是改变运算符的优先级，也就是运算符的计算顺序。所以在以上算法中，无需考虑括号。括号只是在输出时需加以考虑。

#include<cstdio>    
    #include<iostream>    
    #include <cmath>    
    using namespace std;    
    //+-*/   1234    
    unsigned long int xx[1001];    
    int x=1;    
    int pd;    
    int f1(int a, int b, int c, int d)    
    {    
        int sum;    
        pd=0;    
        char s1,s2,s3;    
        for (int j = 1; j <= 4; j++)    
        {    
            for (int k = 1; k <= 4; k++)    
            {    
                for (int l = 1; l <= 4; l++)    
                {    
                    sum = 0;    
                    sum += a;    
                    switch (j)    
                    {    
                    case 1:sum += b; break;    
                    case 2:sum -= b; break;    
                    case 3:sum *= b; break;    
                    case 4:    
                        {    
                            if (sum%b)    
                            {    
                                sum = 9999;    
                            }    
                            else    
                            {    
                                sum /= b;    
                            }    
                        }break;    
                    default:    
                        break;    
                    }    
                    switch (k)    
                    {    
                    case 1:sum += c; break;    
                    case 2:sum -= c; break;    
                    case 3:sum *= c; break;    
                    case 4:    
                        {    
                            if (sum%c)    
                            {    
                                sum = 9999;    
                            }    
                            else    
                            {    
                                sum /= c;    
                            }    
                        }break;    
                    default:    
                        break;    
                    }    
                    switch (l)    
                    {    
                    case 1:sum += d; break;    
                    case 2:sum -= d; break;    
                    case 3:sum *= d; break;    
                    case 4:    
                        {    
                            if (sum%d)    
                            {    
                                sum = 9999;    
                            }    
                            else    
                            {    
                                sum /= d;    
                            }    
                        }break;    
                    default:    
                        break;    
                    }    
                    switch (j)    
                    {    
                    case 1:s1='+';break;    
                    case 2:s1='-';break;    
                    case 3:s1='*';break;    
                    case 4:s1='/';break;    
                    }    
                    switch (k)    
                    {    
                    case 1:s2='+';break;    
                    case 2:s2='-';break;    
                    case 3:s2='*';break;    
                    case 4:s2='/';break;    
                    }    
                    switch (l)    
                    {    
                    case 1:s3='+';break;    
                    case 2:s3='-';break;    
                    case 3:s3='*';break;    
                    case 4:s3='/';break;    
                    }    
                    if (sum == 24)    
                    {    
                        if (x==0)    
                        {    
                            xx[x]=a*1000000+b*100000+c*10000+d*1000+j*100+k*10+l;    
                            x++;    
                            printf("((%d%c%d)%c%d)%c%d==24\n",a,s1,b,s2,c,s3,d);    
                        }    
                        else    
                        {    
                            for (int i=1;i<=x;i++)    
                            {    
                                if ((a*1000000+b*100000+c*10000+d*1000+j*100+k*10+l)==xx[i])    
                                {    
                                    pd=1;    
                                    break;    
                                }    
                            }    
                            if (pd==0)    
                            {    
                                xx[x]=a*1000000+b*100000+c*10000+d*1000+j*100+k*10+l;    
                                x++;    
                                printf("((%d%c%d)%c%d)%c%d==24\n",a,s1,b,s2,c,s3,d);    
                            }    
                        }    
                        return 1;    
                    }    
                }    
            }    
        }    
        return 0;    
    }    
    int f2(int a, int b, int c, int d)    
    {    
        int sum = 0;    
        sum = f1(a, b, c, d) + f1(a, b, d, c) + f1(a, c, b, d) + f1(a, c, d, b) + f1(a, d, b, c) + f1(a, d, c, b);    
        if (sum != 0)    
        {    
            return 1;    
        }    
        else    
        {    
            return 0;    
        }    
    }    
    int main()    
    {    
        int a, b, c, d;    
        int sum;    
        cin >> a >> b >> c >> d;    
        sum = f2(a, b, c, d) + f2(b, a, c, d) + f2(c, a, b, d) + f2(d, a, b, c);    
        if (sum == 0)    
        {    
            cout << 'N' << endl;    
        }    
        return 0;    
    }

【思路二】  
递归方式  
4个数字中任取2个数，使用一种运算得到一个数，将这个数和另外两个没有参与运算的数放在一起，这3个数再任取2个数进行运算，得到的结果再与另外一个数放在一起。最后这两个数再进行运算，看结果是不是24，如果是，我们就找到了一个满足要求的表达式了。根据这个思路，我们可以写递归函数如下：

RecursiveCalc（数组，数组长度 )

> 取数组中2个数计算，和另外的数 组成新的数组

> 递归调用RecursiveCalc（新数组，数组长度-1 )

递归到数组长度=1时结束，此时只需要看数组中元素是否=24，就可以知道这一次运算是否满足要求。  
  
递归的原理是比较简单的，但是里面一些细节需要注意：

> 1. 取出来做运算的2个数应该是不同位置的两个数，例如我们在1,2,3,4中取了3，另外一个数就不能取3了。
> 
> 2. 组成新数组的时候也要注意，是和没有参与运算的数组成新的数组。
> 
> 3. 如果遇到了除法，要小心被除数=0的情况。
> 
> 4. 因为除法可能会产生分数，所以运算中要采用浮点数，不能用整数。例如1,5,5,5 计算24点的表达式为（5 - 1/5)\*5关于处理分数的情况，还有一种方法是自己实现分数类，所有的数都用分数类对象表示。
> 
> 5. 递归方式的打印输出很麻烦，因为到最后一个数是24的时候，你并不知道这个24是通过怎样的运算步骤得到的，所以需要保存中间运算步骤，以便最后的结果输出。

在我实现的代码中，递归的输出部分也是写的比较垃圾，比较好的方式是每个数字都是一个对象的成员，参数用对象来传递，对象中保留表达式。

bool RecursiveCalc(double *pArray, int nCount)  
    {  
        bool bRet = false;  
        if (1 == nCount)  
        {  
            if (fabs(pArray[0] - 24.0) < 0.0001)  
            {  
                g_Total++;  
                Output(pArray[0]);  
                return true;  
            }  
            else  
                return false;  
        }  
        for (int i = 0; i < nCount; i++)  
        {  
            for (int j = 0; j < nCount; j++)  
            {  
                if (j == i)  
                {  
                    continue;  
                }  
                double f1 = pArray[i];  
                double f2 = pArray[j];  
                char *p = g_op;  
                for (int nop = 1; nop <= 4; nop++, p++)  
                {   
                    if ('/' == *p && fabs(f2) < 0.0001)  
                    {   
                        continue;  
                    }  
                    double f = Operation(f1, f2, *p);  
                    double *pnew = new double[nCount-1];  
                    if (!pnew)  
                    {  
                        return bRet;  
                    }  
                    pnew[0] = f;  
                    for (int m = 1, n = 0; m < nCount-1; m++)  
                    {   
                        while (n == i || n == j)  
                        {  
                            n++;  
                        }  
                        pnew[m] = pArray[n++];  
                    }  
                    bRet |= RecursiveCalc(pnew, nCount-1);  
                    g_n2--;  
                    g_n1 -= 2;  
                    delete pnew;  
                    if (g_bOnlyGetOne && bRet)  
                    {  
                        return true;  
                    }  
                }  
            }  
        }  
        return bRet;  
    }

递归方式的次数分析  
在不考虑加法和乘法的交换律的情况下，对于给定的4个数字的递归算法有以下排列：  
4个数中取2个数的排列 12种 \*4种运算符 = 48种  
3个数中取2个数的排列 6种 \*4种运算符 = 24种  
2个数中取2个数的排列 2种 \*4种运算符 = 8种  
所以共有48\*24\*8种 = 9216种情况  
【思路三】  
后缀表达式方法  
后缀表达式又称为逆波兰表达式，是一种把运算符放在要运算的两个数值后面的一种表示方法，后缀表达式的好处是可以不用括号。  
例如对于（1-2）/(3-4)这样的表达式，后缀表示法为：12-34-/，在解释后缀表达式时，我们从左到右扫描，遇到运算符就往运算符的左边取最近的两个数值进行运算，运算结束后将这个运算符和对应的两个运算数替换为运算结果，然后重复这个过程，直到算出最终结果。  
例如对于3 ,6 5 - 8 + \* 这个表达式，我们可以这样计算：  
遇到数字先不管，遇到第一个符号是减号，往前找两个数，是6和5，所以就是6-5，结果=1。用1替换掉6 5 - 得到新的表达式：  
3 1 8 + \* 接下来是加号，1+8 = 9，表达式变为：3 9 \*  
最后的结果就是3\*9 = 27。  
而原来的表达式转换为我们平时看到的中缀表示法就是：3\*（6-5+8），可以看出后缀表达式避免了括号。  
关于这种表达式的更详细说明，读者可以搜索相关介绍。  
将后缀表达式看成栈操作是很多教科书和文章中都提到的一种理解方式，其中向栈中加入数值时不进行任何处理，向栈中加入运算符则取栈顶的2个操作数和运算符进行运算，运算结果再放回栈中，所以每加入一个运算符，相当于栈中数值的数量会减少1，这一点从上面的图中也能看出来，每经过一个运算符，后面括号中的数值都比父节点小1。而每加入一个数值，后面括号中的数值都比父节点多1。

针对4个数字的计算，数值用a表示，符号用+表示，可以得到如下排列：  
aaaa+++  
aaa+a++  
aaa++a+  
aa+aa++  
aa+a+a+  
接下来我们只需要对4个数进行全排列，和对3个符号进行所有的组合，就可以无遗漏的计算所有可能情况。采用后缀表达式需要实现4个数字的全排列，关于全排列又分为有序全排列和无序全排列，在我们这里两种方式都可以。我的代码中对这两种方式都进行了实现。其中，字典序（有序）全排列思路参考：

http://blog.csdn.net/visame/article/details/2455396  
其实，在STL的算法函数库中有字典序全排列的函数可以用，在“algorithm”文件里面定义了next\_permutation函数和prev\_permutation函数，分别表示求有序全排列的下一个排列和上一个排列。其中的思路和所给链接中思路一样。非有序全排列的方法也比较多，网上有很多介绍，我使用的是这篇文章介绍的一种很有趣的方法（进位不同数）：

http://llfclz.itpub.net/post/1160/278490  
有序全排列代码如下：

void SetNextSortPermutation(int *pIdx, int nLen)//调整到有序全排列的下一个排列  
    {  
        int nCurIdx = nLen-1;  
        int nFindIdx = nCurIdx;  
        while (nCurIdx-1 >= 0 && pIdx[nCurIdx-1] > pIdx[nCurIdx])  
        {  
            nCurIdx--;  
        }  
        if (nCurIdx-1 < 0)  
        {  
            return;  
        }  
        while (pIdx[nFindIdx] < pIdx[nCurIdx-1])  
        {  
            nFindIdx--;  
        }  
        int tmp = pIdx[nCurIdx-1];  
        pIdx[nCurIdx-1] = pIdx[nFindIdx];  
        pIdx[nFindIdx] = tmp;  
        for (int i = nCurIdx, j = nLen-1; i < j; i++, j--)  
        {  
            tmp = pIdx[i];  
            pIdx[i] = pIdx[j];  
            pIdx[j] = tmp;  
        }  
    }

调整到运算符的下一个排列的算法类似四则运算中的进位处理，我们定义运算符的顺序是+-\*/。则+++的下一个排列是++-，只需要将最后一个符号（+1）变成下一个符号，如果符号越界了，比如++/，最后一个符号是除法，加1，就需要回到加号，同时对前面的符号进行进位，在进位的过程中可能产生循环进位，所以要循环处理。++/（加加除）的下一个排列是+-+，+//（加除除）的下一个排列是-++（减加加）。对应的代码如下：

void SetNextOpComb(int *nOp, int nLen)//调整到运算符组合的下一个组合，类似运算中的进位处理  
    {  
        int nCurIdx = nLen-1;  
        while (nCurIdx >= 0 && 4 == ++nOp[nCurIdx])  
        {  
            nOp[nCurIdx] = 0;  
            nCurIdx--;  
        }  
    }

具体的模拟栈操作中，我定义了一个结点结构表示数值或者符号：

struct Node  
    {  
        int nType;  
        union  
        {  
            double d;  
            int op;  
        };  
    };

在实际的代码中使用list，只操作list的尾部来模拟栈。代码如下：

bool CalcStack(Node *node_all, int nLen)  
    {  
        std::list<Node> lst;  
        Node node;  
        char output[200] = {0};  
        char tmp[30] = {0};  
        for (int i = 0; i < nLen; i++)  
        {  
            if (0 == node_all[i].nType)  
            {  
                lst.push_back(node_all[i]);  
                sprintf_s(tmp, 30, "%2d ", (int)node_all[i].d);  
                strcat_s(output, 200, tmp);  
            }  
            else if(1 == node_all[i].nType)  
            {  
                sprintf_s(tmp, 30, "%c ", g_op[node_all[i].op]);  
                strcat_s(output, 200, tmp);  
                Node f2 = lst.back();  
                lst.pop_back();  
                Node f1 = lst.back();  
                lst.pop_back();  
                if (abs(f2.d) < 0.0001 && 3 == node_all[i].op)  
                {  
                    return false;  
                }  
                node.nType = 0;  
                node.d = Operation(f1.d, f2.d, g_op[node_all[i].op]);  
                lst.push_back(node);  
            }  
            else  
                assert(0);  
        }  
        double f = lst.back().d;  
        if (abs(f-24.0) < 0.0001)  
        {  
            g_Total++;  
            printf("%s=%d\r\n", output, (int)f);  
            return true;  
        }  
        return false;  
    }

后缀表达式方法共有5种合法的后缀表达式,假设abcd为4个数，+代表符号  
第一种: abcd+++  
第二种: abc+d++  
第三种: ab+cd++  
第四种: abc++d+  
第五种: ab+c+d+  
对于每种情况，4个数字的全排列=24，3个符号的可能性是4\*4\*4，所以每种情况有24\*64=1536种  
5种情况 共1536\*5 = 7680 种排列  
虽然从数据比较上来看，后缀表达式方式的情况比递归法的少，但由于我在代码中用到了list来模拟栈，所以实际代码运行的效率，递归法反而比后缀表达式方法更快，消耗的时间大约只有后缀表达式方法的1/10。也就是低一个数量级。  
  
【题解小结】  
相对于直接玩扑克牌软件形式的计算24点游戏，有的软件对每道题目仅提供一个答案，而不管实际的解法有多少种。而有的版本刚好相反，提供了答案的所有排列方式。这意味着，对于1、2、3、4这四个数，尽管只有1×2×3×4一种解法，而列出的答案包含4×3×2×1、2×1×4×3等多达24种！  
一方面，如果有多种计算方式，我们应该提供所有答案，而不仅是其中一个答案；另一方面，我们应该避免重复提供相同答案的不同形式。给出所有答案是比较容易的，这里我们只讨论如何避免重复提供相同答案的不同形式。比如1、1、3、8这四个数，1×1×3×8与8×3×1×1应该等效的，答案中只需提供其中一个。那么如何认定两个式子是等效的呢？

如果其中一个式子能通过若干次加法交换律和乘法交换律转换为另一个式子，则认为是等效的。

因此1×1×3×8与8×3×1×1、1×3×1×8、1×8×3×1都是等效的，但与1－1＋3×8不是等效的。

减法、除法按与加法、乘法相似的方式处理，这样5+10×2－1与5－1＋2×10，5×10÷2－1与10÷2×5－1分别也是等效的。  
在明确等效规则后，还需要解决随之而来的两个问题：程序如果根据该规则对两个式子进行比较呢？软件应该选择哪一个式子作为提供给用户的标准答案呢？这两个问题可以用同一种方案解决，那就是建立一个排序规则，被比较的式子都按该排序规则使用加法交换律和乘法交换律进行转换，直到演化为一个“标准”的式子，最后看得到的结果是否一样。而提供给用户的答案，就是这个“标准”的式子。  
怎样才算“标准”的式子呢？对用户而言，标准的式子应该比非标准的式子更自然。从小到大，先加后减，先乘后除符合大多数人的视觉习惯。在加法、乘法式子中，总是值小的数或式子的在前。即6×4经排序后得到4×6，3×6＋3×2经排序后得到2×3＋3×6。对于减法和除法，先减去或除以较小的值或式子。加法和减法一起时，先执行加法。乘法和除法一起时，先执行乘法。这样5－1＋10×2经排序后得到5＋2×10－1，（5－1＋4）×3经排序后变成3×（4＋5－1）。  
需要指出的是，这个书写最自然的式子不一定是常人做题时最容易想到的式子。小的数字计算起来更方便，小的中间结果对后面的步骤更有利。在上面的例子1、2、5、10中，5－1＋2×10可能比5＋2×10－1更容易想到。另外对不少人来说，把最难的运算放在第一步更能使自己确信找到了答案，给出的答案最有可能是2×10＋（5－1）。因此，很难说哪一个式子是最合适的。好在用户通常都不会这么较真，您只要给出其中一个式子就可以了。  
如果您是计算24点的发烧友，您一定听说过1、5、5、5这个经典的计算24点考题。这道题的答案是（5－1÷5）×5，最大的特别之处运算中采用了分数，只有允许使用分数才能求解。其实这样的题目不下10道，如2、4、10、10，还有3、3、7、7等。游戏要支持分数运算，可以采用小数运算再取近似值的方式。不过这种方式不够优雅。最好是设计一个分数类，实现四则运算方法，是否要操作符重载就看您的个人偏好了。分数类有两个私有成员变量，一个是分子，一个是分母。当表示整数时，分母为1。在保存中间结果时，分子与分母不必互质。如果要互质，可参考经典的辗转相除法。