函式遞回演算法的運用有一個經典例題，那就是漢諾塔問題，接下來就讓我們一起來看看如何用函式遞回來解決漢諾塔問題叭！
漢諾塔問題的起源：
漢諾塔（又稱河內塔）問題是印度的一個古老的傳說，開天辟地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面，面對龐大的數字(移動圓片的次數)18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動，后來，這個傳說就演變為漢諾塔游戲，
漢諾塔游戲 規則：
簡單來說，就是把a柱上的n個圓盤，通過b柱作為輔助全部搬運到c柱上去，在搬運的程序中一次只能搬運一個圓盤，而且大圓盤不能放到小圓盤上面，
什么是遞回？
要用遞回的方法解決這個問題，我們首先要知道何為遞回，
遞回就是一個函式在它的函式體內呼叫它自身，執行遞回函式將反復呼叫其自身，每呼叫一次就進入新的一層，遞回函式必須有結束條件，
當函式在一直遞推，直到遇到墻后回傳，這個墻就是結束條件，
所以遞回要有兩個要素，結束條件與遞推關系，
問題分析：
我們很容易知道：
當n=1時，我們直接將盤子從a柱移到c柱便解決了問題，
當n=2時，我們可以先把a柱上的第一個盤子移動到b柱（a柱最上面的盤子編號為1，向下依次遞增），然后將a柱上的第二個盤子移動到c柱，再將b柱上的盤子移動到c柱即可，
但是當n的值為3及以上時問題便變得麻煩起來了，那么我們能否將后面復雜的問題化簡為前面簡單的兩種情況呢？
答案是肯定的，這也是函式遞回的目的：將復雜的問題簡單化，
代碼實作：
我們只需將盤子個數為n的分為兩類解決即可：
當n=1時，將盤子從a->c即可，
當n>1時，將a柱上的n-1個盤子移動到b柱上，再將a柱上剩下的一個（也就是第n個）移動到c柱上，然后將b柱上的n-1個移動到，c柱上即可，（記住我們這里是將n-1個盤子看為一個整體）
其中void move(int n, char a, char b, char c)表示你要將n個盤子從a柱上通過b柱移動到c柱上，（通過你傳入的數字即字符來實作相應操作）
編程完成后我們可以輸入一個比較容易檢測的數來看看程式是否正確，
個人看法：
在我看來漢諾塔問題包括大多數能用函式遞回解決的問題都需要我們有一種能力，那就是將一些東西當作一個整體來看待，比如漢諾塔問題中我們就要將n-1看作一個整體，如果不能做到有這種理解能力，那么將很難理解如何用函式遞回解決漢諾塔問題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250752.html
標籤：其他
上一篇：位運算(上)