24点游戏大家都知道：4张牌，可以进行+ - * / 四种运算，可以使用括号，每个牌用一次，任意组合构造表达式使结果为24。

扩展问题：n个整数，四种运算，可使用括号，每个数字使用一次，使表达式结果为 k

下面的算法1和算法2都是穷举，只是穷举的方式不一样，以下给出的两个算法代码都可以计算扩展问题。可能是集合操作原因，算法1的速度明显比算法2快

书上分析如下

算法1：

算法1代码如下，我在原来的基础上做了一点改动1、从数组中任选两个数时，保证数对前面没有选择过； 2、通过运算符优先级去除多余的括号；3、选出的两个数相同时，减法和除法只做一次，即只做a-b ,a/b, 不做 b-a,b/a，其中1、3都可以减少冗余计算

调用函数PointGame即可返回表达式结果

1 #include

2 #include

3 #include

4 #include

5 #include

6 #include

7 #include

8 using namespacestd;9

10 //cards[i]的值是通过表达式expr[i]计算而来11 //且expr的最后一个运算操作lastop[i]

12 bool GameRecur(double cards[], string expr[], charlastop[],13 const int cardsNum, const intresult)14 {15 if(cardsNum == 1)16 {17 if(cards[0] ==result)18 {19 //cout<

20 return true;21 }22 else return false;23 }24 //从已有数中任选两个,计算得到中间结果，并且和剩余的数一起存在cards数组的前25 //cardsNum-1个位置

26 map,bool>selectedPair;27 for(int i = 0; i(cards[i], cards[k]))32 != selectedPair.end() || selectedPair.find(pair

33 (cards[k], cards[i])) !=selectedPair.end() )34 break;35 else

36 {37 selectedPair[pair(cards[i], cards[k])] = 1;38 selectedPair[pair(cards[k], cards[i])] = 1;39 }40 //上面的代码保证选出的数对不重复

41 double a = cards[i], b =cards[k];42 cards[k] = cards[cardsNum-1];43 string expra = expr[i], exprb =expr[k];44 expr[k] = expr[cardsNum-1];45 char lastop_a = lastop[i], lastop_b =lastop[k];46 lastop[k] = lastop[cardsNum-1];47

48 cards[i] = a +b;49 expr[i] = expra + '+' +exprb;50 lastop[i] = '+';51 if(GameRecur(cards, expr, lastop, cardsNum-1, result))52 return true;53

54 cards[i] = a -b;55 if('+' == lastop_b || '-' ==lastop_b)56 expr[i] = expra + '-' + '(' + exprb + ')';57 else expr[i] = expra + '-' +exprb;58 lastop[i] = '-';59 if(GameRecur(cards, expr, lastop, cardsNum-1, result))60 return true;61

62 if(a !=b)63 {64 cards[i] = b -a;65 if('+' == lastop_a || '-' ==lastop_a)66 expr[i] = exprb + '-' + '(' + expra + ')';67 else expr[i] = exprb + '-' +expra;68 lastop[i] = '-';69 if(GameRecur(cards, expr, lastop, cardsNum-1, result))70 return true;71 }72

73 cards[i] = a *b;74 if('-' == lastop_a || '+' ==lastop_a)75 expr[i] = '(' + expra + ')' + '*';76 else expr[i] = expra + '*';77 if('*' == lastop_b || ' ' ==lastop_b)78 expr[i] +=exprb;79 else expr[i] += '(' + exprb + ')';80 lastop[i] = '*';81 if(GameRecur(cards, expr, lastop, cardsNum-1, result))82 return true;83

84 if(b != 0)85 {86 cards[i] = a /b;87 if('-' == lastop_a || '+' ==lastop_a)88 expr[i] = '(' + expra + ')' + '/';89 else expr[i] = expra + '/';90 if(' ' ==lastop_b)91 expr[i] +=exprb;92 else expr[i] += '(' + exprb + ')';93 lastop[i] = '/';94 if(GameRecur(cards, expr, lastop, cardsNum-1, result))95 return true;96 }97

98 if(a != 0 && a!=b)99 {100 cards[i] = b /a;101 if('-' == lastop_b || '+' ==lastop_b)102 expr[i] = '(' + exprb + ')' + '/';103 else expr[i] = exprb + '/';104 if(' ' ==lastop_a)105 expr[i] +=expra;106 else expr[i] += '(' + expra + ')';107 lastop[i] = '/';108 if(GameRecur(cards, expr, lastop, cardsNum-1, result))109 return true;110 }111

