Python中跳台阶、变态跳台阶与矩形覆盖问题的解决方法
前言 跳台阶、变态跳台阶、矩形覆盖其实都和斐波那契数列是一类问题,文中通过示例代码介绍的非常详细,下面话不多说了,来一起看看详细的介绍吧。 跳台阶 问题描述:
分析: 初始值很容易得到,当n > 2时,跳上n级台阶最后一步无外乎两种情况,从第n-1级跳一级跳上来,或是从第n-2级跳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级。因此其递归公式为各个台阶之和再加上直接跳上去的一种情况。
代码: def jump_floor(number): if number == 0: return 0 return 2**(number-1) 矩形覆盖 问题描述: 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? 分析: 仔细分析这个问题实际上就是普通的跳台阶问题。
代码: def jump_floor(number): if number <= 2: return number prev,prev+curr return curr 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对编程小技巧的支持。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |