1.研究介紹：
80年代全世界流行一種數字游戲，在中國我們把這種游戲稱為“24點”�，F在我們 把這個有趣的游戲推廣一下：您作為游戲者將得到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初學者參考外文翻譯