首頁  >  文章  >  後端開發  >  Python解決N階台階走法問題的方法

Python解決N階台階走法問題的方法

不言
不言原創
2018-04-27 15:21:243130瀏覽

這篇文章主要介紹了Python解決N階台階走法問題的方法,簡單描述了走台階問題,並結合實例形式分析了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 &#39;the num of stair is wrong&#39;
    return False


#好的,以上就是分別用了遞迴與遞推法實現的過程。

相關推薦:

python程式設計透過蒙特卡羅法計算定積分詳解

python中subprocess批次執行linux指令



#

以上是Python解決N階台階走法問題的方法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn