iT邦幫忙

0

遞歸(漢諾塔)問題?

hungchinwai 7 年前5047 瀏覽

<script language="javascript">
var hanoi = function (disc, src, aux, dst){
if (disc > 0) {
hanoi(disc-1, src, dst, aux);
document.write('Move disc ' + disc +' from ' + src + ' to ' + dst+'<br>');
hanoi(disc-1, aux, src, dst);
}
}
hanoi(3, 'Src', 'Aux', 'Dst');
</SCRIPT>
結果輸出:
Move disc 1 from Src to Dst
Move disc 2 from Src to Aux
Move disc 1 from Dst to Aux
Move disc 3 from Src to Dst
Move disc 1 from Aux to Src
Move disc 2 from Aux to Dst
Move disc 1 from Src to Dst

請問各位先進,可以幫我解釋上述的javascript遞歸程式嗎(從頭至尾的運作),本人實在不解,謝謝?

總裁 iT邦好手 1 級 ‧ 7 年前 檢舉
很抱歉, 我要來潑個冷水, 如果理解這種遞迴對您來講很吃力, 我勸您以後別走研發這條路, 尤其是AI.
fillano iT邦超人 1 級 ‧ 7 年前 檢舉
我覺得樓主大可能沒注意到第二次呼叫hanoi函數時,傳進去的參數不一樣。

2 個回答

18
fillano
iT邦超人 1 級 ‧ 7 年前
最佳解答

你都把解法過程印出來了...你可以自己追蹤函數執行的過程阿,例如用另一個document.write在函數一開始的時候把傳進來的參數印出來並且標示是剛進入函數,同時在函數結尾的地方做一次並且標示是離開函數前,你就會比較清楚執行過程了。

看更多先前的回應...收起先前的回應...
hungchinwai iT邦研究生 1 級 ‧ 7 年前 檢舉

這位先進,我有試過這個方法,但不解的是disc明明呼叫時都是減1的狀態,可是為何if(disc > 0)最後應該會結束,但還是會列出Move disc 1 from Src to Dst,而且會跳過我之前要輸出值的程式碼,不知我這樣說明先進清不清楚。

海綿寶寶 iT邦超人 1 級 ‧ 7 年前 檢舉

你的問題是在下方執行結果的第3,8,14,19列
以第3列來看
以disc=1執行呼叫後進入函數內部
第4列disc-1=0
第6列disc-1=0
而第5列就是原來的disc
也就是 move 1 過去

海綿寶寶 iT邦超人 1 級 ‧ 7 年前 檢舉
&lt;pre class="c" name="code">
&lt;HTML>
&lt;script language="javascript">
	var cnt=0;
	var hanoi = function (disc, src, aux, dst){
		document.write(++cnt + '.' + 'calling hanoi disc:' + disc + ' from:' + src + ' to:' + dst + ' &lt;/br>');
		if (disc > 0) {
			hanoi(disc-1, src, dst, aux);
			document.write(++cnt + '.' + '-----Move disc ' + disc +' from ' + src + ' to ' + dst+'&lt;br>');
			hanoi(disc-1, aux, src, dst);
		}
	}
	hanoi(3, 'Src', 'Aux', 'Dst');
&lt;/SCRIPT>
&lt;/HTML>
海綿寶寶 iT邦超人 1 級 ‧ 7 年前 檢舉
&lt;pre class="c" name="code">
執行結果
1.calling hanoi disc:3 from:Src to:Dst
2.calling hanoi disc:2 from:Src to:Aux
3.calling hanoi disc:1 from:Src to:Dst
4.calling hanoi disc:0 from:Src to:Aux
5.-----Move disc 1 from Src to Dst
6.calling hanoi disc:0 from:Aux to:Dst
7.-----Move disc 2 from Src to Aux
8.calling hanoi disc:1 from:Dst to:Aux
9.calling hanoi disc:0 from:Dst to:Src
10.-----Move disc 1 from Dst to Aux
11.calling hanoi disc:0 from:Src to:Aux
12.-----Move disc 3 from Src to Dst
13.calling hanoi disc:2 from:Aux to:Dst
14.calling hanoi disc:1 from:Aux to:Src
15.calling hanoi disc:0 from:Aux to:Dst
16.-----Move disc 1 from Aux to Src
17.calling hanoi disc:0 from:Dst to:Src
18.-----Move disc 2 from Aux to Dst
19.calling hanoi disc:1 from:Src to:Dst
20.calling hanoi disc:0 from:Src to:Aux
21.-----Move disc 1 from Src to Dst
22.calling hanoi disc:0 from:Aux to:Dst 
fillano iT邦超人 1 級 ‧ 7 年前 檢舉

另一種觀察,遞迴深度:

&lt;pre class="c" name="code">
&lt;script language="javascript">
var depth = 0;
var hanoi = function (disc, src, aux, dst){
	depth++;
	if (disc > 0) {
		hanoi(disc-1, src, dst, aux);
		document.write('depth:'+depth+', Move disc ' + disc +' from ' + src + ' to ' + dst+'&lt;br>');
		hanoi(disc-1, aux, src, dst);
	}
	depth--;
}
hanoi(3, 'Src', 'Aux', 'Dst');
&lt;/script>
shunyuan iT邦研究生 1 級 ‧ 7 年前 檢舉

大師一出手,就知有沒有。

hungchinwai iT邦研究生 1 級 ‧ 7 年前 檢舉

謝謝先進的指教,我已看的懂1-6行輸出結果,但7.-----Move disc 2 from Src to Aux這個輸出結果的disc 2從哪裡來,本人真的太愚笨了,請先進可否再次解除疑惑。

海綿寶寶 iT邦超人 1 級 ‧ 7 年前 檢舉

其實你沒有看懂...

我換個方式解釋看看
基本上
這個函數f(n)是由三個部份組成
n>0時,f(n)是f(n-1)及一列'Move..'及f(n-1)
n=0時,f(n)什麼事都不做
以下我列出各階層三個部份的列號
提供您參考看看
hanoi(3)=(2-11)(12)(13-22)
hanoi(2)=(3-6)(7)(8-11)
hanoi(1)=(4-6)
hanoi(1)=(9-11)
hanoi(2)=(14-17)(18)(19-22)
hanoi(1)=(15-17)
hanoi(1)=(20-22)

總裁 iT邦好手 1 級 ‧ 7 年前 檢舉

您可以先試著把簡單的FOR迴圈改成用遞迴寫看看, 如果這是您看的第一個遞迴程式, 那是有一點難.

8
marshuang
iT邦新手 1 級 ‧ 7 年前

這是老掉牙的問題,請見資料結構.

我要發表回答

立即登入回答