#斐波纳契 一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
# 假设最后一步到X级台阶,有F(X)种走法,
# 这题求的就是F(11)
# 因为每步可以迈1或2级台阶。
# 所以最后一步到11级台阶,
# 而倒数第2步可能是在第10或9级台阶。
# 所以到11级台阶的走法,是到第10或9级台阶走法的和。
# 同样到9级台阶的走法,是到第7或8级台阶走法的和。
# ...................
# F(11)
# =F(9)+F(10)
# =2F(9)+F(8)
# =3F(8)+2F(7)
# =5F(7)+3F(6)
# =8F(6)+5F(5)
# =13F(5)+8F(4)
# =21F(4)+13F(3)
# =34F(3)+21F(2)
# =55F(2)+34F(1)
# 因为:上1级台阶只有1种走法,所以F(1)=1。
# 上2级台阶有2种走法,1步1步走或1次走2步。所以F(2)=2
# F(11)==55F(2)+34F(1)
# =55*2+34*1
# =110+34
# =144
# 上10级台阶一共有144不同的迈法。
# 1,2,3,5,8,13,21
# count=0
#1、
# def fib(n):
# global count
# count+=1
# # count+=1
# if n<2:
# return 1
# return fib(n-1)+fib(n-2)
#
# print(fib(7))
# print("-----------",count) # fib(n-1)+fib(n-2)有重复运行的问题,运行了21*2-1=41次
#2、
# fib = lambda n: n if n <2 else fib(n - 1) + fib(n - 2)
# print(fib(7))
# print("-----------",count)
#3、
# count = 1
#
# def memo(func):
# cache={}
# def wrap(*args):
# global count
# count+=1
# if args not in cache:
# cache[args]=func(*args)
# # print(cache)
# return cache[args]
# return wrap
#
# @memo
# def fib(n):
# if n<2:
# return 1
# return fib(n-1)+fib(n-2)
#
# print(fib(7))
# print(count)
#运行了13+1=14次
#4、
# count = 1
# def fib(n):
# global count
# a,b=0,1
# for i in range(n):
# count+=1
# a,b=b,a+b
# return b
#
# print(fib(7)) #21
# print(count) #8
#一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
#1、
# fib = lambda n: n if n < 2 else 2 * fib(n - 1)
# print(fib(7))
#2、
# 1 2 3 4 5 6 7
# 1,2,3,5,8,13,21
# def fib(n):
# if n<2:
# return 1
# return 2*fib(n-1)
#如果n=7,那么return 2*fib(6)
#则: 2*fib(6)=4fib(5)=8fib(4)=16fib(3)=32fib(2)=64fib(1)
#按理来说: 如果有7级台阶,应该有
#解释:走7级台阶,
# 最后一次走1级,那么前面的有fib(6)种方法
# 最后一次走2级,那么前面的有fib(5)种方法
# 。。。。。。
# 最有一次走6级,那么前面的有fib(1)种方法
# fib(7)=fib(1)+fib(2)+fib(3)+fib(4)+fib(5)+fib(6)
# fib(6)=fib(1)+fib(2)+fib(3)+fib(4)+fib(5)
#故,得证!!!