1 | 对应本书第四章。 |
目录
笔记
第四章主讲递归,用了很多有意思的例子(可视化的),所以这章的作业会比较有料。
使用递归的三条件:
- 问题必须有基础情况;
- 问题必须可以被分解,直至基础情况;
- 递归算法必须自己调用自己。
例子:
下面的例子都用到了python的画图模块turtle,但貌似只是个toy,用于教学的,这里有一篇入门教程,随便看看。
1 | from __future__ import print_function |
1 | t.left(90) # 方向默认是朝右,向左九十度使其向正上方 |
- t.up()和t.down()是指画笔的起落,落下则行动中会留下轨迹,起来则行动不留痕迹;
- t.right(degree)和t.left(degree)调整乌龟的方向;
- t.forward(distance)和t.backward(distance)使乌龟前进后退;
- t.goto(x,y)使乌龟移动到指定点;
- t.color(color_str)设置乌龟颜色;
- t.fillcolor(color)设置填充颜色,t.begin_fill()在画需要填充颜色的形状前调用,t.end_fill()在画需要填充颜色的形状后调用;
- t.setheading()设置乌龟方向:0 - east,90 - north,180 - west,270 - south;
- t.pensize()调整画笔尺寸。
1.分形
分形(fractal),就是满足如下条件的图形,无论对图像如何进行放大,它的局部图像和总体图像总是一致的。wikipedia的解释。大自然中的分形有雪花/海岸线等等。
你可以想象如果你是上帝,你在创造海岸线的时候,首先在空中画了一副轮廓,当你想进一步描绘海岸线的细节时,你下降了一些高度,然后按照你刚才的思路,接着画了一模一样的轮廓,如此循环。
上面这个过程,正好符合递归的思路。
下面的代码,画一棵分形的树:
1 | def tree(branchLen,t): |
接着画一个分形的三角:
1 | def drawTriangle(points,color,myTurtle): |
2.汉诺塔
汉诺塔规则:
有三根柱子和一些大小不同的盘子。初始状态是所有盘子从大到小一直往上堆积在起始柱上。
每次可以移动一个盘子,到其他两根柱子上,必须保证大的盘子在下面,小的盘子在上面。
最终的目标是把所有盘子从大到小往上堆积在目标柱上。
分析:
考虑问题的分解:
如果有n片盘子,那么可以分解成先将n-1片移到中间柱上,再把最大的一片从起始柱移到目标柱上,再把n-1片移到目标柱上。
移动n片盘子和移动n-1片盘子是完全相同的问题,所以可以使用自己调用自己。
那么基础情况呢?如果只是移动一片盘子,那就直接从起始柱移到目标柱上,就解决了。
根据上面的分析,使用递归的三个条件都满足了。
1 | def moveTower(height,fromPole, toPole, withPole): |
1 | ('moving disk from', 'A', 'to', 'B') |
3.迷宫问题
想必这个问题就不用介绍了,就是给定起点和迷宫信息,要找到一条出去的路径。
分析:
如何找到一条可以出去的路呢?
不考虑出去的路的长短的话,我们可以先考虑当前点可能的操作,无非是上下左右移动(能不能移动另说)。
那么我们可以把问题等价于在当前点的所有可能操作+假设这样做了一步之后的整体搜索。
其实说白了就是深度优先搜索。
作者给出了一个turtle实现的案例(都可以做一个游戏了,老外写书真心认真~)
1 | PART_OF_PATH = 'O' |
1 | True |
对比动态规划
动态规划(Dynamic Programming)。
递归虽然好用,写起来简单,代码易读,但是依然有很多问题不适合用递归。
比如说动态规划,拿最简单的硬币找钱问题举例子。
比如有三种硬币1,2,5元的,现在有一定数额的总数,请问怎么找前可以使得硬币数最少?
类似的还有背包问题:
比如背包可以装的物品有1,2,5公斤的物品,带来的效益分别是1,3,10元,如何安排物品,使得背包的总效益最大?
如果采用递归去解决这些问题,会产生时间复杂度非常大的问题,为什么呢?比如你要求的是规模是10的问题,你把它缩小成规模是5和5的问题,这两个子问题虽然是相同的问题,但由于递归不会记录子问题的答案,所以会计算两次。
那么我们把每次递归计算的不同规模的问题的答案记录下来呢?
当然可以,这会节省很多时间,但在很多情况下,这不是最高明的算法。
如果采用动态规划,直接从最小规模的问题开始出发,记录所有规模下的问题答案,直到指定的规模,获得结果。
当然,需要具体问题具体分析。
作业
q1
用递归的方法写一个阶乘函数:
1 | def factorial(n): |
1 | 24 |
q2
用递归的方法逆转一个list:
1 | def reverse(l): |
1 | [6, 5, 4, 3, 2, 1] |
q3
修改作者的分形树:
1 | import random |
###
q4
画一座分形的山:
1 | def drawTriangle(points,color,myTurtle): |
画风有点像葫芦娃。
q5
用递归的方法解决斐波那契数列:
1 | def genFibonacci(n): |
1 | [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] |
1 | def genFibonacciSequence(n): |
1 | [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] |
分析:
如果只是生成一个指定序号的斐波那契数,那么两种方法的时间复杂度是一样的。
但是如果生成的是一个序列的话,还是循环方法时间复杂度小,是$O(n)$;递归方法的时间复杂度是$O(n^2)$。
关键还是在于递归方法没有记录计算过的指定序号的斐波那契数的数值。
q6
改进汉诺塔的算法,使用3个栈记录三个柱子的实时情况:
1 | class Tower: |
1 | moving disk from A to B |
q7
使用turtle模块,画出Hilbert curve。
Hilbert curve的介绍:wikipedia
思路:
参考这里,将问题分解成画“三笔凸包”和连接线。
1 | def draw_hilbert(x0, y0, xis, yis, xjs, yjs, n): |
q8
使用turtle模块,画出Koch snowflake。
介绍参考wiki-pedia。
思路:
- 首先将任务分成三个相同的三部分,即三角形的三条边,不管每条边如何复杂化,都是相同的操作。
- 对于每条边,宏观上的操作如下,(在一根直线上长出一个角):
1 | def koch(length, order): |