Python中怎么利用遞歸算法實現漢諾塔

本篇文章為大家展示了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

上述內容就是Python中怎么利用遞歸算法實現漢諾塔，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。