简介:
递归算法里面最经典的两个非 fibonacci 和 hanio 莫属了
今天练习就这两数列用 python 代码实现
斐波那契数列
- '''
- Fibonacci(斐波那契数列)
- 1,1,2,3,5,8,13,25....
- '''
- # 使用递归
- # 算法复杂度: O(2^^n) 注: 该递归算法复杂度较高, 且运行速度较慢
- # 定义实现函数
- def fib(n):
- if n <= 1:
- return n
- else:
- return(fib(n-1) + fib(n-2))
- # 获取用户输入
- num = int(input("您要输出几项?"))
- # 检查输入的数字是否正确
- if num <= 0:
- print("输入正数")
- else:
- print("斐波那契数列:")
- for i in range(num):
- print(fib(i))
- # 输出结果
- # 输出结果
您要输出几项? 10
斐波那契数列:
- 0
- 1
- 1
- 2
- 3
- 5
- 8
- 13
- 21
- 34
- # 使用简单的函数
- # 算法复杂度更低的 fibonacci 数列
- # 算法复杂为 O(n)
- def fib(n):
num, a, b = 0, 0, 1
- while num <n:
- print(b)
a, b = b, a + b
- n = n + 1
- return 'done'
- # 输出结果
- >>> fib(6)
- 1
- 1
- 2
- 3
- 5
- 8
- 'done'
汉诺塔
- # 递归
- # 算法复杂度: O(2**n)
- '''
设定三根棒子从左到右为: x,y,z
思路:
第一步: x 上的 (n-1) 个盘子借助 z 到 y 上
第二步: y 上的 (n-1) 个盘子借助 x 到 z 上
- '''
- def hanio(n,x,y,z):
- if n == 1:
- print(x,'-->',z) #如果只有一层, 直接从 x 移动到 z
- else:
- hanio(n-1,x,z,y) #将 n-1 个盘子从 x 移动到 y
- print(x,'-->',z) #最底下的盘子从 x 移动到 z
- hanio(n-1,y,x,z) #将 n-1 个盘子从 y 移动到 z
- n = int(input('please input the floor:'))
- hanio(n,'x','y','z')
- # 输出结果
- please input the floor:3
- x --> z
- x --> y
- z --> y
- x --> z
- y --> x
- y --> z
- x --> z
来源: http://www.bubuko.com/infodetail-2622948.html