1.研究介绍：
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
2.算法分析 ：
首先我们要对这个问题进行数学抽象。
定义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) ，其算法伪代码如下：
算法1
function f(S)
begin
1. if |S| < 2
2. then return S
3. else begin
4. T ← Φ
5. for each (r1, r2) in S do
6. 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) 就是所求。
上一篇：EJB分布式技术在网络教学的毕业设计
下一篇：Delphi初学者参考外文翻译