算法思路
计算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;varLeftBool, RightBool: Boolean;beginResult:=false;if (FLeftChild=nil) And (FRightChild=nil) thenbeginResult:=not FOperatorIterator.IsDone;if Result thenFOperatorIterator.Next;Exit;end;LeftBool:=FLeftChild.Evaluate;if LeftBool thenbeginResult:=true;Exit;end;RightBool:=FRightChild.Evaluate;if Rightbool thenbeginFLeftChild.Resume;Result:=true;Exit;end;if not FOperatorIterator.IsDone thenbeginFOperatorIterator.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;varFResult:TStringList;TI: TTreeIterator;ND: TNode;Num:Double;function GetResult:TStringList;beginif not Assigned(FResult) thenFResult:=TStringList.Create;Result:=FResult;end;begin{ TODO -cMM : Interface wizard: Implement interface method }FResult:=nil;TI:=TTreeIterator.Create(aNumArr);TI.First;while true dobeginND:=TI.CurrentItem;ND.Resume;repeattryNum:=ND.Eventuate;if TCheck.Check(Num) thenGetResult.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;begincase Request of0 : ;1 : if not Assigned(FInstance) then FInstance := CreateInstance;2 : FInstance := nil;elseraise Exception.CreateFmt('Illegal request %d in AccessInstance', [Request]);end;Result := FInstance;end;
ModelMaker带的设计模式不多,也是一大缺陷。Pascal语言似乎没意增加<Template>,操作符重载这两个有用的特性,哪设计模式的使用量相信将会增加,ModelMake应该增强这一点。
文章很多地方带有个人观点,有些描述也不知是否标准化,作者也找不到标准化的例子,希望大家只须了解作者的思想,不必要管哪些表示方法。
源码下载