Python基於遞歸演算法實現的漢諾塔與Fibonacci數列

不言
發布: 2018-04-18 14:28:11
原創
2537 人瀏覽過

這篇文章主要介紹了Python基於遞歸演算法實現的漢諾塔與Fibonacci數列,結合實例形式分析了漢諾塔與Fibonacci數列的遞歸實現技巧,需要的朋友可以參考下

本文實例講述了Python基於遞歸演算法實現的漢諾塔與Fibonacci數列。分享給大家供大家參考,具體如下:

這裡我們透過2個例子,學習python中遞歸的使用。

1. 找出Fibonacci數列中,下標為n 的數(下標從0計數)

Fibonacci數列的形式是這樣的:0,1,1,2,3,5,8,13……

① 使用while循環,python2程式碼如下:














#

def fib(n):
  a,b=0,1
  count=0
  while count<n:
    a,b=b,a+b
    count=count+1
  print a
登入後複製


運行結果如下:


>>> fib(0)

0

>> > fib(1)

1
>>> fib(2)

1
>>> fib(3)
2
#>> ;> fib(4)
3
>>> fib(5)
5



② 使用遞迴(遞迴必須要有邊界條件)
,python2程式碼如下:

def fib(n):
  if n==0 or n==1:#递归的边界条件
    return n
  else:
    return fib(n-1)+fib(n-2)
登入後複製

運行結果如下:

>> ;> fib(0)0>>> fib(1)1

>>> fib(2)

1

#> >> fib(3)

2>>> fib(4)

3

>>> fib(5)

5

遞歸是最能表現計算思維的演算法之一,我們以f(4)為例,看一下遞歸的執行過程:


同一程序,使用遞歸雖然程式簡潔,但遞迴的執行效率要比迴圈低,系統的資源消耗比迴圈大。因為遞歸是一層一層地往裡面調用,結束後又一層一層地返回,所以遞歸的執行效率並不高。那為什麼還要使用遞迴呢?因為有一些問題,我們找不到非常明顯的循環方案,但很容易找到明顯的遞歸方案。比如說著名的漢諾塔問題。


2. 漢諾塔


下圖是簡化版的漢諾塔遊戲,只有4個盤子:




漢諾塔遊戲規則如下:




#python2程式碼如下:

def hanoi(a,b,c,n):
  if n==1:#递归结束条件
    print a,&#39;->&#39;,c
  else:
    hanoi(a,c,b,n-1)
    print a,&#39;->&#39;,c
    hanoi(b,a,c,n-1)
登入後複製

運行結果:

>>> hanoi('A','B','C',1)A -> C>>> hanoi('A','B','C',2)

A -> B

A -> C
B -> C

>>> hanoi('A','B','C',3)###A -> C###A -> B###C -> B###A - > C###B -> A###B -> C###A -> C####################相關推薦:### ######神經網路(BP)演算法Python實作及應用################

以上是Python基於遞歸演算法實現的漢諾塔與Fibonacci數列的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板