最新消息:点击查看大S的省钱秘笈

求解二十四点的所有解 C++版

编程相关 Slyar 7118浏览 8评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

24点游戏是一种使用扑克牌来进行的益智类游戏,游戏内容是:从一副扑克牌中抽去大小王剩下52张,任意抽取4张牌,把牌面上的数(A代表1)运用加、减、乘、除和括号等进行运算得出24。每张牌都必须使用一次,但不能重复使用。

简单说就是给你4个数(1-13),数字可以重复,然后让你运用加、减、乘、除和括号运算得出24,每个数字必须使用一次,但不能重复使用。当然,运算中出现的分数是允许的,如1 5 5 5和3 3 8 8这两组数字得到的24点表达式为((5-(1/5))*5) 和 (8/(3-(8/3))),是不是很变态?

因为表达式是字符串,所以这次我没有用C语言实现,而是选择了具有string类型的C++语言,这样可以更好地处理字符串。在代码中我还使用了STL的Vector来过滤掉重复的解,感叹STL的方便之余对迭代器的使用也有了更深的认识。

至于24点求解的算法,仔细研究一下24点解集,可以发现解的形式无非就是2种。一种是(((A,B),C),D),另一种是((A,B),(C,D))。有了这个发现,就可以在很大程度上避免对于括号的处理,接下来的工作就是…枚举,哈哈。

花了3个多小时敲代码,注释我写得很清晰了,测试了很多组数据,目前没有发现bug,下面是代码。

/*
Slyar
2009.10.31
*/

#include   
#include 
#include 
#include 
#include 
#include 

using namespace std;

/* 存放解集 */
vector ivec;

/* 第1个数和第2个数的值及表达式 */
double key1_2[6] = {0};
string exp1_2[6];

/* 第3个数和第4个数的值及表达式 */
double key3_4[6] = {0};
string exp3_4[6];

/* 第3个数和前2个数的值及表达式 */
double key12_3[6] = {0};
string exp12_3[6];

/* 第4个数和前3个数的值及表达式 */
double key123_4[6] = {0};
string exp123_4[6];

/* 前2个数和后2个数的值及表达式 */
double key12_34[6] = {0};
string exp12_34[6];

/* 函数声明 */
int Permutation(int[], int[][4]);
void Calc(double, double, double[], string[], string, string);
void Work(int[], int[][4], int);

/* 主函数 */
int main()
{
    int num[4] = {0};
    int array[24][4] = {0};
    int count = 0;
    
    cout << "请输入4个1-13之间的整数,中间以空格隔开" << endl;
    
    /* 读入数据 */
    for (int i = 0; i < 4; i++)
    {
        cin >> num[i];
    }
    
    /* 待检测数据的数量 */
    count = Permutation(num, array);
    
    /* 求解24点 */
    Work(num, array, 24);
    
    /* 对结果进行排序 */
    sort(ivec.begin(), ivec.end());
    
    /* 去掉重复的解 */
    vector::iterator iter = unique(ivec.begin(), ivec.end());
    
    /* 输出解集 */
    if (ivec.size() != 0)
    {
        cout << "该组数据的解集为:" << endl;
        for (vector::iterator it = ivec.begin(); it != iter; it++)
        {
            cout << *it << endl;
        }
    }
    else
    {
        cout << "该组数据无解" << endl;
    }
    
    system("pause");
    return 0;
}

/* 计算2个数,保存值及表达式 */
void Calc(double a, double b, double key[], string exp[], string expa, string expb)
{
    key[0] = a + b;
    exp[0] = '(' + expa + '+' + expb + ')';
    
    key[1] = a - b;
    exp[1] = '(' + expa + '-' + expb + ')';
    
    key[2] = b - a;
    exp[2] = '(' + expb + '-' + expa + ')';
    
    key[3] = a * b;
    exp[3] = '(' + expa + '*' + expb + ')';
    
    if (b > 0)
    {
        key[4] = a / b;
        exp[4] = '(' + expa + '/' + expb + ')';
    }
    
    if (a > 0)
    {
        key[5] = b / a;
        exp[5] = '(' + expb + '/' + expa + ')';
    }
}

