算法思路

計算24點，可以抽象描述為：求代數(shù)系統(tǒng)<Real;+,-,*,/>的子系統(tǒng)<SInteger;+,-,*,/>的所有運算結(jié)果為24的運算。一般情況下<SInteger;+,-,*,/>有很多性質(zhì)，如交換律,i+j=j+i,結(jié)合律，i+(j+k)=(i+j)+k等等，為了使我這個惰人寫代碼方便，我去掉所有規(guī)律（這樣使運算量加幾倍了，呵呵，相信可以用來烤機了），并加上一個一元運算符~，~I=I I屬于SInteger,再加上一個似乎破壞了數(shù)學完美性的規(guī)則，SInteger中的元素在一個運算中只能用一次，如果不加這個"所有運算"將會是一個無限集.

第三代語言不能直接操作集合，所以要作一下轉(zhuǎn)化，想辦法把作用在代數(shù)系統(tǒng)<{a,b,c};+,-,*,/>的所有運算（a+b*c,a-b*c,a+b/c,(a+b)*c........）用別的方法表示。

下面我用O表示二元運算符，Oi表示第i個二元運算符。用[<{{a},{b,c}}；Oi>]表示{aO1b,aO2b,aO3b,aO1c,aO2c,aO3c....}，也就是返回作用在集合{a},{b,c}笛卡爾積上的運算結(jié)果。

[<{a}；~>]表示{a},也就是返回作用在集合上的運算結(jié)果。記得上面我去掉了很多性質(zhì)嗎，所以可能a+b不等于b+a,因此我要把a+b+c與c+a+b都要計算一次，而不是推出來.下面是用[<，； >]描述"作用在代數(shù)系統(tǒng)<{a,b,c};+,-,*,/>的所有運算".

[<[<{a};~>],[<[<{b};~>],[<{c};~>]；Oi>]；Oi>]

[<[<{a};~>],[<[<{c};~>],[<{b};~>]；Oi>]；Oi>]

[<[<{b};~>],[<[<{a};~>],[<{c};~>]；Oi>]；Oi>]

[<[<{b};~>],[<[<{c};~>],[<{a};~>]；Oi>]；Oi>]

.........

[<[<{a};~>],[<[<{b};~>],[<{c};~>]；+,->]；+,->]=

[<[<{a};~>],[<{b},{c}；+,->]；+,->]=

[<[<{a};~>],{(b+c),(b-c)}；+,->]=

[<{a},{(b+c),(b-c)}；+,->]=

{a+(b+c),a+(b-c),a-(b+c),a-(b-c)}

.......................

是不是發(fā)現(xiàn)很多重復，可能我上面說的運算量加幾倍了太保守了，最起碼也是個代數(shù)級數(shù)式的增加.

經(jīng)過一輪對數(shù)學世界的破壞，終于使問題對計算機來說簡化了。

記得上一次上數(shù)學課都是兩年前了，不知上面的內(nèi)容表達得是否正確。

• 繪制類圖

上面很多地方提到集合，第三代語言操作集合的最有效方法當然是使用Itertor模式，所以先定義一個TIterator基類，以后的集合都是它的子類。

觀察[<，； >]，它由三部分組成(一元運算只有二部分)，逗號左邊，逗號右邊，分號右邊，其中逗號左右都是一個[<，； >]，分號右邊是運算符，現(xiàn)在把[<，； >]轉(zhuǎn)化為一個類TNode.分號右邊是一系列運算符，因此使用TOperatorIterator表示。

我是用[<，； >]描述"作用在代數(shù)系統(tǒng)<{a,b,c};+,-,*,/>的所有運算".觀察上面，“代數(shù)系統(tǒng)<{a,b,c};+,-,*,/>的所有運算”是由多個[<，； >]的并集表示,因此又需要一個TIterator,命名為TTreeIterator.下面就是用ModelMaker 6.2繪制的類圖

其中的TTreeBuilder是用來構(gòu)建TNode的，如創(chuàng)建一個：[<[<{a};~>],[<[<{b};~>],[<{c};~>]；Oi>]；Oi>]

IClientInterface是一個最小化的界面，大部分二次開發(fā)的人員都不會想與復雜的內(nèi)部結(jié)構(gòu)打交道。

• 繪制順序圖

做到這里時我就想描述內(nèi)部的工作流，活動圖是一種不錯的方法，考慮到RUP的開發(fā)方式(主要是我只會一點點UML)，所以決定還是先畫個順序圖，可是畫完順序圖后，代碼就寫出來了，可能這個問題過于簡單，有機會我想找個復雜的問題。順序圖中我用了一些不太標準的表示方法，用來描述函數(shù)的返回。

（為了整體布局，我把圖縮小了，有點失真，請用看圖工具打開這張圖)

