1. 问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
2. 分析
- 归纳推理：
- 最后推导的
如何理解呢？
跳到第n个台阶的方法总数就是跳到第n-1个台阶的方法总数加上第n-2个台阶的总数。 - 其实该题是Fibonacci数列的巧妙应用
3. python代码
- 方法一：非递归 running time:0.000027
# -*- coding:utf-8 -*-
from time import clock
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
else:
f1 = 1
f2 = 2
for i in range(3,number+1):
fn = f1 + f2
f1 = f2
f2 = fn
return fn
if __name__ == '__main__':
start_time = clock()
solution = Solution()
print solution.jumpFloor(7)
end_time = clock()
print("time:%f" % (end_time - start_time))
- 方法二 递归 running time:0.000060
# -*- coding:utf-8 -*-
from time import clock
class Solution:
def jumpFloor(self, number):
# write code here
if number == 1:
return 1
elif number == 2:
return 2
else:
return self.jumpFloor(number-1) + self.jumpFloor(number-2)
if __name__ == '__main__':
start_time = clock()
solution = Solution()
print solution.jumpFloor(7)
end_time = clock()
print("time:%f" % (end_time - start_time))
