求算24点C++源码

关于二十四点游戏的编程思路与基本算法

2003-4-10 7:55:13 VCOK 檀银兵阅读次数: 3105
　　漫长的假期对于我来说总是枯燥无味的，闲来无聊便和同学玩起童年时经常玩的二十四点牌游戏来。此游戏说来简单，就是利用加减乘除以及括号将给出的四张牌组成一个值为24的表达式。但是其中却不乏一些有趣的题目，这不，我们刚玩了一会儿，便遇到了一个难题——3、6、6、10（其实后来想想，这也不算是个太难的题，只是当时我们的脑筋都没有转弯而已，呵呵）。　　问题既然出现了，我们当然要解决。冥思苦想之际，我的脑中掠过一丝念头——何不编个程序来解决这个问题呢？文曲星中不就有这样的程序吗？所以这个想法应该是可行。想到这里我立刻开始思索这个程序的算法，最先想到的自然是穷举法（后来发现我再也想不到更好的方法了，悲哀呀，呵呵），因为在这学期我曾经写过一个小程序——计算有括号的简单表达式。只要我能编程实现四个数加上运算符号所构成的表达式的穷举，不就可以利用这个计算程序来完成这个计算二十四点的程序吗？确定了这个思路之后，我开始想这个问题的细节。
首先穷举的可行性问题。我把表达式如下分成三类——
1、无括号的简单表达式。
2、有一个括号的简单表达式。
3、有两个括号的较复4、杂表达式。
穷举的开始我对给出的四个数进行排列，其可能的种数为4*3*2*1=24。我利用一个嵌套函数实现四个数的排列，算法如下:
/* ans[] 用来存放各种排列组合的数组 */
/* c[] 存放四张牌的数组 */
/* k[] c[]种四张牌的代号，其中k[I]=I+1。
用它来代替c[]做处理，考虑到c[]中有可能出现相同数的情况 */
/* kans[] 暂存生成的排列组合 */
/* j 嵌套循环的次数 */
int fans(c,k,ans,kans,j)
int j,k[],c[];char ans[],kans[];
{ int i,p,q,r,h,flag,s[4],t[4][4];
for(p=0,q=0;p<4;p++)
{ for(r=0,flag=0;r if(k[p]!=kans[r]) flag++;
if(flag==j) t[j][q++]=k[p];
}
for(s[j]=0;s[j]<4-j;s[j]++)
{ kans[j]=t[j][s[j]];
if(j==3) { for(h=0;h<4;h++)
ans[2*h]=c[kans[h]-1]; /* 调整生成的排列组合在最终的表
达式中的位置 */
for(h=0;h<3;h++)
symbol(ans,h); /* 在表达式中添加运算符号 */
}
else { j++;
fans(c,k,ans,kans,j);
j--;
}
}
}　　正如上面函数中提到的，在完成四张牌的排列之后，在表达式中添加运算符号。由于只有四张牌，所以只要添加三个运算符号就可以了。由于每一个运算符号可重复，所以计算出其可能的种数为4*4*4=64种。仍然利用嵌套函数实现添加运算符号的穷举，算法如下:/* ans[],j同上。sy[]存放四个运算符号。h为表达式形式。*/
int sans(ans,sy,j,h)
char ans[],sy[];int j,h;
{ int i,p,k[3],m,n; char ktans[20];
for(k[j]=0;k[j]<4;k[j]++)
{ ans[2*j+1]=sy[k[j]]; /* 刚才的四个数分别存放在0、2、4、6位
这里的三个运算符号分别存放在1、3、5位*/
if(j==2)
{ ans[5]=sy[k[j]];
/* 此处根据不同的表达式形式再进行相应的处理 */
}
else { j++; sans(ans,sy,j--,h); }
}
}　　好了，接下来我再考虑不同表达式的处理。刚才我已经将表达式分为三类，是因为添加三个括号对于四张牌来说肯定是重复的。对于第一种，无括号自然不用另行处理；而第二种情况由以下代码可以得出其可能性有六种，其中还有一种是多余的。
for(m=0;m<=4;m+=2)
for(n=m+4;n<=8;n+=2)
　　这个for循环给出了添加一个括号的可能性的种数，其中m、n分别为添加在表达式中的左右括号的位置。我所说的多余的是指m=0，n=8，也就是放在表达式的两端。这真是多此一举，呵呵！最后一种情况是添加两个括号，我分析了一下，发现只可能是这种形式才不会是重复的——（a b）(c d)。为什么不会出现嵌套括号的情况呢？因为如果是嵌套括号，那么外面的括号肯定是包含三个数字的（四个没有必要），也就是说这个括号里面包含了两个运算符号，而这两个运算符号是被另外一个括号隔开的。那么如果这两个运算符号是同一优先级的，则肯定可以通过一些转换去掉括号（你不妨举一些例子来试试），也就是说这一个括号没有必要；如果这两个运算符号不是同一优先级，也必然是这种形式((a+-b)*/c)。而*和/在这几个运算符号中优先级最高，自然就没有必要在它的外面添加括号了。　　综上所述，所有可能的表达式的种数为24*64*（1+6+1）=12288种。哈哈，只有一万多种可能性（这其中还有重复），这对于电脑来说可是小case哟！所以，对于穷举的可行性分析和实现也就完成了。
　　接下来的问题就是如何对有符号的简单表达式进行处理。这是栈的一个著名应用，那么什么是栈呢？栈的概念是从日常生活中货物在货栈种的存取过程抽象出来的，即最后存放入栈的货物（堆在靠出口处）先被提取出去，符合“先进后出，后进先出”的原则。这种结构犹如子弹夹。
在栈中，元素的插入称为压入（push）或入栈，元素的删除称为弹出（pop）或退栈。　　栈的基本运算有三种，其中包括入栈运算、退栈运算以及读栈顶元素，这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。　　那么作为栈的著名应用，表达式的计算可以有两种方法。　　第一种方法——
　　首先建立两个栈，操作数栈OVS和运算符栈OPS。其中，操作数栈用来记忆表达式中的操作数，其栈顶指针为topv，初始时为空，即topv=0；运算符栈用来记忆表达式中的运算符，其栈顶指针为topp，初始时，栈中只有一个表达式结束符，即topp=1，且OPS（1）=‘；’。此处的‘；’即表达式结束符。

#include "stdafx.h"
#include <iostream>
#include <string>
#include <cmath>using namespace std;const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER  = 4;
const int NUMBER_TO_BE_CAL = 24;double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];bool Search(int n)
{
    if (n == 1) {
        if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) {
            cout << expression[0] <<"="<<NUMBER_TO_BE_CAL<< endl;
            return false;
        } else {
            return false;
        }
    }    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double a, b;
            string expa, expb;            a = number[i];
            b = number[j];
            number[j] = number[n - 1];            expa = expression[i];
            expb = expression[j];
            expression[j] = expression[n - 1];            expression[i] = '(' + expa + '+' + expb + ')';
            number[i] = a + b;
            if ( Search(n - 1) ) return true;

            expression[i] = '(' + expa + '-' + expb + ')';
            number[i] = a - b;
            if ( Search(n - 1) ) return true;

            expression[i] = '(' + expb + '-' + expa + ')';
            number[i] = b - a;
            if ( Search(n - 1) ) return true;
                                    expression[i] = '(' + expa + '*' + expb + ')';
            number[i] = a * b;
            if ( Search(n - 1) ) return true;            if (b != 0) {
                expression[i] = '(' + expa + '/' + expb + ')';
                number[i] = a / b;
                if ( Search(n - 1) ) return true;
            }
            if (a != 0) {
                expression[i] = '(' + expb + '/' + expa + ')';
                number[i] = b / a;
                if ( Search(n - 1) ) return true;
            }            number[i] = a;
            number[j] = b;
            expression[i] = expa;
            expression[j] = expb;
        }
    }
    return false;
}
int main(int argc, char* argv[])
{
    for (int i = 0; i < COUNT_OF_NUMBER; i++) {
        char buffer[20];
        int  x;
        cin >> x;
        number[i] = x;
        itoa(x, buffer, 10);
        expression[i] = buffer;
    }    if ( Search(COUNT_OF_NUMBER) ) {
        cout << "Success." << endl;
    } else {
        cout << "Fail." << endl;
    }
    return 0;
}