這是一個取[<，； >]中所有計算結(jié)果的順序圖。Actor首先通知TNode重新開始(Resume),跟著取第一個運算的運算結(jié)果（Eventuate，{a+(b+c),a+(b-c),a-(b+c),a-(b-c)}中的a+(b+c) )，再用Evaluate評估是否還有運算式（當還有運算符時，代表還有運算式,當然首先要檢查逗號兩邊的[<，； >]，如果它們有表達式，哪一定就是有表達式存在，沒必要看當前是否還有運算符），如果有評估為真，哪繼續(xù)用Eventuate取結(jié)果。“繼續(xù)”寫起來容易，但畫就難了，我在ModelMaker中找不到相應(yīng)循環(huán)符號,所以用了一條豎線表示范圍，用文本表示退出條件。

下面是我對著這個圖寫出來的怪怪代碼:

function TNode.Evaluate: Boolean;
var
LeftBool, RightBool: Boolean;
begin
Result:=false;
if (FLeftChild=nil) And (FRightChild=nil) then
begin
Result:=not FOperatorIterator.IsDone;
if Result then
FOperatorIterator.Next;
Exit;
end;

LeftBool:=FLeftChild.Evaluate;
if LeftBool then
begin
Result:=true;
Exit;
end;

RightBool:=FRightChild.Evaluate;
if Rightbool then
begin
FLeftChild.Resume;
Result:=true;
Exit;
end;

if not FOperatorIterator.IsDone then
begin
FOperatorIterator.Next;
FLeftChild.Resume;
FRightChild.Resume;
Result:=true;
Exit;
end;

end;

是不是感覺怪怪的。

(FLeftChild=nil) And (FRightChild=nil)這句檢測這是否一個只有一元運算符的[<； >]。

看到這里，大家應(yīng)該明白它們之間的對應(yīng)關(guān)系了吧

"作用在代數(shù)系統(tǒng)<{a,b,c};+,-,*,/>的所有運算(別忘了加上一個破壞規(guī)則，)"是一個很大的集合，

分成多個子集，分別為

+,-,*,/作用有元組(a,b,c)上

+,-,*,/作用有元組(a,c,b)上

+,-,*,/作用有元組(b,a,c)上

.............

再從這些子集中把每個元素提取出來。

+,-,*,/作用有元組(a,b,c)上用TNode表示,哪全集用TTreeIterator表示，下面就是與它相關(guān)的順序圖

function TClientInterface.GetAnswer(aNumArr:IntArray): TStringList;
var
FResult:TStringList;
TI: TTreeIterator;
ND: TNode;
Num:Double;
function GetResult:TStringList;
begin
if not Assigned(FResult) then
FResult:=TStringList.Create;
Result:=FResult;
end;
begin
{ TODO -cMM : Interface wizard: Implement interface method }
FResult:=nil;
TI:=TTreeIterator.Create(aNumArr);
TI.First;
while true do
begin
ND:=TI.CurrentItem;
ND.Resume;
repeat
try
Num:=ND.Eventuate;
if TCheck.Check(Num) then
GetResult.Add(ND.except
//捕捉零除異常
end;
until (not ND.Evaluate);
if TI.IsDone then Break;
TI.Next ;
end;
Result:=FResult;
end;

Actor從TTreeIterator中取一個子集，再取子集的所有元素，取完元素后，再取一個子集一直循環(huán)下去。

可能大家看完一本UML書后，也找不到幾個資源釋放的字樣，這應(yīng)該是技術(shù)發(fā)展的走勢，就像今天沒人會考慮640的限制，所以我在代碼里也沒寫這部分，我希望學習的是未來的技術(shù)。

• 使用ModelMaker的一些經(jīng)驗

1. 更改了源代碼后一定要按以保持與Model的同步，如果忘記了可能會見到這個對話框

這時最好按NO，如是按了YES，可能你在Delphi中辛苦寫的代碼就被刪了。如果覺得經(jīng)常用Refresh in Model很煩，可以在下面這里保持同步

2.這應(yīng)該是一個BUG

ModelMaker中的組合與聚合關(guān)系竟然是一樣的線，要注意一下，別理解錯誤了.

3.又是一個BUG

ModelMaker中的Singleton模式竟然產(chǎn)生錯誤代碼,我本來想在TMonitor使用這個模式。

class function TForm1.accessInstance(Request: Integer): TForm1;

const FInstance: TForm1 = nil;

begin
case Request of
0 : ;
1 : if not Assigned(FInstance) then FInstance := CreateInstance;
2 : FInstance := nil;
else
raise Exception.CreateFmt('Illegal request %d in AccessInstance',
[Request]);
end;
Result := FInstance;
end;

ModelMaker帶的設(shè)計模式不多，也是一大缺陷。Pascal語言似乎沒意增加<Template>，操作符重載這兩個有用的特性，哪設(shè)計模式的使用量相信將會增加，ModelMake應(yīng)該增強這一點。

文章很多地方帶有個人觀點，有些描述也不知是否標準化，作者也找不到標準化的例子，希望大家只須了解作者的思想，不必要管哪些表示方法。

源碼下載