【剑指 offer】跳台阶 1

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))