遞歸(漢諾塔)問題？

javascript

hungchinwai 2010-04-27 01:04:01 ‧ 5731 瀏覽

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

總裁 iT邦好手 1 級 ‧ 2010-05-01 14:48:28 檢舉

很抱歉, 我要來潑個冷水, 如果理解這種遞迴對您來講很吃力, 我勸您以後別走研發這條路, 尤其是AI.

fillano iT邦超人 1 級 ‧ 2010-05-03 11:51:17 檢舉

我覺得樓主大可能沒注意到第二次呼叫hanoi函數時，傳進去的參數不一樣。

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

2 個回答

fillano

iT邦超人 1 級 ‧ 2010-04-27 09:54:59

最佳解答

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

回應 9
分享
檢舉

看更多先前的回應...收起先前的回應...

hungchinwai iT邦研究生 1 級 ‧ 2010-04-27 11:00:25 檢舉

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

海綿寶寶 iT邦大神 1 級 ‧ 2010-04-27 11:23:18 檢舉

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

海綿寶寶 iT邦大神 1 級 ‧ 2010-04-27 11:23:41 檢舉

&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 級 ‧ 2010-04-27 11:23:59 檢舉

&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 級 ‧ 2010-04-27 14:59:06 檢舉

另一種觀察，遞迴深度：

&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 級 ‧ 2010-04-28 02:50:14 檢舉

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

hungchinwai iT邦研究生 1 級 ‧ 2010-04-30 17:57:23 檢舉

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

海綿寶寶 iT邦大神 1 級 ‧ 2010-04-30 23:30:42 檢舉

其實你沒有看懂...

我換個方式解釋看看
基本上
這個函數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)