Python算法题(一)——青蛙跳台阶
题目一(青蛙跳台阶):
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析:
假设只有一级台阶,则总共只有一种跳法;
假设有两级台阶,则总共有两种跳法;
假设有n级台阶,那么第一步就要分为跳一步和跳两步:
跳一步,那么接下来就是跳n-1;
跳两步,那么接下来就是跳n-2;
所以,总数可以认为是f(n-1)+f(n-2)。
主要代码:
def frog(num):
if num <= 2:
return num
t1, t2 = 1, 2
for _ in range(3, num+1):
t1, t2 = t2, t1+t2
return t2
题目二(变态跳台阶):
一只青蛙一次可以跳上1级台阶,也可以跳上2级......它也可以跳上n阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析:
相比之前的跳台阶,这次可以从任意台阶跳上n级,所以总体来看与上一个问题差不多,只不过递归公式应该是各个台阶之和再加上直接跳上去的情况,所以总数应该是f(n-1)+f(n-2)+f(n-3)+...+f(2)+f(1)=2**n-1。
主要代码:
def frog(num):
if num==0:
return 0
return 2**(num-1)
拓展问题(矩形覆盖):
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
分析:
这个问题实际上就是普通的跳台阶问题,只不过说法不一样而已。
假设n=1,则只有一种方法;
假设n=2,则共有两种方法;
假设n=3,则分为两种情况:
第一次用一个矩形竖着覆盖(左图阴影),则剩下共有2(n-1)种方法
第二次用一个矩形横着覆盖(右图蓝色),那么下方区域只剩下图示一种方法,所以剩下1(n-2)种方法
最后可以看出求矩形覆盖问题和求青蛙跳台阶问题的通式是一样的,它们都符合斐波那契数列的通式,即f(n-1)+f(n-2)
主要代码:
def rectangle(num):
if num <= 2:
return num
t1, t2 = 1, 2
for _ in range(3, num+1):
t1, t2 = t2, t1+t2
return t2
通过这几个题目我们可以看出,其实很多题目都有共通之处,甚至有些题目的变题会更简单,所以我们需要从平时开始积累,日积月累下来,我们见识过的题目多了,自然而然写代码的水平就上去了。
最新文章
- 向Maven的本地库中添加jar文件
- maven url
- A.Kaw矩阵代数初步学习笔记 10. Eigenvalues and Eigenvectors
- Redis数据库的使用与介绍
- [问题2014S05] 复旦高等代数II(13级)每周一题(第五教学周)
- iis 301重定向
- mod_php VS mod_fastcgi
- no branch 问题
- 【C#学习笔记】鼠标控制
- C#排序算法的比较
- 怎样在WIN7系统下安装IIS和配置ASP(详细)
- Java使用POI为Excel打水印,调整列宽并设置Excel只读(用户不可编辑)
- 子集构造法实现NFA的确定化
- chrome 和IE 上传的文件,在net 后台取值Request.Form.Files[0].FileName 的不同
- WebView 判断放大缩小操作
- 【Shared Server Mode】测试调整shared_servers参数对数据库的影响
- 数据库-MySQL入门
- mysql启动、关闭与登录
- 洛谷P3806 点分治1 &; POJ1741 Tree &; CF161D Distance in Tree
- 一个或多个音频服务未运行 win7 错误1079:此服务的账户不同于运行于同一进程上的其他服务账户