/* 生成数据的排列组合 */
int Permutation(int num[], int array[][4])
{
    int flag;
    int k = 0;
    int count = 0;
    int i, j, m, n, s;
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < 4; j++)
        {
            for (m = 0; m < 4; m++)
            {
                for (n = 0; n < 4; n++)
                {
                    if (i != j && i != m && i != n && j != m && j != n && m != n)
                    {
                        flag = 1;
                        for(s = 0; s < k; s++)
                        {
                            if(array[s][0] == num[i] && array[s][1] == num[j] && array[s][2] == num[m] && array[s][3] == num[n])
                            {
                                flag = 0;
                            }
                        }
                        if (flag == 1)
                        {
                            array[k][0] = num[i];
                            array[k][1] = num[j];
                            array[k][2] = num[m];
                            array[k][3] = num[n];
                            k++;
                            count++;
                        }
                    }
                }
            }
        }
    }
    return count;
}

/* 求解24点 */
void Work(int num[], int array[][4], int count)
{
    for (int i = 0; i < count; i++)
    {
        char buffer[20];
        string expa, expb;
        
        /* 转换第1个数字为表达式 */
        itoa(array[i][0], buffer, 10);
        expa = buffer;
        
        /* 转换第2个数字为表达式 */
        itoa(array[i][1], buffer, 10);
        expb = buffer;
        
        /* 计算第1个数和第2个数 */
        Calc(array[i][0], array[i][1], key1_2, exp1_2, expa, expb);
        
        /* (((A,B),C),D)形式 */
        for (int j = 0; j < 6; j++)
        {
            /* 转换第3个数字为表达式 */
            itoa(array[i][2], buffer, 10);
            expb = buffer;
            
            /* 计算第3个数和前2个数 */
            Calc(key1_2[j], array[i][2], key12_3, exp12_3, exp1_2[j], expb);
            
            for (int k = 0; k < 6; k++)
            {
                /* 转换第4个数字为表达式 */
                itoa(array[i][3], buffer, 10);
                expb = buffer;
                
                /* 计算第4个数和前3个数 */
                Calc(key12_3[k], array[i][3], key123_4, exp123_4, exp12_3[k], expb);
                
                for (int t = 0; t < 6; t++)
                {
                    if (fabs(key123_4[t] - 24) < 1e-6)
                    {
                        ivec.push_back(exp123_4[t]);
                    }
                }
            } 
        }
        
        /* 转换第3个数字为表达式 */
        itoa(array[i][2], buffer, 10);
        expa = buffer;
        
        /* 转换第4个数字为表达式 */
        itoa(array[i][3], buffer, 10);
        expb = buffer;
        
        /* 计算第3个数和第4个数 */
        Calc(array[i][2], array[i][3], key3_4, exp3_4, expa, expb);
        
        /* ((A,B),(C,D))形式 */
        for (int j = 0; j < 6; j++)
        {
            for (int k = 0; k < 6; k++)
            {
                /* 计算前2个数和后2个数 */
                Calc(key1_2[j], key3_4[k], key12_34, exp12_34, exp1_2[j], exp3_4[k]);
                
                for (int t = 0; t < 6; t++)
                {
                    if (fabs(key12_34[t] - 24) < 1e-6)
                    {
                        ivec.push_back(exp12_34[t]);
                    }
                }
            }
        }
    }
}

转载请注明:Slyar Home » 求解二十四点的所有解 C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (8)

  1. @woejoy 呵呵,编译器的问题,那种写法要求C99,很多老的编译器依旧是C98标准。
    Slyar9年前 (2011-07-13)回复
  2. 如果你那边运行没错,那就是我的vc++6.0编译器出问题了,我这边编译的时候提示出错,我删了那一行的int就可以了。我不是内行,不知道什么理由,无法告知,留言只是说明我在使用你的代码时的结果,谢谢。@Slyar
    woejoy9年前 (2011-07-13)回复
  3. @woejoy 呵呵,为什么要删去呢?没有理由的。
    Slyar9年前 (2011-07-02)回复
  4. 经运行,218行的int需要删去,望检查。
    woejoy9年前 (2011-07-02)回复
  5. @felix021 啊,这不是前一段一直被其他程序阻碍了嘛,嘿嘿... 恩,我知道next_permutation和prev_permutation,不过因为要判重嘛,所以就直接写了...
    Slyar11年前 (2009-10-31)回复
  6. 对了,顺便说一下,stl的algorithm里面有两个函数分别是 next_permutation prev_permutation
    felix02111年前 (2009-10-31)回复
  7. 唔,可以正常算出3388和1555的解,赞~ 不过你说要研究这个算法可是5个月以前的事情了啊。。。 详见这篇的评论:https://www.felix021.com/blog/read.php?1602
    felix02111年前 (2009-10-31)回复
  8. 你好NB,我自叹不如
    hdlover11年前 (2009-10-31)回复