【Python】今日份刷题

题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法?

解题思路:列出前5级台阶可以产生多少种跳法,并观察规律  可以发现规律如下

没有台阶的时候,不用跳,0种跳法

只有1阶台阶的时候,有1种跳法

有2阶台阶的时候,有2种跳法

有3阶台阶的时候,有3种跳法

有4阶台阶的时候,有5种跳法

有5阶台阶的时候,有8种跳法

结论:除了没有台阶,1阶,2阶比较特别,3阶开始后续的跳法符合斐波那契数,即f(n)=f(n-1)+f(n-2) 函数递归可解

代码如下

【Python】今日份刷题
def fibonacci(n):
    if n ==0:
        result=0
        return result
    elif n==1:
        result=1
        return result
    elif n==2:
        result=2
        return result
    else:
        result=fibonacci(n-1)+fibonacci(n-2)
        return result
user_input=int(input("请输入台阶数量:"))
print("青蛙一共有%d种方案跳台阶"%fibonacci(user_input))
View Code


上一篇:数据结构之队列的应用(实现斐波那契数列)


下一篇:java数据结构和算法(07)斐波那契数列