lzm

who dare win.
posts - 14, comments - 29, trackbacks - 0, articles - 0

加减乘除24

Posted on 2008-10-21 08:13 lzmagic 阅读(2387) 评论(7)  编辑 收藏 引用

 

  1/**
  2 *    程序：加减乘除24
  3 *    输入：四个1到13整数（输入四个0结束）  1/**//**
  2 *    程序：加减乘除24
  3 *    输入：四个1到13整数（输入四个0结束）
  4 *    输出：加减乘除得到24的式子，否则输出"None."
  5 *    思路：我们希望构造出满足形如 a[0] opr[0] a[1] opr[1] a[2] opr[2] a[3] = 24 的式子，采用回溯的思路，将右式不断缩小，
  6 *        最后只剩下a[0]，然后再判断左式是否与它相等，相等的话就结束搜索，输出结果。
  7 *            注：1）opr[i]指的是右式（不妨设为X）和a[i]的操作类型，一共有6种：
  8 *                         ADD: X + a[i] (= a[i] + X，算为同一种)
  9 *                         SUB_L: a[i] - X
 10 *                        SUB_R: X - a[i]
 11 *                        MUL: X * a[i] (= a[i] * X，算为同一种)
 12 *                        DIV_L: a[i] / X
 13 *                        DIV_R: X / a[i]
 14 *                2）回溯中把右式分解出分子(u)和分母(d)主要是考虑一些特殊情况，例如3, 3, 7, 7和4, 4, 5, 5
 15 *    作者：lzmagic
 16 */
 17
 18#include <iostream>
 19using namespace std;
 20
 21enum OPR { ADD, SUB_L, SUB_R, MUL, DIV_L, DIV_R };
 22
 23int a[4];            // 操作数的数组
 24OPR opr[3];    // 操作符的数组
 25int top;            // 当前要处理的操作符的下标       
 26bool ok;          // 是否成功的布尔值
 27
 28void TB2 (int id)
 29{
 30    if (id == 0)
 31    {
 32        cout << a[id];
 33        return;
 34    }
 35
 36    switch (opr[id - 1])
 37    {
 38        case ADD:   cout << "( ";                               TB2 (id - 1); cout << " + " << a[id] << " )"; break;
 39        case SUB_L: cout << "( " << a[id] << " - "; TB2 (id - 1); cout << " )";                               break;
 40        case SUB_R: cout << "( ";                             TB2 (id - 1); cout << " - " << a[id] << " )";  break;
 41        case MUL:   cout << "( ";                               TB2 (id - 1); cout << " * " << a[id] << " )"; break;
 42        case DIV_L: cout << "( " << a[id] << " / ";  TB2 (id - 1); cout << " )";                               break;
 43        case DIV_R: cout << "( ";                               TB2 (id - 1); cout << " / " << a[id] << " )"; break;
 44    }
 45}
 46
 47void Print()
 48{
 49    cout << "24 = ";
 50    TB2(3);
 51    cout << endl;
 52}
 53
 54void Swap (int & a, int & b)
 55{
 56    int tmp = a; a = b; b = tmp;
 57}
 58
 59void TB1 (int u, int d, int id)     // u: up，表示右式的分子；d: down，表示右式的分母；TB: trackback，表示回溯。
 60{
 61    if (id == 0)
 62    {
 63        if (d != 0 && u % d == 0 && u / d == a[id])
 64        {
 65            ok = true;
 66            Print();
 67        }
 68        return;
 69    }
 70
 71    for (int i = id; i >= 0; --i)
 72    {
 73        Swap (a[id], a[i]);
 74       
 75        // ADD : X + a[id] = u / d <==> X = (u - a[id] * d) / d
 76        opr[top--] = ADD;
 77        TB1 (u - a[id] * d, d, id - 1); if (ok == true) break;
 78        top++;
 79
 80        // SUB_L : a[id] - X = u / d <==> X = (a[id] * d - u) / d
 81        opr[top--] = SUB_L;
 82        TB1 (a[id] * d - u, d, id - 1); if (ok == true) break;
 83        top++;
 84       
 85        // SUB_R : X - a[id] = u / d <==> X = (a[id] * d + u) / d
 86        opr[top--] = SUB_R;
 87        TB1 (a[id] * d + u, d, id - 1); if (ok == true) break;
 88        top++;
 89
 90        // MUL : X * a[id] = u / d <==> X = a[id] / (a[id] * d)
 91        opr[top--] = MUL;
 92        TB1 (u, a[id] * d, id - 1);        if (ok == true) break;
 93        top++;
 94
 95        // DIV_L : a[id] / X = u / d <==> X = (a[id] * d) / u
 96        opr[top--] = DIV_L;
 97        TB1 (a[id] * d, u, id - 1);        if (ok == true) break;
 98        top++;
 99
100        // DIV_R : X / a[id] = u / d <==> X = (a[id] * u) / d
101        opr[top--] = DIV_R;
102        TB1 (a[id] * u, d, id - 1);        if (ok == true) break;
103        top++;
104
105        Swap (a[id], a[i]);
106    }
107}
108
109int main()
110{
111    for (int i = 0; i < 4; ++i)
112        cin >> a[i];
113
114    while (a[0] != 0 || a[1] != 0 || a[2] != 0 || a[3] != 0)
115    {
116        ok = false;
117        top = 2;
118        TB1 (24, 1, 3);
119        if (ok == false)
120            cout << "None." << endl;
121       
122        for (i = 0; i < 4; ++i)
123            cin >> a[i];
124    }
125   
126    return 0;
127}
  4 *    输出：加减乘除得到24的式子，否则输出"None."
  5 *    思路：我们希望构造出满足形如 a[0] opr[0] a[1] opr[1] a[2] opr[2] a[3] = 24 的式子，采用回溯的思路，将右式不断缩小，
  6 *        最后只剩下a[0]，然后再判断左式是否与它相等，相等的话就结束搜索，输出结果。
  7 *            注：1）opr[i]指的是右式（不妨设为X）和a[i]的操作类型，一共有6种：
  8 *                         ADD: X + a[i] (= a[i] + X，算为同一种)
  9 *                         SUB_L: a[i] - X
 10 *                        SUB_R: X - a[i]
 11 *                        MUL: X * a[i] (= a[i] * X，算为同一种)
 12 *                        DIV_L: a[i] / X
 13 *                        DIV_R: X / a[i]
 14 *                2）回溯中把右式分解出分子(u)和分母(d)主要是考虑一些特殊情况，例如3, 3, 7, 7和4, 4, 5, 5
 15 *    作者：lzmagic
 16 */
 17
 18#include <iostream>
 19using namespace std;
 20
 21enum OPR { ADD, SUB_L, SUB_R, MUL, DIV_L, DIV_R };
 22
 23int a[4];            // 操作数的数组
 24OPR opr[3];    // 操作符的数组
 25int top;            // 当前要处理的操作符的下标        
 26bool ok;          // 是否成功的布尔值
 27
 28void TB2 (int id)
 29{
 30    if (id == 0)
 31    {
 32        cout << a[id];
 33        return;
 34    }
 35
 36    switch (opr[id - 1])
 37    {
 38        case ADD:   cout << "( ";                               TB2 (id - 1); cout << " + " << a[id] << " )"; break;
 39        case SUB_L: cout << "( " << a[id] << " - "; TB2 (id - 1); cout << " )";                               break;
 40        case SUB_R: cout << "( ";                             TB2 (id - 1); cout << " - " << a[id] << " )";  break;
 41        case MUL:   cout << "( ";                               TB2 (id - 1); cout << " * " << a[id] << " )"; break;
 42        case DIV_L: cout << "( " << a[id] << " / ";  TB2 (id - 1); cout << " )";                               break;
 43        case DIV_R: cout << "( ";                               TB2 (id - 1); cout << " / " << a[id] << " )"; break;
 44    }
 45}
 46
 47void Print()
 48{
 49    cout << "24 = ";
 50    TB2(3);
 51    cout << endl;
 52}
 53
 54void Swap (int & a, int & b)
 55{
 56    int tmp = a; a = b; b = tmp;
 57}
 58
 59void TB1 (int u, int d, int id)     // u: up，表示右式的分子；d: down，表示右式的分母；TB: trackback，表示回溯。
 60{
 61    if (id == 0)
 62    {
 63        if (d != 0 && u % d == 0 && u / d == a[id])
 64        {
 65            ok = true;
 66            Print();
 67        }
 68        return;
 69    }
 70
 71    for (int i = id; i >= 0; --i)
 72    {
 73        Swap (a[id], a[i]);
 74        
 75        // ADD : X + a[id] = u / d <==> X = (u - a[id] * d) / d
 76        opr[top--] = ADD;
 77        TB1 (u - a[id] * d, d, id - 1); if (ok == true) break;
 78        top++;
 79
 80        // SUB_L : a[id] - X = u / d <==> X = (a[id] * d - u) / d
 81        opr[top--] = SUB_L;
 82        TB1 (a[id] * d - u, d, id - 1); if (ok == true) break;
 83        top++;
 84        
 85        // SUB_R : X - a[id] = u / d <==> X = (a[id] * d + u) / d
 86        opr[top--] = SUB_R;
 87        TB1 (a[id] * d + u, d, id - 1); if (ok == true) break;
 88        top++;
 89
 90        // MUL : X * a[id] = u / d <==> X = a[id] / (a[id] * d) 
 91        opr[top--] = MUL;
 92        TB1 (u, a[id] * d, id - 1);        if (ok == true) break;
 93        top++;
 94
 95        // DIV_L : a[id] / X = u / d <==> X = (a[id] * d) / u
 96        opr[top--] = DIV_L;
 97        TB1 (a[id] * d, u, id - 1);        if (ok == true) break;
 98        top++;
 99
100        // DIV_R : X / a[id] = u / d <==> X = (a[id] * u) / d
101        opr[top--] = DIV_R;
102        TB1 (a[id] * u, d, id - 1);        if (ok == true) break;
103        top++;
104
105        Swap (a[id], a[i]);
106    }
107}
108
109int main()
110{
111    for (int i = 0; i < 4; ++i)
112        cin >> a[i];
113
114    while (a[0] != 0 || a[1] != 0 || a[2] != 0 || a[3] != 0)
115    {
116        ok = false;
117        top = 2;
118        TB1 (24, 1, 3);
119        if (ok == false)
120            cout << "None." << endl;
121        
122        for (i = 0; i < 4; ++i)
123            cin >> a[i];
124    }
125    
126    return 0;
127}

Feedback

# re: 加减乘除24  回复  更多评论   

2008-10-22 19:58 by 天策魂之音
与其光贴代码不如把思路share出来

何如？

而且关键代码一行注释也没-。-

# re: 加减乘除24  回复  更多评论   

2008-10-22 21:42 by 金山毒霸2008
没错，需要思路的介绍啊，期待中。

# re: 加减乘除24  回复  更多评论   

2008-10-23 09:48 by canopus
很好，看懂了，收藏

# re: 加减乘除24  回复  更多评论   

2008-10-23 15:36 by lzmagic
哈哈，改过来了，之前没太重视，谢谢大家的建议！

# re: 加减乘除24  回复  更多评论   

2009-04-15 14:22 by brightcoder
博主好强大，呵呵，搜索，又是搜索

# re: 加减乘除24  回复  更多评论   

2009-06-18 13:09 by adad
6.7.8.9.10加减乘除怎么能=24

# re: 加减乘除24  回复  更多评论   

2010-07-12 10:38 by 65666
想问下~为什么tb1函数要swap交换后在执行后有swap

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理