漢諾塔的兩種非遞歸解法

yangtou

[code]
如同我們能求出fabonacci數(shù)列的表達(dá)式，一定能用歸納的辦法解決hanoi問(wèn)題。

1 基本規(guī)律：
        最容易看出的規(guī)律就是盤子移動(dòng)的序列：
給盤子從小到大編號(hào)1，2，……，N,試驗(yàn)移動(dòng)盤子則可以得到一個(gè)這樣的盤子移動(dòng)序列（可以叫他hanoi數(shù)列H(n)）：
1，2，1， 3， 1，2，1，    4      ，1，2，1， 3， 1，2，1，………
容易歸納出，1占據(jù)所有的奇數(shù)位，2占據(jù)所有序號(hào)可被2整除而不能被4整除的位，。。。。。。m占了能被2^(m-1)整除而不能被2^m整除的所有的位置。。。。。。。。由此可得，對(duì)m=((p*2^k) + 2^k-1),H(m)=k。很容易用數(shù)學(xué)歸納法證明。
這樣就可以隨機(jī)得到某一步所移動(dòng)的盤子了。

另一方面，還要確定某一個(gè)盤子是往哪而移動(dòng)的。這一點(diǎn)不容易直接想到，但是通過(guò)實(shí)驗(yàn)可以發(fā)現(xiàn)，在某一個(gè)盤子數(shù)N下，1號(hào)盤子的移動(dòng)方向總是一定的。方向一定就是說(shuō)，總是按照1