游戏规则： 一副牌中去掉大小王，在剩下的52张牌中任意取四张。使用四则运算，使其最后结果为24.其中每张牌只能使用一次且A=1,J=11，Q=12，K=13。
　　　　　譬如 2,4,6,8 &------& &结果为 6/(4-2)*8=24;
算法思考： 首先，从宏观上说，这种问题都是遍历穷举。再看看运算符，其中+，* 都是没有顺序的。即（a*b=b*a）, 但是 -、/ 是有顺序的。那么假设都有顺序的。那么就可以统一处理了（最多效率低点，先解决问题。再考虑优化）。那么遍历所有a,b,c,d 以及 三次运算 。即A(4,4) *4*4*4 就是该算法的复杂度。（事实证明我错了。后面会讲到。）
　　　　　微观上，由于中间有除法，那么不能用int类型来储存数据了。需要用double或者float.每次运算都只有两个数运算。我们可用 Function CalcValue(float x,float y , char sy)来表示。x表示第一数，y表示第二个数， sy表示四则运算符之一。
　　代码如下：
public float CalcValue(float x, float y, char f)
float res = 0;
switch (f)
case '+': res = x +
case '-': res = x -
case '*': res = x *
case '/': res = x /
　　遍历代码如下
for (int i1 = 0; i1 & Nums.C i1++)//Nums 为4个数
List&float& Nums1 = CloneValue(this.Nums);
float num1 = Nums1[i1];//第一个数
Nums1.RemoveAt(i1);//移除第一数
for (int i2 = 0; i2 & Nums1.C i2++)//遍历剩下的3个数
List&float& Nums2 = CloneValue(Nums1);
float num2 = Nums1[i2];//第二个数
Nums2.RemoveAt(i2);
for (int i3 = 0; i3 & Nums2.C i3++)
List&float& Nums3 = CloneValue(Nums2);
float num3 = Nums2[i3];//第三个数
Nums3.RemoveAt(i3);
//第四个数,因为最后一个了。不要循环了。
float num4 = Nums3.First();
//即四个数的顺序为num4,num3,num2,num1;接下来遍历符号
for (int sy1 = 0; sy1 & 4; sy1++)//遍历第一的运算符号
char currentSymbol1 = symbols[sy1];
float tem1 = CalcValue(num4, num3, currentSymbol1);//第一个中间值
for (int sy2 = 0; sy2 & 4; sy2++)
char currentSymbol2 = symbols[sy2];
float tem2 = 0;
for (int dir = 0; dir & 2; dir++)//一开始没写这个循环。只计算了下面注释的部分。其实写程序到这里我就感觉不太对了。。后来验证果然不对。
if (dir == 0)
tem2 = CalcValue(tem1, num2, currentSymbol2);
if (dir == 1)
tem2 = CalcValue(num2, tem1, currentSymbol2);
// float tem2
= CalcValue(tem1, num2, currentSymbol2);
for (int sy3 = 0; sy3 & 4; sy3++)
char currentSymbol3 = symbols[sy3];
float tem3 = 0;
for (int dir2 = 0; dir2 & 2; dir2++)//同样。这个一开始没写。后来补的。
if (dir2 == 0)
tem3 = CalcValue(tem2, num1, currentSymbol3);
if (dir2 == 1)
tem3 = CalcValue(num1, tem2, currentSymbol3);
// float tem3 = CalcValue(tem2, num1, currentSymbol3);
if (tem3 == 24)//发现了计算
//下面的都是后来补的。所以导致程序很乱。
if (dir == 0 && dir2==0)//按顺序的
Console.WriteLine("{0}{1}{2}, {3}{4},{5}{6}", num4, currentSymbol1, num3, currentSymbol2, num2, currentSymbol3, num1);
if (dir == 1 && dir2==0)//第二次计算时 num2与temp四则运算
6/(4-2) * 8
Console.WriteLine("{3}{4},{0}{1}{2},{5}{6}", num4, currentSymbol1, num3, num2, currentSymbol2, currentSymbol3, num1);
if (dir==0 && dir2 == 1)// 最后次计算 num4与temp四则运算 如
Console.WriteLine("{6}{5}, ({0}{1}{2},{4}{3})", num4, currentSymbol1, num3, num2, currentSymbol2, currentSymbol3, num1);
if (dir==1 && dir2 == 1)//
如 8/(3-8/3)
Console.WriteLine("{6}{5}, {4}{3},{0}{1}{2}", num4, currentSymbol1, num3, num2, currentSymbol2, currentSymbol3, num1);
　　从遍历代码中发现。我们少考虑的点东西。 即并不是遍历所有abcd以及 运算的组合就行了。我们遍历的只是数出现的顺序。而并没有遍历所有表达式。
举个例子： ((a+b)-c)+d 和&(c-(a+b))+d &这两个表达式 都是 ab运算， 再和c运算，最后和d运算。 运算数的顺序是一样的,都是abcd，但是表达式不同。
也就是说，遍历数所有abcd的组合还不够。还需要添加一个顺序。计算的顺序。于是在遍历的程序中 多了两个for(dir=0;dir&2;dir++) 的循环。。。
重新思考： &看到计算表达式&((a+b)-c)+d&&，就想起大学时候的波兰表达式。 先去括号再说。ab+c-d+。很好很强大！！这个就能解决顺序的问题。不必先弄所有的数字的组合（带顺序的，A(x,x),不是C(x,x) ) 然后还要考虑 计算的顺序。。。。那么关键是有多少种符合的表达式类型呢？ 穷举！！！
改天再想吧。。。
罗列下待解决的问题： 效率问题。太多的重复判断。或许波兰表达式能解决。
　　　　　　　　　　 去括号后相同的表达式。。 譬如 a-(b+c)+d &与 a-b-c+d &是相同的。
阅读(...) 评论()24点游戏 判断4个数字能否组合成24点的算法 - 下载频道 - CSDN.NET
&&&&24点游戏 判断4个数字能否组合成24点的算法
&24点游戏 判断4个数字能否组合成24点的算法
判断4个数字能否通过加减乘除得到24 4点游戏 判断4个数字能否组合成24点的算法
若举报审核通过，可奖励20下载分
被举报人：
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：
您可能还需要
Q.为什么我点的下载下不了，但积分却被扣了
A. 由于下载人数众多，下载服务器做了并发的限制。若发现下载不了，请稍后再试，多次下载是不会重复扣分的。
Q.我的积分不多了，如何获取积分？
A. 获得积分，详细见。
完成任务获取积分。
评价资源返积分。
论坛可用分兑换下载积分。
第一次绑定手机，将获得5个C币，C币可。
下载资源意味着您已经同意遵守以下协议
资源的所有权益归上传用户所有
未经权益所有人同意，不得将资源中的内容挪作商业或盈利用途
CSDN下载频道仅提供交流平台，并不能对任何下载资源负责
下载资源中如有侵权或不适当内容，
本站不保证本站提供的资源的准确性，安全性和完整性，同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
课程资源下载排行
积分不够下载该资源
如何快速获得积分？
你下载资源过于频繁，请输入验证码
如何快速获得积分？
你已经下载过该资源，再次下载不需要扣除积分
24点游戏 判断4个数字能否组合成24点的算法
所需积分：3
剩余积分：
VIP会员，免积分下载
会员到期时间：日
剩余下载次数：1000
VIP服务公告:看书、学习、写代码
24点游戏题解
一、问题描述
80年代全世界流行一种数字游戏，在中国我们把这种游戏称为&24点&。现在我们把这个有趣的游戏推广一下：您作为游戏者将得到6个不同的自然数作为操作数，以及另外一个自然数作为理想目标数，而您的任务是对这6个操作数进行适当的算术运算，要求运算结果小于或等于理想目标数，并且我们希望所得结果是最优的，即结果要最接近理想目标数。您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是合法的，2*（2/4）是不合法的）
下面我们给出一个游戏的具体例子：若给出的6个操作数是：1，2，3，4，7和25，理想目标数是573；则最优结果是573：（（（4*25-1）*2）-7）*3。输入：输入文件名为game.in。输入文件仅一行，包含7个整数，前6个整数Mi,1&=Mi&=100，表示操作数，最后一个整数T, 1&=T&=1000,表示理想目标数。输出：输出文件名为game.out。输出文件有两行，第一行仅一个整数，表示您的程序计算得到的最优结果；第二行是一个表达式，即您得到的最优结果的运算方案。输入输出示例：输入文件1 2 3 4 7 25 573输出文件573((4*25-1)*2)-7)*3
二、算法分析
首先我们要对这个问题进行数学抽象。定义1：对于有理数组成的多重集合S ，f(S) 定义如下：
如果 S 是空集或只包含一个元素，则 f(S)=S ；
否则 f(S)=& f( ( S-{r1, r2}) & {r} ) ，对于每一个 r=r1+r2 , r1-r2 , r1&r2，r1&r2(r2&0)，且r1, r2取遍 S 中所有元素的组成的二元组。
定义1说明：要计算集合S中的元素通过四则混合运算所能得到的所有值，我们只需要任取 S 中的两个元素 r1 , r2 ，分别计算 r1 , r2 的加减乘除运算，然后用所得的结果与 S 中剩下的其他数字进行四则混合运算。只要取遍所有的 r1 ,r2 ，最后得到的所有结果的并集就是 S 中的元素通过四则混合运算所能得到的所有值的集合。根据上述定义，在本问题中，集合 S 就是由输入中给定的6个正整数组成的集合，题目所求就是找出 f(S) 中小于或等于目标数的最大数。
定义2：给定两个多重集合 S1 , S2，定义&&&&&&& comb( S1, S2 ) = & { r1+r2 , r1-r2, r1&r2, r1&r2(r2&0) }&&&&&& (1.1)其中 ( r1 , r2 ) & S1 & S2。定义2实际上定义了两个集合中的元素两两进行加减乘除运算所能得到的结果集合。
定理1：对于有理数组成的多重集合 S ，如果 S 至少有两个元素，则&&&&&&& f(S)=& comb( f(S1), f(S - S1) )&&&&&&&&&&&&&&&&&&&&& (1.2)其中 S1 取遍 S 的所有非空真子集。
定理1的含义是：要计算 S 中的元素通过四则混合运算所能得到的所有值，可以先将 S 分解为两个子集 S1 和 S- S1 ，分别计算 S1 和 S-S1 中的元素进行四则混合运算所能得到的结果集合，即 f(S1) 和 f(S-S1) ，然后对这两个集合中的元素进行加减乘除运算，即 comb( f(S1), f(S-S1) ) ，最后得到的所有集合的并集就是 f(S) 。限于篇幅，定理1的正确性易用数学归纳法证明。
定义1和定理1实际上分别给出了计算f(S)的两种不同的方法。根据定义1，可以递归地计算f(S) ，其算法伪代码如下：
function f(S) begin 1.& if |S| & 22.&&& then return S 3.&&& else begin 4.&&&&&&&&&& T & &P 5.&&&&&&&&&& for each (r1, r2) in S do6.&&&&&&&&&& begin 7.&&&&&&&&&&&& r & r1 + r2; 8.&&&&&&&&&&&& T & T + f(S & {r1, r2} + {r}); 9.&&&&&&&&&&&& r & r1 - r2; 10.&&&&&&&&&&& T & T + f(S & {r1, r2} + {r}); 11.&&&&&&&&&&& r & r1 * r2; 12.&&&&&&&&&&& T & T + f(S & {r1, r2} + {r}); 13.&&&&&&&&&&& if (r2 && 0) and (r1 mod r2 = 0) then 14.&&&&&&&&&&& begin 15.&&&&&&&&&&&&& r & r1 / r2; 16.&&&&&&&&&&&&& T & T + f(S & {r1, r2} + {r}); 17.&&&&&&&&&&& end 18.&&&&&&&&& end 19.&&&&&&&&& return T; 20.&& end end
上述伪代码中使用了+, - 来分别表示集合的并和差运算。算法1每次选择两个数字进行某种运算，然后将结果与剩下的数字递归地进行运算，最后求得所有数字进行四则混合运算的结果。当然，在具体实现该算法的过程中有很多可以优化的地方，比如根据加法交换律， a+b+c=a+c+b ，因此我们可以规定：如果上一层递归作了加法运算，这一层仅当满足当前的操作数大于上一层的两个操作数的时候才进行加法运算，以确保 a+b+c 这样的式子中的操作数总是从小到大排列，这样就可以避免重复进行等价的加法计算。类似地我们可以对乘法也作此规定。在进行减法的时候，我们可以规定只能计算大数减小数，因为最后所需计算得到的目标数是一个正数，如果计算过程中出现负数，肯定有另外一个较大的正数与其作加法或者有另外一个负数与其做乘除法以消除负号。因此我们总可以调整运算次序使得四则混合运算的每一步的中间结果都是正数。在作除法的时候，因为题目规定中间结果只能是整数，所以也只需要用大数除小数，且仅当能除尽的时候才进行除法。对于本题而言，初始的集合 S 中一共有6个操作数，每次递归都可以合并两个操作数，所以递归到第5层的时候集合 S 中只剩下一个数，这个数就是原先的6个操作数进行四则混合运算所能得到的结果。本题只要求最接近目标值的结果，所以实现上述算法的时候可以只记录当前最优的结果。对于本题也可以利用递归回溯构造出所有的四则混合运算的语法树，但本质上与算法1是没有区别的。
定理1则给出了另一种计算f(S)的方法。我们当然也可以根据(1.2)式直接地递归计算f(S)，但那样的话会有很多冗余计算。
例如对于S={1,2,3,4}，f(S) = comb( f({ 1 }), f({ 2,3,4}) )& ... & comb( f({ 1,2 }), f({3,4 }) ) & ...;
计算f(S)的时候需要计算 f({ 2,3,4 })和f({ 3,4 }) ，又因为&& f({2,3,4}) = comb(f({ 2 }), f({3,4})) & ...;在计算 f({ 2,3,4}) 的时候又要重复地计算 f({ 3,4 }) ，这就产生了冗余的计算。这种情况下直接地递归就不适用。必须按照一定的顺序，递推地进行计算。这种将递归改为递推，以解决冗余的算法设计策略，就叫做动态规划。下面我们具体阐述一下该算法的步骤。设初始时集合 S 中的 n 个数字分别为x[0], x[1],...,x[n-1] ，我们可以用一个二进制数k来表示S 的子集 S[k] ，x[i] & S[k] 当且仅当二进制数k的第i位为1。于是我们用一个数组 F[0..2^n-1]就可以保存函数f对于S的所有子集的函数值（注意，函数f的函数值是一个集合），且 F[2^n-1]=f(S) 就是所求。
1.& for i & 0 to 2^n-12.&&& do F[i]&&P; 3.& for i & 0 to n-14.&&& do F[2^i]& {x[i]}; 5.& for x & 1 to 2^n-1 do6.& begin 7.&&& for i & 1to x-1 do8.&&& begin 9.&&&&& if x&i=i then 10.&&&& begin 11.&&&&&& j & x & 12.&&&&&& if i & j 13.&&&&&&&& then F[x] & F[x] + comp(F[i],F[j]); 14.&&&& 15.&& 16.&&&&&&&&&&&&&&&&& 17. return F[ 2 n ?1] ;
上述伪代码中使用了+表示集合的并运算。算法2的第1～2行将F中所有的集合初始化为空；第3～4行中 2^i 即表示只包含元素 x[i]的子集（因为 2^i 只有第 i 位上是1），根据定义1我们知道当集合中只有一个元素的时候函数 f 的函数值就是那唯一的元素组成的集合，所以3～4行计算出了函数 f 对于所有只有一个元素的子集的函数值；第5～17行按照一定的顺序计算函数 f 对于 S 的所有子集的函数值。对于 S 的两个子集 S[i] 和 S[x] ， S[i]真包含于S[x]的充要条件是 x&i=i ，这里 & 是按位进行与操作，而 x&i=i 的必要条件是 i&x 。因而第7~15行的循环将S[x]拆成两个子集S[i]和S[j]，并在第13行根据(1.2)式计算所有的comp( f(S[i]),f(S[j]) ) 的并。第12行的判断语句是为了优化算法的效率，因为将 S[x]拆成两个子集 S[i]和 S[j]的过程是对称的，所以我们对于 comp(f(S[i]),f(S[j]) ) 和 comp( f(S[j]),f(S[i]) ) 两者只取一个进行计算。下面是函数comp的伪代码：
function comp(S1, S2) 1.& T & &P ; 2.& for each x in S1 do3.& begin 4.&&& for each y in S2 do5.&&& begin 6.&&&&& T & T + {(x + y)}; 7.&&&&& T & T + {(x * y)}; 8.&&&&& if x & y then 9.&&&&& begin 10.&&&&&& T & T + {(x & y)}; 11.&&&&&& if (y && 0) and (x mod y = 0) 12.&&&&&&&&& then T & T + {(x / y)}; 13.&&&& end 14.&&&& else begin 15.&&&&&& T & T + {(y & x)}; 16.&&&&&& if (x && 0) and (y mod x = 0) 17.&&&&&&&& then T & T + {(y / x)}; 18.&&&& 19.&& 20. 21. return T;
comp在进行计算的时候不考虑参数集合S1和S2的顺序，进行减法的时候始终用大数减小数，这样保证运算过程中不出现负数（这样做的理由前文已经阐明）。因为我们只关心最后的f(S)中最接近目标值的数字，并且题目只要求求出任何一组最优解，所以算法2中的集合不需要是多重集合，只要是一般的集合即可。换句话说，集合F[i]中所有的元素互不相同，重复出现元素的我们只保留其中一个。这样可以大大减少计算中的冗余。做了这样的处理后，算法2的效率至少不会比算法1差，因为算法1中所能采用的主要剪枝手段是排除等价的表达式，但因为等价的两个表达式计算出的结果也一定相同，而算法2排除了所有结果相同的表达式，所以算法2的效率至少不会比算法1差，算法2中所进行的计算基本上都是得到最优解所必需的计算。
在实现算法2的过程中，集合可以用一个链表加上一个哈希表来实现。链表中保存每个表达式及其值，哈希表用来记录该集合中是否存在某个特定值的表达式。当向集合中插入一个新的表达式的时候，首先检查哈希表，看看该集合是否已经有和新表达式值相同的表达式，如果有的话就不插入，否则将新的表达式追加到链表末尾。采用这种数据结构，可以在常数时间内完成集合的插入和删除操作。利用链表，集合的并操作也很容易高效地实现。
在实现算法2的过程中，可以不必保存表达式的字符串，只需要记录下当前的值是 由哪两个集合中的元素通过哪种运算得到的，最后再根据最优解递归地计算出最优 解的表达式。
这样只在最后构造最优解的表达式时才进行字符串操作，程序运行效率能提高7～8倍左右。另外，在comb函数中进行乘法运算的时候要注意考虑运算结果超出整数范围的情况经
过以上优化，利用算法2实现的程序对于100个随机生成的测试数据总共只需要5秒左右就可以出解，平均每个数据只需要50毫秒即可出解（测试用的CPU为赛扬1GB）。
这样的效率已经非常令人满意了。
三、附录：
1、根据算法1计算24点的代码 ：
#include &iostream&#include &string&#include &cmath&
const double PRECISION = 1E-6; const int COUNT_OF_NUMBER& = 4; const int NUMBER_TO_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_CAL) & PRECISION ) { &&&&&&&&&&& cout && expression[0] && &&&&&&&&&&& &&&&&&& } else { &&&&&&&&&&& &&&&&&& }&&& }
&&& for (int i = 0; i & i++) { &&&&&&& for (int j = i + 1; j & j++) { &&&&&&&&&&& double a, &&&&&&&&&&& string expa,
&&&&&&&&&&& 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 + &&&&&&&&&&& if ( Search(n - 1) )
&&&&&&&&&&& expression[i] = '(' + expa + '-' + expb + ')'; &&&&&&&&&&& number[i] = a - &&&&&&&&&&& if ( Search(n - 1) )
&&&&&&&&&&& expression[i] = '(' + expb + '-' + expa + ')'; &&&&&&&&&&& number[i] = b - &&&&&&&&&&& if ( Search(n - 1) )
&&&&&&&&&&& expression[i] = '(' + expa + '*' + expb + ')'; &&&&&&&&&&& number[i] = a * &&&&&&&&&&& if ( Search(n - 1) )
&&&&&&&&&&& if (b != 0) { &&&&&&&&&&&&&&& expression[i] = '(' + expa + '/' + expb + ')'; &&&&&&&&&&&&&&& number[i] = a / &&&&&&&&&&&&&&& if ( Search(n - 1) ) &&&&&&&&&&& }&&&&&&&&&&& if (a != 0) { &&&&&&&&&&&&&&& expression[i] = '(' + expb + '/' + expa + ')'; &&&&&&&&&&&&&&& number[i] = b / &&&&&&&&&&&&&&& if ( Search(n - 1) ) &&&&&&&&&&& }
&&&&&&&&&&& number[i] = &&&&&&&&&&& number[j] = &&&&&&&&&&& expression[i] = &&&&&&&&&&& expression[j] = &&&&&&& }&&& }&&& }
int main() { &&& for (int i = 0; i & COUNT_OF_NUMBER; i++) { &&&&&&& char buffer[20]; &&&&&&& int& &&&&&&& cin && &&&&&&& number[i] = &&&&&&& itoa(x, buffer, 10); &&&&&&& expression[i] = &&& }
&&& if ( Search(COUNT_OF_NUMBER) ) { &&&&&&& cout && "Success." && &&& } else { &&&&&&& cout && "Fail." && &&& }}
2、根据算法2计算解决题目的程序代码：
#include &fstream&#include &algorithm&#include &string&#include &sstream&#include &list&#include &cmath&#include &climits&#include &bitset&
const char* INPUT_FILE& = "game.in"; const char* OUTPUT_FILE = "game.out"; const int NUMBER_COUNT& = 7; const int STATE_COUNT&& = (1 && NUMBER_COUNT); const int MAX_NUMBER&&& = 100; const int MAX_EXPECTION = 1000; const int MAX_VALUE&&&& = MAX_EXPECTION * MAX_NUMBER;
struct Node { &&& &&& int left,&&&&&&& &&& int leftvalue, &&& };
typedef list&Node& NodeL
struct State { &&& bitset&MAX_VALUE+10& &&& NodeL };
int number[NUMBER_COUNT], State state[STATE_COUNT];
void ReadData() { &&& ifstream fin(INPUT_FILE);
&&& for (int i = 0; i & NUMBER_COUNT; i++) { &&&&&&& fin && number[i]; &&& }&&& fin && }
void Init() { &&& N &&& for (int i = 0; i & NUMBER_COUNT; i++) { &&&&&&& node.value&&&&&&&&&&&&& = number[i]; &&&&&&& node.left = node.right = -1; &&&&&&& state[(1 && i)].nodelist.push_back(node); &&&&&&& state[(1 && i)].exist[node.value] = &&& }}
void Merge(int a, int b, int x) {&&&&&& &&& N&&&&& &&& NodeList::const_iterator i,
&&& for (i = state[a].nodelist.begin(); i != state[a].nodelist.end(); i++){ &&&&&&& for (j = state[b].nodelist.begin(); j != state[b].nodelist.end(); j++){&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&& node.value = (*i).value + (*j). &&&&&&&&&&& node.left& = &&&&&&&&&&& node.right =&&&&&&&&&&&&&&&& &&&&&&&&&&& node.leftvalue& = (*i). &&&&&&&&&&& node.rightvalue = (*j). &&&&&&&&&&& node.opr&& = '+'; &&&&&&&&&&& if ( (node.value &= MAX_VALUE) && (!state[x].exist[node.value]) ) { &&&&&&&&&&&&&&& state[x].nodelist.push_back(node); &&&&&&&&&&&&&&& state[x].exist[node.value] = &&&&&&&&&&& }
&&&&&&&&&&& /////////////////////////////////////////////////////
&&&&&&&&&&& double tmp = double((*i).value) * double((*j).value);
&&&&&&&&&&& if (tmp & INT_MAX) { &&&&&&&&&&&&&&& node.value = (*i).value * (*j). &&&&&&&&&&&&&&& node.left& = &&&&&&&&&&&&&&& node.right = &&&&&&&&&&&&&&& node.leftvalue& = (*i). &&&&&&&&&&&&&&& node.rightvalue = (*j). &&&&&&&&&&&&&&& node.opr&& = '*'; &&&&&&&&&&&&&&& if ( (node.value &= MAX_VALUE) && (!state[x].exist[node.value]) ){ &&&&&&&&&&&&&&&&&&& state[x].nodelist.push_back(node); &&&&&&&&&&&&&&&&&&& state[x].exist[node.value] = &&&&&&&&&&&&&&& }&&&&&&&&&&& }
&&&&&&&&&&& /////////////////////////////////////////////////////
&&&&&&&&&&& if ((*i).value &= (*j).value) { &&&&&&&&&&&&&&& node.value = (*i).value - (*j). &&&&&&&&&&&&&&& node.left& = &&&&&&&&&&&&&&& node.right = &&&&&&&&&&&&&&& node.leftvalue& = (*i). &&&&&&&&&&&&&&& node.rightvalue = (*j). &&&&&&&&&&&&&&& node.opr&& = '-'; &&&&&&&&&&& } else { &&&&&&&&&&&&&&& node.value = (*j).value - (*i). &&&&&&&&&&&&&&& node.left& = &&&&&&&&&&&&&&& node.right = &&&&&&&&&&&&&&& node.leftvalue& = (*j). &&&&&&&&&&&&&&& node.rightvalue = (*i). &&&&&&&&&&&&&&& node.opr&& = '-'; &&&&&&&&&&& }
&&&&&&&&&&& if ( (node.value &= MAX_VALUE) && (!state[x].exist[node.value]) ) { &&&&&&&&&&&&&&& state[x].nodelist.push_back(node); &&&&&&&&&&&&&&& state[x].exist[node.value] = &&&&&&&&&&& }
&&&&&&&&&&& /////////////////////////////////////////////////////
&&&&&&&&&&& if ( ((*j).value != 0) && ((*i).value &= (*j).value) && ((*i).value % (*j).value == 0) ) &&&&&&&&&&& { &&&&&&&&&&&&&&& node.value = (*i).value / (*j). &&&&&&&&&&&&&&& node.left& = &&&&&&&&&&&&&&& node.right =&&&&&&&& &&&&&&&&&&&&&&& node.leftvalue& = (*i). &&&&&&&&&&&&&&& node.rightvalue = (*j). &&&&&&&&&&&&&&& node.opr&& = '/'; &&&&&&&&&&& } else if ( ((*i).value != 0) && ((*j).value &= (*i).value) && ((*j).value % (*i).value == 0) ) &&&&&&&&&&& { &&&&&&&&&&&&&&& node.value = (*j).value / (*i). &&&&&&&&&&&&&&& node.left& = &&&&&&&&&&&&&&& node.right = &&&&&&&&&&&&&&& node.leftvalue& = (*j). &&&&&&&&&&&&&&& node.rightvalue = (*i). &&&&&&&&&&&&&&& node.opr&& = '/'; &&&&&&&&&&& }
&&&&&&&&&&& if ( (node.value &= MAX_VALUE) && (!state[x].exist[node.value]) ){&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&&& state[x].nodelist.push_back(node); &&&&&&&&&&&&&&& state[x].exist[node.value] = &&&&&&&&&&& }&&&&&&&&&&& /////////////////////////////////////////////////////
&&&&&&& }&&& }}
void Solve() { &&& Init();
&&& for (int x = 2; x & STATE_COUNT; x++) { &&&&&&& for (int i = 1; i & i++) {&&&&&&&&&&&&&&&&&& &&&&&&&&&&& if ( (x & i) == i ) { &&&&&&&&&&&&&&& int j = x - &&&&&&&&&&&&&&& if (i &= j) { &&&&&&&&&&&&&&&&&&& Merge(i, j, x);&&&&&&&& &&&&&&&&&&&&&&& }&&&&&&&&&&& }&&&&&&& }&&& }}
void PrintExpression(ostream& out, Node node) { &&& if (node.left == -1) { &&&&&&& out && node. &&& } else { &&&&&&& NodeList::const_
&&&&&&& out && "(";
&&&&&&& for (iter = state[node.left].nodelist.begin(); &&&&&&&&&&& iter != state[node.left].nodelist.end(); &&&&&&&&&&& iter++) &&&&&&& { &&&&&&&&&&& if ((*iter).value == node.leftvalue) { &&&&&&&&&&&&&&& PrintExpression(out, *iter); &&&&&&&&&&&&&&& &&&&&&&&&&& }&&&&&&& }
&&&&&&& out && node.
&&&&&&& for (iter = state[node.right].nodelist.begin(); &&&&&&&&&&& iter != state[node.right].nodelist.end(); &&&&&&&&&&& iter++) &&&&&&& { &&&&&&&&&&& if ((*iter).value == node.rightvalue) { &&&&&&&&&&&&&&& PrintExpression(out, *iter); &&&&&&&&&&&&&&& &&&&&&&&&&& }&&&&&&& }
&&&&&&& out && ")"; &&& }}
void Output() { &&& ofstream fout(OUTPUT_FILE);
&&& int bestValue = -INT_MAX;&&&&&& &&& NodeList::const_iterator iter, bestI
&&& NodeList& nodelist = state[STATE_COUNT-1].
&&& for (iter = nodelist.begin(); iter != nodelist.end(); iter++) &&& {&&&&&& &&&&&&& if ( ((*iter).value &= expection) && (bestValue & (*iter).value) ) { &&&&&&&&&&& bestValue = (*iter). &&&&&&&&&&& bestIter& = &&&&&&& }&&& }&&& fout && bestValue && &&& PrintExpression(fout, *bestIter ); &&& fout && }
int main() { &&& ReadData(); &&& Solve(); &&& Output();&&& system("PAUSE"); &&& return 0; }
可以参考&编程之美&
阅读(...) 评论()