计算机问题求解 – 论题1-4 - 基本的算法结构 2018年10月09日
Part I Loop and if-then-else
问题1： 什么是“control structure”? Paramount: of highest rank of importance
问题2: 你会吃蟹黄汤包吗? 轻轻提, 慢慢移, 先开窗, 再喝汤。
吃一只蟹黄汤包的“算法” 顺序很重要： 将包子从蒸笼中轻轻提起，and then 将包子慢慢移动到面前的小碟子中，and then 将包子送入口中。 完成！
问题3： 你如何确保过程无误？ 假如我们认为在步骤4和5执行前要确保前面的结果是正确的，可以在相应的地方设个“监视哨” – “guard”。
问题4： 但是我们并不只是吃 一只，那怎么办呢？
策略一：吃饱为止 是否已饱？ 是 否 上下颠倒 问题5： 如果即使饱了，也希望至少品尝一只，该怎么办？
策略二：控制数量 开始 假如规定吃8只： 注意： 这个过程的“结构”与计数器的初始值没有关系！ 否 是 结束 设一个计数器，并将其值设定为0。 吃一只汤包 此框的内容即前面的顺序操作序列 否 计数器值加1，并判断其是否为8 是 结束
如何确定循环过程是正确的？ 问题6： 你能为上述两种吃蟹黄汤包的策 略选定一个循环不变式吗？ 循环不变式(量) 这是一个逻辑表达式 在循环执行过程它应该始终为“真” 例如：用一个逐项累加的循环计算a*b, 循环不变式可以是：“存放中间结果的量的值=a*“循环变量的当前值” 问题6： 你能为上述两种吃蟹黄汤包的策 略选定一个循环不变式吗？
Invariant: 也是解题的“利器” 太简单，没意思？
“冒泡”排序 – 循环的嵌套 当然我们没有必要每一趟都试探n-1次，那该如何优化呢？ 自下往上 这一段干的是什么事情?
是否可以将“冒泡”中 的内层循环表示成一个 procedure/subroutine, 形式上成为单层循环？ 问题7: 是否可以将“冒泡”中 的内层循环表示成一个 procedure/subroutine, 形式上成为单层循环？ Max(E, low, high): 找出指定范围内的最大元素
有人知道饱不饱，但有人不知道！ 问题8： 如果要判断的 不止是两种可 能，那怎么办？ 结束 开始 否 是 选用策略2 选用策略1 要吃汤包的人不到5岁吗？ 选用策略2 选用策略1 结束
分类定量控制 结束 开始 是 否 否 是 选用策略2(带参数) 要吃汤包的人不到5岁吗？ 要吃汤包的人超过60岁吗？ 参数设为2 选用策略1 参数设为4 选用策略2(带参数) 结束
Subroutine and Recursion Part II Subroutine and Recursion
一个复合结构的例子 两个指针各是什么含义？ 要解的问题: 累加所有工 资比自己的 顶头上司高 的员工的工 资总额。
对包含“money”一词的句子计数 搜索“money”一词 搜索句子结尾标记
问题9： 前面的例子中“搜索”两次， 尽管对象不同，动作确是一样 的，有可能只描述一次吗？ 回想一下前面讨论“冒泡”排序时提出的问题？
问题10： 你能总结一下采用 subroutine的好处吗
关于“Goto” 问题11： 你理解下面的话吗？
如果从循环外goto到这里，会怎么样呢？ …或者，从这里“跳”出去？
从“归纳”到“递归” 归纳： 递归： “假如”这个结论对k-1是成立的，我试图证明它对k也是成立的。 如果我做到了，就可以认为（当然考虑到“奠基”）对任意不小于奠基值的自然数结论都成立。 递归： “假如”有“人”能帮我解决规模为k-1的问题“实例”，我就试图用那个结果来解该问题规模为k的“实例” 如果我做到了，就可以认为（当然也得给个“base case”的解法）我解了这个问题。 但是…
Hanoi Tower – Easy or Difficult? 还记得前页上那个“但是”吗？ 但是，“那个结果”在哪儿呢？
你看到的算法 这才是“真实”的执行过程！
问题12： 你能比较一下递归方法与数 学归纳法吗？ 为什么计算机出现之前只流行数学归纳法，却没有广泛使用的“递归解题法”？
问题13: 什么是Expressive Power of Control Structures？
课外作业 DH: 2.1-2.8 解那个关于大盒子套小盒子的问题