http://www.csdn.net/develop/read_article.asp?id=20064

#include "iostream.h"
#include "stdlib.h"void step1 (int x,int y,int * p)
{
    p[0]=x+y;
    p[1]=x-y;
    p[2]=x*y;
    if (y!=0&&(x%y==0))
        p[3]=x/y;
    else
        p[3]=-1000;  //make it couldn't reach 24
}int conclude (int x,int y)
{
    if ((x+y)==24)
        return 0;
    if ((x-y)==24)
        return 1;
    if ((x*y)==24)
        return 2;
    if (y==0 || (x%y!=0))
        return -1;
    if ((x/y)==24)
        return 3;
    return -1;
}extern void exit (int);void print (int x,int y,int s)
{
    switch (s)
    {    case 0:
        cout<<x<<'+'<<y<<'='<<x+y<<' ';   break;
    case 1:
        cout<<x<<'-'<<y<<'='<<x-y<<' ';   break;
    case 2:
        cout<<x<<'*'<<y<<'='<<x*y<<' ';   break;
    case 3:
        cout<<x<<'/'<<y<<'='<<x/y<<' ';   break;
    default:
        cout<<"Error!";
        exit(0);
    }
}int main ()
{
    int i,j,k,l,m,n,result;
    int a[4],b[4],num[4];
    bool circulate=true;    while(circulate)
    {
        cout<<"please enter four numbers:";
        for (i=0;i<4;i++)
        {
            cin>>num[i];
            if (num[i]<=0 || num[i]>13)
            {
                cout<<"\a error! enter again."<<endl;
                cin.ignore(100,'\n');
                break;
            }
            if (i==3)
                circulate=false;
        }
    }    int signal_1=0,signal_2=0,signal_3=0,signal_4=0,signal_x=0;
    int sign=0,temp1=0,temp2=0;    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            if (j==i) continue;
            step1(num[i],num[j],a);            for (l=0;l<4;l++)
            {
                if (l==i||l==j) continue;
                n=6-i-j-l;
                for (k=0;k<4;k++) //signal_1 signal_2
                {
                    step1(a[k],num[l],b);
                    for (m=0;m<4;m++)
                    {
                        result=conclude (b[m],num[n]);
                        if (result!=-1)
                        {
                            if (signal_1 && (k==m && m==result && k==0) )
                                continue;
                            if (signal_2 && (k==m && m==result && k==2) )
                                continue;
                            //if (signal_3 && (m==result && k==0) )
                            //    continue;
                            //if (signal_4 && (m==result && k==2) )
                            //    continue;                            else
                            {
                                if (k==m && m==result && k==0)
                                    signal_1=1;
                                if (k==m && m==result && k==2)
                                    signal_2=1;
                            //    if (m==result && k==0)
                            //        signal_3=1;
                            //    if (m==result && k==2)
                            //        signal_4=1;

                                print (num[i],num[j],k);
                                print (  a[k],num[l],m);
                                print (  b[m],num[n],result);
                                cout <<endl;
                            }
                        }
                    }// end of the innerest "for" statement

                }//end of the first condition
                step1 (num[l],num[n],b);                for (k=0;k<4;k++)
                {
                    for (m=0;m<4;m++)
                    {
                        result=conclude (a[k],b[m]);                        if (result !=-1)
                        {
                            if (signal_1 && (k==m && m==result && k==0) )
                                continue;
                            if (signal_2 && (k==m && m==result && k==2) )
                                continue;
                            if (signal_x==1 && temp1==a[k] && b[m]==temp2 && sign==result)
                                continue;                            if (signal_x!=1)
                            {
                                sign=result;
                                temp1=a[k];
                                temp2=b[m];
                                signal_x=1;
                            }                            print (num[i],num[j],k);
                            print (num[l],num[n],m);
                            print (  a[k],  b[m],result);
                            cout<<endl;
                        }
                    }
                }//end of the second condition.
            }//end "for" starement of L
        }//end "for" statement of J
    }//end "for" statement of I
    system("pause");
    return 0;
}

调试易

求算24点C++源码

解决方案 »