代数方法求,速度又提高n个数量级,呵呵。
[问题的提出]
问题: 一个庙,100个和尚,100个馒头,大和尚一人吃3个、中和尚一人吃2个、小和尚3人吃一个,请问大、中、小和尚编制分别多少个?
探讨:用lisp求解、运行的方法和速度。
前面偶在8楼首先提出用二层循环替代三层循环的办法后,程序运行时间已经从xx秒精简到0.0x秒,原因是什么?循环少了,计算量将大大减少。不是一点点,而是呈n个数量级的减少,这个可以从aeo提出的计算量统计方法得出。那么还有没有更快的办法?我不禁问自己。
于是,新的解决方案在我脑海中蠢蠢欲动,终于忍不住浮出水面,破壳而出。(待续,先去买包烟...)
要大大提高运行效率,仅仅改变对程序函数的选用(如repeat,while,foreach,mapcar等)是不够的,关键在于改变程序的结构,如何使得经过一层循环就能得出我们想要的结果呢?aeo提出了一个问题,程序循环结构中:从中和尚开始循环比从大和尚开始循环要慢,那么,从小和尚开始呢?(请大家思考20秒钟…)
现在,我们已经得出了三个好的问题:
1. 能否一层循环就解决问题?
2. 从小和尚开始循环是否会更快?
3. 已知小和尚的数目,中和尚,大和尚的数目是确定的么?
有人说,提出一个好的问题胜于解决一个难的问题。(如果没有人承认说过,那就算是我说的啦,哈哈,不好意思J)
[解决方案]
经过简单的思考,我得出以下结论:
1. 小和尚必然是3的倍数,而且不可能太少(否则100个馒头不够分的)
2. 小和尚的数目确定了,中和尚大和尚的数目也确定了,由如下两个方程式可求解:
a+b+c=100
3a+2b+c/3=100
(注:a=大和尚数目,b=中和尚数目,c=小和尚数目)
3. 从小和尚循环,可以一层循环就得出结果,循环可以从1开始至100,但是有很多是不可能的,可以通过计算求出小和尚可能的数目范围。通过如下公式:
(1) a+c=100 ; 3a+c/3=100
(2) b+c=100 ; 2b+c/3=100
两个公式即求出小和尚可能的数目范围,本题为60~75。又,中、大和尚数目不可能为0且小和尚数目只能以3递增,所以实际范围为:63~72。
[编程解析]
经过以上分析,通过一层循环求解是可能的。程序如下:

