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