Python解决N阶台阶走法问题的方法分析

yipeiwu_com5年前Python基础

本文实例讲述了Python解决N阶台阶走法问题的方法。分享给大家供大家参考,具体如下:

题目:一栋楼有N阶楼梯,兔子每次可以跳1、2或3阶,问一共有多少种走法?

Afanty的分析:

遇到这种求规律的问题,自己动动手推推就好,1阶有几种走法?2阶有几种走法?3阶有几种走法?4阶有几种走法?5阶有几种走法?

对吧,规律出来了!

易错点:这不是组合问题,因为第1次走1阶、第2次走2阶不同于 第1次走2阶、第2次走1阶

下面是Python的递归实现代码:

def allMethods(stairs):
  '''''
  :param stairs:the numbers of stair
  :return:
  '''
  if isinstance(stairs,int) and stairs > 0:
    basic_num = {1:1,2:2,3:4}
    if stairs in basic_num.keys():
      return basic_num[stairs]
    else:
      return allMethods(stairs-1) + allMethods(stairs-2) + allMethods(stairs-3)
  else:
    print 'the num of stair is wrong'
    return False

当然也可以用非递归的方法来实现,下面就是基于递推法的代码:

def allMethod(stairs):
  '''''递推实现
  :param stairs: the amount of stair
  :return:
  '''
  if isinstance(stairs,int) and stairs > 0:
    h1,h2,h3,n = 1,2,4,4
    basic_num = {1:1,2:2,3:4}
    if stairs in basic_num.keys():
      return basic_num[stairs]
    else:
      while n <= stairs:
        temp = h1
        h1 = h2
        h2 = h3
        h3 = temp + h1 + h2
      return h3
  else:
    print 'the num of stair is wrong'
    return False

好的,以上就是分别用了递归和递推法实现的过程。

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程

希望本文所述对大家Python程序设计有所帮助。

相关文章

python获取指定网页上所有超链接的方法

本文实例讲述了python获取指定网页上所有超链接的方法。分享给大家供大家参考。具体如下: 这段python代码通过urllib2抓取网页,然后通过简单的正则表达式分析网页上的全部url...

Python中字典的浅拷贝与深拷贝用法实例分析

Python中字典的浅拷贝与深拷贝用法实例分析

本文实例讲述了Python中字典的浅拷贝与深拷贝用法。分享给大家供大家参考,具体如下: 最近发现的一个很值得记录的东西就是python字典的浅拷贝问题 首先,明确一下什么是浅拷贝,什么是...

通过pykafka接收Kafka消息队列的方法

没有Kafka环境,所以也没有进行验证。感觉今后应该能用到,所以借抄在此,备查。 pykafka使用示例,自动消费最新消息,不重复消费: # -* coding:utf8 *- fr...

使用python实现哈希表、字典、集合操作

使用python实现哈希表、字典、集合操作

哈希表 哈希表(Hash Table, 又称为散列表),是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标。...

python虚拟环境的安装和配置(virtualenv,virtualenvwrapper)

python虚拟环境的安装和配置(virtualenv,virtualenvwrapper)

一、为什么要安装虚拟环境     情景一、项目A需要某个库的1.0版本,项目B需要这个库的2.0版本。如果没有安装虚拟环境,那么当你使用这两个项目时,你就需要来回的卸...