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

类别:Delphi 点击:0 评论:0 推荐:

算法思路

计算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};~>],[<[<;~>],[<{c};~>];Oi>];Oi>]

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

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

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

.........

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

[<[<{a};~>],[<,{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};~>],[<[<;~>],[<{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的一些经验 更改了源代码后一定要按以保持与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应该增强这一点。

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

源码下载

 

本文地址:http://com.8s8s.com/it/it5476.htm