用面向对象方法解决24点问题

核心提示：算法思路 计算24点，可以抽象描述为：求代数系统<Real;+,-,*,/>的子系统<SInteger;+,-,*,/>的所有运算结果为24的运算，用面向对象方法解决24点问题，一般情况下<SInteger;+,-,*,/>有很多性质，如交换律,i+j=j+i,结合律，作者也找不到标

算法思路

计算24点，可以抽象描述为：求代数系统<Real;+,-,*,/>的子系统<SInteger;+,-,*,/>的所有运算结果为24的运算。一般情况下<SInteger;+,-,*,/>有很多性质，如交换律,i+j=j+i,结合律，i+(j+k)=(i+j)+k等等，为了使我这个惰人写代码方便，我去掉所有规律（这样使运算量加几倍了，呵呵，相信可以用来烤机了），并加上一个一元运算符~，~I=I I属于SInteger,再加上一个似乎破坏了数学完美性的规则，SInteger中的元素在一个运算中只能用一次，如果不加这个"所有运算"将会是一个无限集.

第三代语言不能直接操作集合，所以要作一下转化，想办法把作用在代数系统<{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}笛卡尔积上的运算结果。

[<{a}；~>]表示{a},也就是返回作用在集合上的运算结果。记得上面我去掉了很多性质吗，所以可能a+b不等于b+a,因此我要把a+b+c与c+a+b都要计算一次，而不是推出来.下面是用[<，； >]描述"作用在代数系统<{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)}

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

是不是发现很多重复，可能我上面说的运算量加几倍了太保守了，最起码也是个代数级数式的增加.

经过一轮对数学世界的破坏，终于使问题对计算机来说简化了。

记得上一次上数学课都是两年前了，不知上面的内容表达得是否正确。

• 绘制类图

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

观察[<，； >]，它由三部分组成(一元运算只有二部分)，逗号左边，逗号右边，分号右边，其中逗号左右都是一个[<，； >]，分号右边是运算符，现在把[<，； >]转化为一个类TNode.分号右边是一系列运算符，因此使用TOperatorIterator表示。

我是用[<，； >]描述"作用在代数系统<{a,b,c};+,-,*,/>的所有运算".观察上面，“代数系统<{a,b,c};+,-,*,/>的所有运算”是由多个[<，； >]的并集表示,因此又需要一个TIterator,命名为TTreeIterator.下面就是用ModelMaker 6.2绘制的类图

其中的TTreeBuilder是用来构建TNode的，如创建一个：[<[<{a};~>],[<[<{b};~>],[<{c};~>]；Oi>]；Oi>]

IClientInterface是一个最小化的界面，大部分二次开发的人员都不会想与复杂的内部结构打交道。

• 绘制顺序图

做到这里时我就想描述内部的工作流，活动图是一种不错的方法，考虑到RUP的开发方式(主要是我只会一点点UML)，所以决定还是先画个顺序图，可是画完顺序图后，代码就写出来了，可能这个问题过于简单，有机会我想找个复杂的问题。顺序图中我用了一些不太标准的表示方法，用来描述函数的返回。

（为了整体布局，我把图缩小了，有点失真，请用看图工具打开这张图)

这是一个取[<，； >]中所有计算结果的顺序图。Actor首先通知TNode重新开始(Resume),跟着取第一个运算的运算结果（Eventuate，{a+(b+c),a+(b-c),a-(b+c),a-(b-c)}中的a+(b+c) )，再用Evaluate评估是否还有运算式（当还有运算符时，代表还有运算式,当然首先要检查逗号两边的[<，； >]，如果它们有表达式，哪一定就是有表达式存在，没必要看当前是否还有运算符），如果有评估为真，哪继续用Eventuate取结果。“继续”写起来容易，但画就难了，我在ModelMaker中找不到相应循环符号,所以用了一条竖线表示范围，用文本表示退出条件。

下面是我对着这个图写出来的怪怪代码:

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)这句检测这是否一个只有一元运算符的[<； >]。

看到这里，大家应该明白它们之间的对应关系了吧

"作用在代数系统<{a,b,c};+,-,*,/>的所有运算(别忘了加上一个破坏规则，)"是一个很大的集合，

分成多个子集，分别为

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

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

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

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

再从这些子集中把每个元素提取出来。

+,-,*,/作用有元组(a,b,c)上用TNode表示,哪全集用TTreeIterator表示，下面就是与它相关的顺序图

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.PRint+'='+FloatToStr(Num));
except
//捕捉零除异常
end;
until (not ND.Evaluate);
if TI.IsDone then Break;
TI.Next ;
end;
Result:=FResult;
end;

Actor从TTreeIterator中取一个子集，再取子集的所有元素，取完元素后，再取一个子集一直循环下去。

可能大家看完一本UML书后，也找不到几个资源释放的字样，这应该是技术发展的走势，就像今天没人会考虑640的限制，所以我在代码里也没写这部分，我希望学习的是未来的技术。

• 使用ModelMaker的一些经验

1. 更改了源代码后一定要按以保持与Model的同步，如果忘记了可能会见到这个对话框

这时最好按NO，如是按了YES，可能你在Delphi中辛苦写的代码就被删了。如果觉得经常用Refresh in Model很烦，可以在下面这里保持同步

2.这应该是一个BUG

ModelMaker中的组合与聚合关系竟然是一样的线，要注意一下，别理解错误了.

3.又是一个BUG

ModelMaker中的Singleton模式竟然产生错误代码,我本来想在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带的设计模式不多，也是一大缺陷。Pascal语言似乎没意增加<Template>，操作符重载这两个有用的特性，哪设计模式的使用量相信将会增加，ModelMake应该增强这一点。

文章很多地方带有个人观点，有些描述也不知是否标准化，作者也找不到标准化的例子，希望大家只须了解作者的思想，不必要管哪些表示方法。

源码下载