分享
 
 
 

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

王朝delphi·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

算法思路

计算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的一些经验

更改了源代码后一定要按

以保持与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应该增强这一点。

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

源码下载

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有