python输出台阶图案_Python中跳台阶、变态跳台阶与矩形覆盖问题的解决方法

前言

跳台阶、变态跳台阶、矩形覆盖其实都和斐波那契数列是一类问题，文中通过示例代码介绍的非常详细，下面话不多说了，来一起看看详细的介绍吧。

跳台阶

问题描述：

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

分析：

初始值很容易得到，当n > 2时，跳上n级台阶最后一步无外乎两种情况，从第n-1级跳一级跳上来，或是从第n-2级跳2级跳上来，因此很容易得到如下递归公式。

F(0)= 0

F(1)= 1

F(2)= 2

F(n)= F(n-1)+ F(n-2)(n > 2)

代码：

def jump_floor(number):

if number <= 2:

return number

prev, curr = 1, 2

for _ in range(3, number+1):

prev, curr = curr, prev+curr

return curr

变态跳台阶

问题描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

相比上一个跳台阶，这次可以从任意台阶跳上第n级台阶，也可以直接跳上第n级。因此其递归公式为各个台阶之和再加上直接跳上去的一种情况。

F(0)= 0

F(1)= 1

F(2)= 2

F(n)= F(n-1)+ F(n-2)+ … + F(2)+ F(1)+ 1 = 2 **(n-1)

代码：

def jump_floor(number):

if number == 0:

return 0

return 2**(number-1)

矩形覆盖

问题描述：

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

分析：

仔细分析这个问题实际上就是普通的跳台阶问题。

F(0)= 0

F(1)= 1

F(2)= 2

F(n)= F(n-1)+ F(n-2)(n > 2)

代码：

def jump_floor(number):

if number <= 2:

return number

prev, curr = 1, 2

for _ in range(3, number+1):

prev, curr = curr, prev+curr

return curr

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对脚本之家的支持。