本系列旨在通过一系列由浅入深的python实战代码或项目,使普通人也能感受到编程的乐趣,编程能够在平时的工作生活上有所帮助。欢迎查看系列的开篇词和前面文章。
概述
小时候是否被这个问题考过,假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
例如:2级阶梯,那你有2种方法登上楼顶
- 1步台阶+1步台阶
- 2步台阶
例如:3级台阶,那你有3中方法登上楼顶
- 1步台阶+1步台阶+1步台阶
- 1步台阶+2步台阶
- 2步台阶+1步台阶
如果是n阶楼梯,那该怎么计算了
代码实现过程
这个问题的正确思路应该是从最后一步台阶考虑,意思是最后一步台阶可能跨了一级台阶,也可能跨了两级台阶。
如果我们用n表示台阶数,那意味着爬到第 级台阶的方案数是爬到第 n - 1 级台阶的方案数和爬到第 n- 2 级台阶的方案数的和。我们只需要不断的两项方案加起来。
#定义
def climbStair(n):
n1 = 0
n2 = 0
r = 1
for i in range(n):
n1 = n2
n2 = r
r = n1 + n2
print("爬{}级阶梯有{}种方法".format(n, r))
return
if __name__ == '__main__':
print("是否被考过这个问题,假设你正在爬楼梯。需要 n阶你才能到达楼顶。"
"每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?")
n = int(input("请输入台阶数:"))
climbStair(n)
计算4阶楼梯,有5种方法,与手动计算是一致的
C:\ProgramData\Anaconda3\python.exe "G:/OneDrive - shu.edu.cn/1-学习资料/python/python实战项目代码合集/爬楼梯问题.py"
是否被考过这个问题,假设你正在爬楼梯。需要 n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
请输入台阶数:4
爬4级阶梯有5种方法
计算10阶楼梯,有89种方法
C:\ProgramData\Anaconda3\python.exe "G:/OneDrive - shu.edu.cn/1-学习资料/python/python实战项目代码合集/爬楼梯问题.py"
是否被考过这个问题,假设你正在爬楼梯。需要 n阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
请输入台阶数:10
爬10级阶梯有89种方法
评论区