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

這篇文章主要介紹了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,'->',c
  else:
    hanoi(a,c,b,n-1)
    print a,'->',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中文網其他相關文章！