一只青蛙一次可以跳一级或二级台阶，请问跳n级台阶有多少次跳法之斐波那契数列的非递归写法

ゞ浴缸里的玫瑰 2022-03-01 16:22 161阅读 0赞

##### 对于这个问题 #####

*  前三次都好算分别为1,2,3次,后面多的话不好简单计算
 *  当第n级台阶时,因为青蛙只能跳一级或二级台阶,所以第n级只有两种方法跳过来,  
    即,从前一级(n-1)或前两级(n-2),所以调到这两级的方法加起来即为n级方法总数
 *  现在构成斐波那契数列(fěi bō nà qì shù liè)

##### 注意 #####

*  这个是斐波那契的变种，斐波那契为　１　１　２　３　５　８
 *  现在这个问题为　　　　　　　 　　　　１　２　３　５　８  
    仅仅少了个１，代码稍加改动即可

#### 下面代码都是基于1 2 3 5 8实现的 ####

##### １.斐波那契问题最简单的是递归实现，但是递归运行效率太低，而且python有最大递归深度,我试了一下基本上递归900次都需要很长时间.所以只简单写出来参考,`不推荐` #####

注意:python3默认最大递归深度为998,可以通过sys.setrecursionlimit(1000)来设置最大递归深度,但是递归效率太低,所以`不推荐,仅供了解`

def Fibonacci(num):
        if num <= 2:
            return num
        else:
            fn = Fibonacci(num-1) + Fibonacci(num - 2)
        return fn
    
    print(Fibonacci(30))

# 运行时间   30次递归都要31秒
        Fibonacci executed in 31.423158 s
        1346269

##### 2.非递归实现 #####

def Fibonacci(n):
        if n <=2:
            return n
        else:
            last,last_last = 1, 2
            for i in range(n - 2):
                last,last_last = last_last, last + last_last
            return last_last
    print(Fibonacci(10000))

# 非递归10000次才0.004秒
    Fibonacci executed in 0.003991 s
    544383731135652813387342609937503801353891845546959670262477

##### 3.非递归2 #####

def Fibonacci(n):
        if n <=3:
            return n
        else:
            last,last_last = 3,2
            for i in range((n//2)-1):
                last_last = last+last_last
                last = last+last_last
            return last_last if n%2 == 0 else last
    print(Fibonacci(30))

##### 4.列表实现(因为要添加列表元素,比2,3慢,也`不太推荐`) #####

def Fibnacci(n):
        result = [1,2]
        if n <= 2:
            return n
        for i in range(2,n+1):
            result.append(result[i-1]+result[i-2])
        return result[n-1]
    print(Fibnacci(10000))

Fibnacci executed in 0.012464 s
    5443837311356528133873426099375038013538918455469596702624