- ;| 和尚分饼-----by 狂刀 2005.10.11
- 问题: 一个庙,100个和尚,100个馒头,大和尚一人吃3个、中和尚一人吃2个、小和尚3人吃一个,请问大、中、小和尚编制分别多少个?
- 探讨:用lisp求解、运行的方法和速度。
- |;
- (defun c:tt (/ n1 n2 a b c i)
- (setq n1 (/(- (* 2 3 100)(* 3 100))(1- (* 2 3)));;=60
- n2 (/(- (* 3 3 100)(* 3 100))(1- (* 3 3)));;=75
- c n1);;求n1,n2可简化,在此按公式代入方便理解。
- (repeat (setq I (1-(/(- n2 n1) 3)));;循环次数减1
- (setq c (+ 3 c);;每次加3,因3个小和尚才分1个饼
- a (-(/(* 5 c)3)100);;根据代数公式得出,推导过程详附录1
- b (- 100 a c);;不用解释了吧?
- )
- (mapcar 'princ (list "\n大和尚: " a " 中和尚: " b " 小和尚: "c " 共分饼: " (+(* 3 a)(* 2 b)(/ c 3))));;检测是否正确
- )
- (princ "\n本次共计算")(princ I )(princ " 个单元")
- (princ)
- )
;;测试结果:
命令: tt
大和尚: 5 中和尚: 32 小和尚: 63 共分饼: 100
大和尚: 10 中和尚: 24 小和尚: 66 共分饼: 100
大和尚: 15 中和尚: 16 小和尚: 69 共分饼: 100
大和尚: 20 中和尚: 8 小和尚: 72 共分饼: 100
本次共计算 4 个单元
[测试速度]
二层循环已经将速度提高到0.0x数量级,甚至测出0.00的运算时间,一层循环就看不出结果了。将程序运行1000次才能看出结果。
比对测试程序:

- (defun c:ttt ()
- (setq *x!-time (getvar "cdate"))
- (repeat 1000 (c:tt))
- (setq tm (- (getvar "cdate") *x!-time)
- tm$ (rtos tm 2 8)
- )
- (mapcar '(lambda(x y / a)(princ (strcat (setq a (substr tm$ x 2)) y)) a) '(3 5 7 9) '("时" "分" "." "秒"))
- (princ)
- )
- ;; 用时: 00分03.13秒
以13楼aeo的程序(c:test)为例测试:

- (defun c:tests ()
- (setq *x!-time (getvar "cdate"))
- (repeat 1000 (c:test))
- (setq tm (- (getvar "cdate") *x!-time)
- tm$ (rtos tm 2 8)
- )
- (mapcar '(lambda(x y / a)(princ (strcat (setq a (substr tm$ x 2)) y)) a) '(3 5 7 9) '("时" "分" "." "秒"))
- (princ)
- )
- ;; 用时: 00分46.16秒
可见速度从46.16提升至3.13,是原来二层循环结构速度的0.0678 倍。
将(c:tt)和(c:test)程序中过程princ的显示部分屏蔽掉(行首加; ,aeo的要在;前加T),再测试
命令: ttt
00时00分00.03秒
命令: tests
00时00分03.95秒
排除计算机用于显示结果(princ,print)的过程,实际计算过程速度提高为:
命令: cal
>> 表达式: 3/395
0.00759494
即运行效率为原二层循环的0.00759494 倍。
[小结]
1. 初学lisp的朋友,经常注重函数的运用,而忽视了程序结构的设计,是大错特错的。
好的程序结构,可以使得效率大大提高,编程的乐趣也在于此,这就是所谓的“和别人的思路不一样”,思路不一样,程序的结构必然不同。(用不同的语言,lisp,vba,arx的效率也大相迳庭,从慢到快,在此不讨论)
2.批量依次处理一堆数据,常用的autolisp函数有:repeat,while,mapcar,foreach;(应用于vlisp的还有vlax-for,vlax-map-collection,暂不讨论)。其中repeat,while,mapcar,foreach函数本身的效率比对可参考eachy版主的相关帖子。在此特别指出while函数,在循环中有特别的用途,while有一个判断条件(而repeat,mapcar,foreach是无条件循环),当有一个测试数据条件不符合,即刻跳出循环、返回结果,这在处理大的数据、进行判断的时候是非常有用的,效率提高也是显而易见的。而当测试数据都满足while条件的时候,这几个函数效率上也有所的差别,但对比程序结构效率的提升,改变相对是很小的。从前面几个帖子也得出此结论。
3.本论题(不是本帖),建议已经入门的,有一定基础的lisp编程爱好者好好看看,其中各个帖子对函数的应用、程序的结构及解决问题的过程等等对提高编程水平是很有帮助的。
[附录1] 推表达式的过程:
a b c
a=0
;; n1
2*x+y/3=100
x+y=100
;
6x+y=3x+3y
3x=2y
5y=300
y=60
;
2*3*(100 - y)+y=3*100
(2*3*100-3*100)/(2*3-1)=y
;; n2
3*x+y/3=100
x+y=100
;
9x+y=3x+3y
6x=2y
8y=600
y=75
;;已知c,求a b
a+b+c=100
3a+2b+c/3=100
;
3a+2(100-c-a)+c/3=100
a=100-c/3-200+2c
a=(5c/3)-100
注:
1. 本文作者: 狂刀
2. 相关索引:
原帖: http://www.xdcad.net/forum/showt ... 2282653#post2282653
3. 本帖已经发到教学中心:
现提供word文件打包下载
4. 你可以转贴转载,但请保留作者信息及保持文章的完整性。.
时间: 2005.10.11 |