112 //把选出来的两个数放回原位

113 cards[i] =a;114 cards[k] =b;115 expr[i] =expra;116 expr[k] =exprb;117 lastop[i] =lastop_a;118 lastop[k] =lastop_b;119 }120 }121 return false;122 }123

124 //cards 输入的牌125 //cardsNum 牌的数目126 //result 想要运算得到的结果

127 string PointGame(int cards[], const int cardsNum, const intresult)128 {129 stringexpr[cardsNum];130 charlastop[cardsNum];131 doublecardsCopy[cardsNum];132 for(int i = 0; i < cardsNum; i++)133 {134 char buf[30];135 sprintf(buf, "%d", cards[i]);136 expr[i] =buf;137 lastop[i] = ' ';//表示cardsCopy[i]是不经过任何运算的原始数据

138 cardsCopy[i] =cards[i];139 }140 if(GameRecur(cardsCopy, expr, lastop, cardsNum, result))141 return expr[0];142 else return "-1";143 }

View Code

对算法1稍作修改可以输出全部的表达式：

1 //------------------------------------------------------------算法1输出所有组合2 //cards[i]的值是通过表达式expr[i]计算而来3 //且expr的最后一个运算操作lastop[i]

4 bool GameRecur_all(double cards[], string expr[], charlastop[],5 const int cardsNum, const intresult)6 {7 if(cardsNum == 1)8 {9 if(cards[0] ==result)10 {11 cout<

18 map,bool>selectedPair;19 bool res = false;20 for(int i = 0; i(cards[i], cards[k]))25 != selectedPair.end() || selectedPair.find(pair

26 (cards[k], cards[i])) !=selectedPair.end() )27 break;28 else

29 {30 selectedPair[pair(cards[i], cards[k])] = 1;31 selectedPair[pair(cards[k], cards[i])] = 1;32 }33 //上面的代码保证选出的数对不重复

34 double a = cards[i], b =cards[k];35 cards[k] = cards[cardsNum-1];36 string expra = expr[i], exprb =expr[k];37 expr[k] = expr[cardsNum-1];38 char lastop_a = lastop[i], lastop_b =lastop[k];39 lastop[k] = lastop[cardsNum-1];40

41 cards[i] = a +b;42 expr[i] = expra + '+' +exprb;43 lastop[i] = '+';44 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)45 ||res;46

47 cards[i] = a -b;48 if('+' == lastop_b || '-' ==lastop_b)49 expr[i] = expra + '-' + '(' + exprb + ')';50 else expr[i] = expra + '-' +exprb;51 lastop[i] = '-';52 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result) ||res;53

54 if(a !=b)55 {56 cards[i] = b -a;57 if('+' == lastop_a || '-' ==lastop_a)58 expr[i] = exprb + '-' + '(' + expra + ')';59 else expr[i] = exprb + '-' +expra;60 lastop[i] = '-';61 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)62 ||res;63 }64

65 cards[i] = a *b;66 if('-' == lastop_a || '+' ==lastop_a)67 expr[i] = '(' + expra + ')' + '*';68 else expr[i] = expra + '*';69 if('*' == lastop_b || ' ' ==lastop_b)70 expr[i] +=exprb;71 else expr[i] += '(' + exprb + ')';72 lastop[i] = '*';73 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)74 ||res;75

76 if(b != 0)77 {78 cards[i] = a /b;79 if('-' == lastop_a || '+' ==lastop_a)80 expr[i] = '(' + expra + ')' + '/';81 else expr[i] = expra + '/';82 if(' ' ==lastop_b)83 expr[i] +=exprb;84 else expr[i] += '(' + exprb + ')';85 lastop[i] = '/';86 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)87 ||res;88 }89

90 if(a != 0 && a!=b)91 {92 cards[i] = b /a;93 if('-' == lastop_b || '+' ==lastop_b)94 expr[i] = '(' + exprb + ')' + '/';95 else expr[i] = exprb + '/';96 if(' ' ==lastop_a)97 expr[i] +=expra;98 else expr[i] += '(' + expra + ')';99 lastop[i] = '/';100 res = GameRecur_all(cards, expr, lastop, cardsNum-1, result)101 ||res;102 }103

