首页 > 代码库 > 编程题目: 斐波那契以及台阶问题

编程题目: 斐波那契以及台阶问题

       0         n = 1

f(n)  =     1          n = 1

       f(n-1) + f(n-2)  n >=2

一.斐波那契

1.递归实现

递归实现的代码一目了然,简单易懂.但重复计算了元素,所以效率比较低下。

 1 #!/usr/bin/env python3
 2 
 3 def fibs(n):
 4         if n < 0:
 5                 raise ValueError("n must >= 0")
 6         if n == 0 or n == 1:    return 1
 7         else:
 8                 return fibs(n-2) + fibs(n-1)
 9 
10 if __name__ == "__main__":
11         print(fibs(10))

 

2.迭代实现

迭代的时间效率为 0(n),空间效率为0(1)

 1 #!/usr/bin/env python3
 2 
 3 def fibs(n):
 4         if n < 0:
 5                 raise ValueError("n must >= 0")
 6         a = [1,1]
 7         if n == 0 or n == 1:    return 1
 8         for i in range(2,n+1):
 9                 a[0],a[1] = a[1],a[0]+a[1]
10         return a[1]
11 
12 if __name__ == "__main__":
13         print(fibs(10))

 

 

二.台阶问题

一只青蛙可以一次跳1阶台阶,也可以一次跳2次台阶。请问当这只青蛙跳了n阶的时候,请问有多少种跳法?

 

求f(n),当青蛙跳了1阶台阶的时候,这个问题就变成了f(n-1);

当青蛙跳了2阶台阶的时候,这个问题就变成了f(n-2)。

所以 f(n) = f(n-2) + f(n-1)

当只有1阶时,有1种跳法;当位2阶时,有2种跳法。

 

所以

       1         n = 1

f(n)  =     2          n = 2

       f(n-1) + f(n-2)  n >2

 1 #!/usr/bin/env python3
 2 
 3 def taijie(n):
 4         if n <= 0:
 5                 raise ValueError("n must >0")
 6         a = [1,2]
 7         if n == 1:      return 1
 8         if n == 2:      return 2
 9         for i in range(3,n+1):
10                 a[0],a[1] = a[1],a[0]+a[1]
11         return a[1]
12 
13 if __name__ == "__main__":
14         print(taijie(5))

 

编程题目: 斐波那契以及台阶问题