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

总结

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

赞 (0)

相关推荐

  • 使用C++递归求解跳台阶问题

    使用C++递归求解跳台阶问题

    题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级.求总共有多少总跳法? 分析: 也是比较基础的题目,通过递归可以方便的求解. 用Fib(n)表示青蛙跳上n阶台阶的跳法数,青蛙一次性跳上n阶台阶的跳法数1(n阶跳),设定Fib(0) = 1:        当n = 1 时, 只有一种跳法,即1阶跳:Fib(1) = 1;        当n = 2 时, 有两种跳的方式,一阶跳和二阶跳:Fib(2) = Fib(1) + Fib(0) = 2;        当n = 3

  • php中青蛙跳台阶的问题解决方法

    一只青蛙一次可以跳上1级台阶,也可以跳上2级.求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果). 思路: 1.找规律 f(1)=1 f(2)=2 f(3)=3 f(4)=5 f(n)=f(n-1)+f(n-2)这是一个斐波那契数列 2.因为调到第n个台阶时,倒数第一个台阶可以一步跳过来,倒数第二个台阶也可以一步就跳过来 非递归版本: JumpFloor(target) if target==1 || target==2 return target jumpSum=0 jum

  • 利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题

    跳台阶问题 题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级. 求总共有多少总跳法,并分析算法的时间复杂度. 分析: 也是比较基础的题目,通过递归可以方便的求解 代码实现如下(GCC编译通过): #include "stdio.h" #include "stdlib.h" int function(int n); int main(void) { int tmp; tmp = function(5); printf("%3d\n&q

  • c语言 跳台阶问题的解决方法

    c语言 跳台阶问题的解决方法

    题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级.求总共有多少种跳法,并分析算法的时间复杂度.答:用一个函数f(n)来表示n级台阶总的跳法.1.只有1个台阶,则f(1) = 1;2.有2个台阶,则f(2) = 2;3.当有n个台阶时,如果第一次跳1级,有f(n-1)种跳法,如果第一次跳2级,有f(n - 2)种跳法,即f(n) = f(n-1) + f(n-2).即为Fibonacci序列. 复制代码 代码如下: #include "stdafx.h"#include <

  • 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-

  • Python中循环后使用list.append()数据被覆盖问题的解决

    前言 最近发现一个问题,在一次爬虫实战中,需要将字典加入列表中,意外的情况出现了!!!下面简单分析一下出现的状况: list = [] dic = {} for i in range(5): dic['num'] = i list.append(dic) print(id(dic)) print(list) 136652096 136652096 136652096 136652096 136652096 [{'num': 4}, {'num': 4}, {'num': 4}, {'num':

  • python中的try except与R语言中的tryCatch异常解决

    目录 1. 起因 2. Python中的try/except 1)情形一 2)情形二 3)情形三 3. R中的tryCatch 1)情形一 2)情形二 3)情形三 补充 1. 起因 当我们需要写一个非常非常长的循环时,通常在某个循环如果出现error,那么整个代码后面的循环就不能进行. 这时候试想,如果你在服务器上挂一个要跑很久的循环(并行),亦或是需要在自己电脑上挂一晚上跑东西,可能刚点完运行,美滋滋地上床后,程序突然出现问题.这时第二天满怀期待地点亮屏幕,发现是一个大大的红红的ERROR时,

  • python中利用numpy.array()实现俩个数值列表的对应相加方法

    小编想把用python将列表[1,1,1,1,1,1,1,1,1,1] 和 列表 [2,2,2,2,2,2,2,2,2,2]对应相加成[3,3,3,3,3,3,3,3,3,3]. 代码如下: import numpy a = numpy.array([1,1,1,1,1,1,1,1,1,1]) b = numpy.array([2,2,2,2,2,2,2,2,2,2]) c = a + b print(type(c)) print(list(c)) 输出结果为: <class 'numpy.nd

  • Python连接Oracle之环境配置、实例代码及报错解决方法详解

    Python连接Oracle之环境配置、实例代码及报错解决方法详解

    Oracle Client 安装 1.环境 日期:2019年8月1日 公司已经安装好Oracle服务端 Windows版本:Windows10专业版 系统类型:64位操作系统,基于x64的处理器 Python版本:Python 3.6.4 :: Anaconda, Inc. 2.下载网址 https://www.oracle.com/database/technologies/instant-client/downloads.html 3.解压至目录 解压后(这里放D盘) 4.配置环境变量 控制

  • python报错TypeError: Input z must be 2D, not 3D的解决方法

    python报错TypeError: Input z must be 2D, not 3D的解决方法

    目前,在使用python处理一个nc文件绘制一个风场图时,出现了以下报错 虽然图片画出来了,但是很丑而且没有理想的填充颜色! 但是不知道为啥,但是参考画图过程,分析这个其中的Z应该指的绘制等高线中的这个函数:matplotlib.pyplot contourf  中使用到的Z! 而这个函数的用法为 coutour([X, Y,] Z,[levels], **kwargs) 在这里提出,matplotlib.pyplot contourf 是用来绘制三维等高线图的,不同点是contour()是绘制

  • Android编程中调用Camera时预览画面有旋转问题的解决方法

    本文实例讲述了Android编程中调用Camera时预览画面有旋转问题的解决方法.分享给大家供大家参考,具体如下: 在调用Camera写应用的时候,前后摄像头的情况有时候是不一样的.有时候,明明后摄像头没有问题,而调用到前摄像头时,却倒转了180°,或者其他角度,百思不得其解.在查看了Android源码之后,发现它的解决办法很是好,接下来贴个源码,以备日后查看. public static int getDisplayRotation(Activity activity) { int rotat

  • python打包生成的exe文件运行时提示缺少模块的解决方法

    事情是这样的我用打包命令:pyinstaller -F E:\python\clpicdownload\mypython.py打包了一个exe程序,但是运行时提示我缺 少bs4模块然后我就去查pyinstaller的使用方法,找到pyinstaller有一个-p参数: 1.设置导入路径(和使用PYTHONPATH效果相似).可以用路径分割符(Windows使用分号,Linux使用冒号)分割,指定多个目录. 2.也可以使用多个-p参数来设置多个导入路径 然后我找到bs4模块所在的目录E:\pyth

  • 浅谈python在提示符下使用open打开文件失败的原因及解决方法

    题目:在提示符下使用open打开一个文件 刚开始网上看了下打开的方式,结果一直实现不了,报错是没找到这个文件,而且和我输入的文件名不一样. 错误如下: >>>open('d:\456.txt') Traceback (most recent call last): File "<pyshell#0>", line 1, in <module> open('d:\456.txt') IOError: [Errno 2] No such file

  • angular4中*ngFor不能对返回来的对象进行循环的解决方法

    解决方法:可以循环返回的对象,得到对象里每一个key所对应的值,然后把值放到自己定义的一个数组中. 例如: tipAttr: any = []; $.each(response.ipCustomer.tip, function(key, val) { console.log(val); self.tipAttr.push(val); return self.tipAttr; }); 以上这篇angular4中*ngFor不能对返回来的对象进行循环的解决方法就是小编分享给大家的全部内容了,希望能给

随机推荐