Python中跳台阶、变态跳台阶与矩形覆盖问题的解决方法

yipeiwu_com7年前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

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对【听图阁-专注于Python设计】的支持。

相关文章

Python 中Django验证码功能的实现代码

Python 中Django验证码功能的实现代码

  为了防止机器人频繁登陆网站或者破坏分子恶意登陆,很多用户登录和注册系统都提供了图形验证码功能。   验证码(CAPTCHA)是“Completely Automated Public...

删除目录下相同文件的python代码(逐级优化)

删除目录下相同文件的python代码(逐级优化)

这两天闲来无事在百度上淘了点图片,不多,也就几万张吧,其中有不少美女图片奥!哈哈!这里暂且不说图片是怎么获得的,咱聊聊得到图片以后发生的事。 遇到的第一个问题就是有些图片没有后缀名。在w...

python 3.0 模拟用户登录功能并实现三次错误锁定

Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。 Python由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。 像Perl...

在Django的视图中使用数据库查询的方法

在视图中也有笨方法可以从数据库中获取数据。 很简单: 用现有的任何 Python 类库执行一条 SQL 查询并对结果进行一些处理。 在本例的视图中,我们使用了 MySQLdb 类库(可以...

基于python实现的百度新歌榜、热歌榜下载器(附代码)

基于python实现的百度新歌榜、热歌榜下载器(附代码)

前言 首先声明,本工具仅仅为学习之用,不涉及版权问题,因为百度音乐里面的歌曲本身是可以下载的,而且现在百度也提供了”百度音乐播放器”,可以通过这个工具进行批量下载。 我当时做这个工具的时...