编码任务
假设有一个池塘,里面有无穷多的水。现有2个空水壶,容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水(最后,这三升水,在其中一个壶里)

分析

显然,水壶的容积必须为正数,目标水量必须非负,且不能超过容量大的那个水壶的容积。如果目标水量及两个水壶的容积分别用 t、a、b 来表示,则必须有 a > 0, b > 0, 0 ≤ t ≤ max(a, b)。另外,t、a、b 三个量必须可公度,它们可以是有理数。如果都乘以分母的最小公倍数,即可化为整数。因此,我们仅需考虑 t、a、b 都是整数的情形。

令 d 是 a 和 b 的最大公约数。由于 a 和 b 都是 d 的倍数,如果 t 不是 d 的倍数,把 d 升水考虑为 1 份水,可知原题无解。另一方面,数论中有一个定理1,方程 ax + by = t 有整数解 x, y,当且仅当 t 是 d 的倍数。因此,如果 t 是 d 的倍数,按照欧几里得算法的步骤,原题可解。

  1. 参见“最大公约数与欧几里得算法”中的定理25

Scheme

Lisp 是第一个函数式程序设计语言,已经使用了半个世纪。在现存的活语言里,只有 Fortran 比它的寿命更长些。这两种语言都支持着一些重要领域中的程序设计需要,Fortran 用于科学与工程计算,Lisp 用于人工智能。这两个领域现在仍然很重要,它们的程序员都如此倾心于这两种语言,因此,Lisp 和 Fortran 都还可能继续生存至少半个世纪。

Scheme 是 Lisp 两种主要的方言之一(另一种为 Common Lisp)。它的精简性与优雅的语法广受计算机科学教育者以及语言设计学者的欢迎,并经常被用于基础计算机科学教育上。麻省理工学院与其他院校曾利用 Scheme 教授入门课程,著名的入门教材《计算机程序的构造和解释》(SICP,或称“魔法书”)就是利用 Scheme 来解释程序设计。

我这里用的是 MIT/GNU Scheme,可到官网 http://www.gnu.org/software/mit-scheme 下载 GNU/Linux、OS X 和 Windows 等平台的安装包。

两只水壶程序

言归正传,解释一下我的 Scheme 程序:

主函数 pot 的三个参数 t a b 分别是目标水量及两个壶的容积。

函数 solve 用于解题,参数 p q 是两个壶的当前水量。
(嵌套函数 x,计算从 A 壶最多能往 B 壶倒多少水)
函数 solve 首先打印当前水量;
如果当前水量等于目标水量,成功;
否则,如果 A 壶空,则装满它;
否则,如果 B 壶满,则清空它;
否则,尽可能地从 A 壶往 B 壶倒水;
递归地调用以上步骤即可完成解题。

主函数 pot 首先判断输入的参数 t a b 是否超出允许范围;
接着根据目标水量是不是两个壶的容积的最大公约数的倍数判断是否有解;
现在可以置两个壶的初始水量为零,调用函数 solve 0 0 开始解题。

(define (pot t a b)
  (define (solve p q)
    (define x (min p (- b q)))
    (display " -> ") (display p) (display " ") (display q) (newline)
    (cond ((or (= p t) (= q t)) (display "------- OK! ------"))
      ((= p 0) (display "Fill A full") (solve a q))
      ((= q b) (display "Empty pot B") (solve p 0))
      (else (display "Pour A to B") (solve (- p x) (+ q x)))))
  (cond ((or(< a 1)(< b 1)(< t 0)(> t (max a b))) (display "Arg out of range"))
    ((not (= (remainder t (gcd a b)) 0)) (display "No solve!"))
    (else (display "Start with ") (solve 0 0)))) 

以目标水量 3,两个壶的容积分别为 5 和 6 为参数调用 pot 的结果如下:

(pot 3 5 6)

Start with  -> 0 0
Fill A full -> 5 0
Pour A to B -> 0 5
Fill A full -> 5 5
Pour A to B -> 4 6
Empty pot B -> 4 0
Pour A to B -> 0 4
Fill A full -> 5 4
Pour A to B -> 3 6
------- OK! ------

美国人的火箭发射系统

上世纪七十年代,前苏联情报机构克格勃对美国太空技术软件发生了浓厚的兴趣,派遣了各种各样的间谍搜集任何可能的相关信息。

一天下午,一个间谍气喘吁吁的回到总部,手里拿着一张纸,兴奋的对着他的上司叫喊,“同志!同志!美国人的火箭发射系统是用 Lisp 语言编写的!”

长官很疑惑:“你怎么知道的?”

“我闯进了他们的研究室,从他们的电传机上偷了一张纸!这上面不是整个程序,只是最后一页,记录了程序的结束部分!你自己看!!!”

长官看着这张纸笑了:

))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

倾情推荐