信息科学系低年级讨论班.PDF

信息科学系 低年级讨论班 （4 ） 裘宗燕 北京大学数学学院信息科学系 2010年3月～6月 本科生讨论班报告（1） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/1 为“The Book”写程序 《代码之美》第33章 本科生讨论班报告（1） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/2 “The Book” Paul Erdos (例如：/group/topic/3017467/) 常说到“The Book” （或许可称为“天书”），里面包含着所有数学定理 的最优证明（Paul Erdos，一位与许多人合作的当代数学家） 本文作者提出“应该”也有一本算法和程序的“The Book”，里面包含所 有可计算问题的最优解决方案（及实现算法的最优程序） 作者的问题：我们能不能为这本书写一个程序？ 也就是说，针对一个问题写出一个不仅无懈可击，而且每个读者都只 能赞不绝口、高山仰止的程序 人都希望自己能创造出这样的算法艺术瑰宝，但 程序里常会有些瑕疵，有不如意之处 即使正确，也常有勉强和不自然之处、结构脆弱之处、逻辑较混乱的 特殊情况和例外情况 在这些方面努力，可能突然获得灵感，或通过别人工作的启发，得到一 个绝妙的可以写入“The Book”的程序 本科生讨论班报告（1） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/3 本文的问题 作者讲了自己的一个故事：不断追求最终写出了一个好程序 问题领域：计算几何。这里的情况和特点： 许多问题看似容易，深入之后会发现很麻烦 计算集合中的算法不是以象素为单位（不像图形学），而是理想化 的（像尺规作图）：点无大小，线宽为0，圆是精确的，等等 必须得到精确结果，一点不精确都可能改变整个计算的性质。例如 小数点后最低位的数字也可能逆转结果的性质 欧几里得说：几何无捷径。现在还加上效率。这里主要关心美学 问题：写一个函数，判断平面三点是否共线 似乎很简单，有许多数学上正确的方法 肯定有许多人做过 可以找别人的做法，但作者是自己考虑 本科生讨论班报告（1） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/4 Lisp 下面要给出函数的几个版本，都是用Lisp 写的 例：求最大公约数的欧几里得算法 (defun gcd (a b) (if (= b 0) a (gcd b (mod a b)))) 这个程序肯定在“The Book”里面 Lisp 采用括号括起的前缀表达式，括号里 第一个表达式表示操作，后面是操作对象 defun 定义函数，随后是函数名，参数表和函数体 if 是条件表达式，后面三项分别是条件和两个分支 本科生讨论班报告（1） 北京大学数学学院信息科学系 裘宗燕 2010年2月18 日/5 朴素算法（第一试） 用纸和笔计算（若目测不能确定）： 在纸上画出三个点 过两点画直线，看第三个点是否在线上 计算机上也可以这样做 需要选两个点画直线，怎样选择最好？为什么？ 请大家讨论 假设直线方程为y = mx + b ，假定三个点是p, q, r，用两点算方程，用 第三点坐标判断是否在线上，函数定义如下： (def