[转贴]：和尚与馒头问题

snoopychen

狂刀兄分析的很好
我也谈谈个人的一些小看法
碰到这个问题的时候,我想也不想的就编了4楼的程序
大概花2分钟,计算用3秒
我的思路是,硬算,这个可能是高手所不齿的,不过花的总时间最短
不过这样子遇到更大的问题有可能速度的平方增长的
所以,假如问题重复遇到的话,就必须研究算法

对于xyp版主提出的和尚馒头和字母求和.现在的感觉就是
利用一些简单的数学知识,可以大大减小计算时间

其实这道不定方程,就是
3X+2Y+Z/3=100  (1)
X+Y+Z=100      (2)
的正整数解

(2)*3-(1) 得到Y+8Z/3=200,这个表明Y可以用Z表示,

所以只要对Z进行+3循环,就可以依次得到Y值,按X=100-Y-Z,判断X是否正数,代入式子(1)看对否
这种应该就是一次循环吧

要是象狂刀兄缩小范围就更快了

初步感觉:
这种m个未知数和n个方程的,有无穷多解的,
(大概是线性代数中讲的非满秩相容线性方程组吧,不大记得了)
加上正整数之类的就是约束

假如m和n的数目相等的时候,肯定就可以用什么高斯消元法来作

假如m>n的时候,感觉最小的循环次数应该是m-n
比如4个未知数W X Y Z , 2个方程
那么只能化到W+X+Y=?,
此时的循环次数应该是4-2=2
需对X和Y循环得到W,再代入原始两条方程验算

学到了不少东西,不如以后编些经典题目,比如8皇后问题啊,华容道啊什么的:)

iVox

学习

winabcd

15楼的论述中，所表达的思想很好，看了后很有启示。

aeo

你的测试是不是太夸张了?
不要太自信了!

(while (<= (/ x 3) 100)
----就是我的repeat 33

(while (< (setq b (+ x x x y y)) 100)
---就是(repeat (/(- 100(* 3 x))2)

难道有什么错吗?
而且应该是repeat更快一些

2. 
   
3. (defun c:test( / x y z lst j)
   
4. (setq x 0 j 0.)
   
5. (repeat 33   ;大和尚
   
6.   (setq y 0)
   
7.   (setq lst(cons (/(- 100(* 3 x))2) lst))
   
8.   (repeat (/(- 100(* 3 x))2);中和尚
   
9.     (setq j(+ 1 j))
   
10.     (if(and(setq z(- 100 x x x y y)) ;小和尚的馒头
    
11.            (= 100(+ x y(* z 3)))
    
12.         )
    
13.        (mapcar 'princ(list "\n大中小分别是: " x "; " y "; "(* z 3)))
    
14.     )
    
15.     (setq y(1+ y))
    
16.   )(setq x(1+ x))
    
17. )
    
18. (princ(strcat "\n次数"(rtos j 2 10)))(princ)
    
19. )
    

<br /> (defun c:test( / x y z lst j)<br /> (setq x 0 j 0.)<br /> (repeat 33   ;大和尚<br />   (setq y 0)<br />   (setq lst(cons (/(- 100(* 3 x))2) lst))<br />   (repeat (/(- 100(* 3 x))2);中和尚<br />     (setq j(+ 1 j))<br />     (if(and(setq z(- 100 x x x y y)) ;小和尚的馒头<br />            (= 100(+ x y(* z 3)))<br />         )<br />        (mapcar 'princ(list "\n大中小分别是: " x "; " y "; "(* z 3)))<br />     )<br />     (setq y(1+ y))<br />   )(setq x(1+ x))<br /> )<br /> (princ(strcat "\n次数"(rtos j 2 10)))(princ)<br /> )<br />

850次

2. 
   
3. (defun c:xx (/ t1 x y z b d t2 h m s j)
   
4.   (setq j 0.)
   
5.   (setq x 0)
   
6.   (while (<= x 33)
   
7.     (setq y 0)
   
8.     (while (< (setq b (+ x x x y y)) 100)
   
9.       (setq j(+ j 1))
   
10.       (setq z (- 100 x y))
    
11.       (if (and (= 0 (rem z 3))
    
12.                (= 100 (+ b (/ z 3))))
    
13.           (mapcar 'princ (list "\n大和尚=" x " ; " "中和尚=" y " ; " "小和尚=" z))
    
14.       )
    
15.       (setq y (1+ y))
    
16.      )
    
17.     (setq x (1+ x))
    
18.   )
    
19.    
    
20.   (princ(strcat "\n"(rtos j 2 10)))(princ)
    
21. )
    

<br /> (defun c:xx (/ t1 x y z b d t2 h m s j)<br />   (setq j 0.)<br />   (setq x 0)<br />   (while (<= x 33)<br />     (setq y 0)<br />     (while (< (setq b (+ x x x y y)) 100)<br />       (setq j(+ j 1))<br />       (setq z (- 100 x y))<br />       (if (and (= 0 (rem z 3))<br />                (= 100 (+ b (/ z 3))))<br />           (mapcar 'princ (list "\n大和尚=" x " ; " "中和尚=" y " ; " "小和尚=" z))<br />       )<br />       (setq y (1+ y))<br />      )<br />     (setq x (1+ x))<br />   )<br />     <br />   (princ(strcat "\n"(rtos j 2 10)))(princ)<br /> )<br />

867次
其他地方速度不论，看次数就知道.

我上次是把表里的相乘了，其实应该相加.

狂刀

aeo版主先别着急，你没有看完我的15贴，15贴里面是另外一个程序：）！

eachy

执行程序前先 (gc)

FLOODITIDE

佩服各位的探索精神

cy956

比的精度已经不够体现，建议统一时间函数，用到纳秒级。还要统一提示和输出格式，才公平。呵呵.

yxpxa

不公平啊，运行的时间与电脑的配置有关系吧。P3的和P4的肯定相差较大。

xyp1964

最初由 yxpxa 发布
[B]不公平啊，运行的时间与电脑的配置有关系吧。P3的和P4的肯定相差较大。 [/B]

跑得再慢，百米速度比世界记录也不过差几秒！呵呵……

wuzz

其实斑竹提出此问题的真正用意是关于此问题的算法思想，而不是程序的执行时间问题，现在的电脑配置都比较高了，谁会在乎几秒的等待时间？

wujimmy

显示时间可以用这个函数,简捷
(princ (menucmd (strcat "M=$(edtime," (rtos (- t2 t1)2 16)  ",HH:MM:SS:MSEC)")))

旮旯酋酋长

我还以为什么轻松话题呢？

楚界

敬业的老师

wj518_0

谈的真多阿，我都看累了