Skip to content

Latest commit

 

History

History
38 lines (37 loc) · 2.86 KB

chapter5.md

File metadata and controls

38 lines (37 loc) · 2.86 KB

复习题5.5

  1. 用您自己的话,讲述递归思想对解决汉诺塔问题的必要性。(为什么递归能解决汉诺塔问题)
    • 汉诺塔问题能被分解为形式相同的子问题,且不破坏汉诺塔的移动规则;
    • 汉诺塔存在一个最简单的情景,能被轻易地解决。
  2. 在下面的解决汉诺塔问题的递归策略中存在什么错误:
    • 将最上面的圆盘从起始座上移动到临时座上;
    • 将剩下的N-1个圆盘从起始座上移动到终点座上;
    • 将放在临时座上的圆盘移回到重点座上。
      • 小圆盘上不能放大圆盘,先移动N-1,就有两个柱子可以移动。如果先移动最上面的圆盘,对后来的N-1来说就只有一个空柱子,另一个柱子被一开始移动的小圆盘占据,无法使用。
  3. 如果调用 MoveTower(16, 'A', 'B', 'C') 那么第一次调用MoveSingleDisk函数时会出现什么样的情形呢?该解决方案的最后一步是什么?
    • 第一次调用为MoveSingleDisk('A', 'C');会将最上层圆盘从A移动到C
    • 解决方案的最后一步是MoveSingleDisk('C', 'B')会将临时柱上的圆盘移动到B
  4. 什么叫排列?
    • 从n个不同元素中取出m(m<=n)个元素,按照一定顺序拍成一列
  5. 用您自己的话,解释递归思想对于枚举某个字符串中字母所有排列的必要性。
    • 字符串中的每一个字符可以被看做一个元素;
    • 排列字符串实际上能被分解为x个排好的元素与n-x个未排好的元素;
    • 存在最简单的情景,即所有字母都已经被排列完毕;
    • 每一个字符串都可看作排列好的字符和没排列好的字符。
  6. 对于字符串”WXYZ“来说,有多少种排列?
    • A44 = 24
  7. 为什么在排列问题中,ListPermutations和RecursivePermute函数两者都必须定义?
    • 因为ListPermutations的参数是string,而我们将问题分解为了排列好的字符和未排列好的字符,这与原问题不对称,所以需要RecursivePermute完成我们分解后的问题,而ListPermutations作为包装器。
  8. 在绘图窗口中,原点位于什么地方?
    • 绘图窗口最左下角像素原点处。
  9. 绝对坐标和相对坐标有什么区别?
    • 绝对坐标以原点处进行运算,相对坐标以上一次停下的位置进行运算。
  10. 说出graphics.h库中的8个函数。
    • InitGraphics, MovePen, DrawLine, DrawArc, GetWindowWidth, GetWindowHeight, GetCurrentX, GetCurrentY
  11. 在什么简单情境下,能结束mondrian.c函数中的递归?
    • 生成的矩形面积小于设定值
  12. 画一副1级koch雪花图形。
  13. 在2级koch雪花图形中有多少条线段?
    • 48
  14. 从调用者的角度,描述函数DrawPolarLine的作用?
    • 画与x周逆时针夹角为theta方向长度为r的线段,并将绘图点移动至线段末尾。