104 //把选出来的两个数放回原位

105 cards[i] =a;106 cards[k] =b;107 expr[i] =expra;108 expr[k] =exprb;109 lastop[i] =lastop_a;110 lastop[k] =lastop_b;111 }112 }113 returnres;114 }115

116 //cards 输入的牌117 //cardsNum 牌的数目118 //result 想要运算得到的结果

119 void PointGame_all(int cards[], const int cardsNum, const intresult)120 {121 stringexpr[cardsNum];122 charlastop[cardsNum];123 doublecardsCopy[cardsNum];124 for(int i = 0; i < cardsNum; i++)125 {126 char buf[30];127 sprintf(buf, "%d", cards[i]);128 expr[i] =buf;129 lastop[i] = ' ';//表示cardsCopy[i]是不经过任何运算的原始数据

130 cardsCopy[i] =cards[i];131 }132 if(GameRecur_all(cardsCopy, expr, lastop, cardsNum, result) == false)133 cout<

View Code

算法2

算法2代码如下，集合用stl中的set表示，代码中变量名保持和书中一致

调用函数PointGame2即可返回表达式结果，调用方式同算法1

1 #include

2 #include

3 #include

4 #include

5 #include

6 #include

7 #include

8 using namespacestd;9

10 structsetNode11 {12 doubleval;13 string expr;//运算出val的表达式

14 setNode(double v, stringe):val(v),expr(e){}15 setNode(double v, chare[]):val(v),expr(e){}16 bool operator < (const setNode &s)const

17 {18 return val

22 void f(const int i, set s[], const doubleresult)23 {24 int len = sizeof(s)/sizeof(set) - 1;//len = 2^n - 1

25 if(s[i].empty() == true)26 for(int x = 1; x <= i/2; x++)27 if((x&i) ==x)28 {29 set::iterator it1, it2;30 //s[i] U= fork(s[x] ,s[i-x])

31 for(it1 = s[x].begin(); it1 != s[x].end(); it1++)32 for(it2 = s[i-x].begin(); it2 != s[i-x].end(); it2++)33 {34 stringexpr;35 doubletempresult;36 tempresult = it1->val + it2->val;37 expr = '(' + it1->expr + '+' + it2->expr + ')';38 s[i].insert(setNode(tempresult, expr));39 //计算f[2^n-1]时，若计算好了结果则可以停止

40 if(i == len && tempresult == result)return;41

42

43 tempresult = it1->val - it2->val;44 expr = '(' + it1->expr + '-' + it2->expr + ')';45 s[i].insert(setNode(tempresult, expr));46 if(i == len && tempresult == result)return;47 if(it1->val != it2->val)48 {49 tempresult = it2->val - it1->val;50 expr = '(' + it2->expr + '-' + it1->expr + ')';51 s[i].insert(setNode(tempresult, expr));52 if(i == len && tempresult == result)return;53 }54

55 tempresult = it1->val * it2->val;56 expr = '(' + it1->expr + '*' + it2->expr + ')';57 s[i].insert(setNode(tempresult, expr));58 if(i == len && tempresult == result)return;59

60 if(it2->val != 0)61 {62 tempresult = it1->val / it2->val;63 expr = '(' + it1->expr + '/' + it2->expr + ')';64 s[i].insert(setNode(tempresult, expr));65 if(i == len && tempresult == result)return;66 }67 if(it1->val != it2->val && it1->val != 0)68 {69 tempresult = it2->val / it1->val;70 expr = '(' + it2->expr + '/' + it1->expr + ')';71 s[i].insert(setNode(tempresult, expr));72 if(i == len && tempresult == result)return;73 }74 }75 }76 }77

78 string PointGame2(int cards[], const int cardsNum, const intresult)79 {80 int len = 1< S[len]; //对应文章中的数组S82 //初始化只有一个元素的子集，j = 2^i，即只有一个2进制位是1

83 for(int i = 0, j = 1; i < cardsNum; i++, j = j<<1)84 {85 char buf[30];86 sprintf(buf, "%d", cards[i]);87 S[j].insert(setNode(cards[i],buf));88 }89 for(int i = 1; i <= len - 1; i++)90 f(i, S, result);91 for(set::iterator it = S[len-1].begin();92 it != S[len-1].end(); it++)93 {94 if(it->val ==result)95 return it->expr;96 }97 return "-1";98 }

View Code