1. 斐波那契数列
简单的递归数列问题
(1) 蓝桥杯入门训练:Fibonacci数列
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
代码详细:1
2
3
4
5
6
7
8
9
10
11n = int(input())
a=b = 1
c = 0
if n==1 or n == 2:
print(1)
elif n > 2:
for i in range(3, n+1):
c = (a + b) % 10007
a = b
b = c
print(c)
(2) Leetcode509. 斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
代码详细:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution(object):
def fib(self, N):
"""
:type N: int
:rtype: int
"""
# 第一次提交的代码,优化的不是很好
"""
a=1
b=1
c=0
if N == 0 :
return 0
elif N==1 or N==2:
return 1
else:
for i in range(3,N+1):
c=a+b
a=b
b=c
return c
"""
# 最优解
if N in (0, 1):
return N
a=0
b=1
for i in range(2,N+1):
temp=a
a=b
b=temp+a
return b
(3) LeetCode70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
3. 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 2 阶
5. 2 阶 + 1 阶
代码详细:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
# 第一次提交的代码,优化的不是很好
"""
a=1
b=1
c=0
if n==1:
return a
elif n==2:
return a+b
else:
for i in range(2, n+1):
c=a+b
a=b
b=c
return c
"""
#最优解 使用了append列表函数添加数字
lis = []
lis.append(1)
lis.append(2)
if n==1:
return 1
if n==2:
return 2
for i in range(2, n):
lis.append(lis[i-1]+lis[i-2])
return lis[-1]
(4) LeetCode1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例 1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2：
输入：n = 25
输出：1389537
提示：
0 <= n <= 37
答案保证是一个 32 位整数，即 answer <= 2^31 - 1。
代码详细:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
def tribonacci(self, n):
"""
:type n: int
:rtype: int
"""
if n in (0, 1):
return n
lis=[]
lis.append(0)
lis.append(1)
lis.append(1)
for i in range(3,n+1):
lis.append(lis[i-1]+lis[i-2]+lis[i-3])
return lis[-1]
2. 汉诺塔
如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去
期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
代码详细:
1 | def Move(n, A, B, C): |
以上就是一些递归的经典算法,再接再厉,每日学习一点算法,然后温故而知新。