簡化漢諾塔

這段代碼是將無論多么復雜的漢諾塔都簡化為三步嗎？但現實中的漢諾塔是要(2**n-1)步是不是可以這樣理解這段代碼并不能完全打印出全部步驟只是三步而已 ? 大神在上

胡說魚

2017-07-28

源自：初識Python 7-5

關注問題我要回答

515

操作

收起

1 回答

折翼舞_0 回答被采納 +2 積分
2017-07-28

對，無論多復雜都是三步，不過，這三步是從宏觀上來看的，你看第一步，就是一個自調用（自調用里面還有自調用，也就是遞歸），第三步又是一個自調用，只有n==1成立時，才停止遞歸。

1 回復有任何疑惑可以回復我~

收起回答

折翼舞_0

從這里無窮的自調用就能看出并不是只要三步就能移動完

2017-07-28 回復有任何疑惑可以回復我~

折翼舞_0

實際上，真正在移動的就是第二步，第一和三其實還是交給了遞歸處理，也就是說，每次執行一次自調用，就是移動一次（第二步），每次自調用里面又執行了二次自調用，我們把這個遞歸函數的深度看作n（如果學過數據結構可以看做深度為n的樹），在深度為1時，移動了一次（第二步），同時產生兩個分支（一和三步），形成兩個節點，處于深度為2的空間，然后每個分支會再移動一次（第二步），并產生2個分支，形成兩個節點，處于下一個深度的空間，一直到遞歸結束，

2017-07-28 回復有任何疑惑可以回復我~

折翼舞_0

可見每個節點就相當于移動一次，深度為n的空間存在2^(n-1)（2的n-1次方）個節點，全部節點數（即總移動次數）也就是 2^0 + 2^1 + …… + 2^(n-1) ,即 2^n - 1。 (次數沒有錯誤，可以打印全部結果)至于為什么2^0 + 2^1 + …… + 2^(n-1) = 2^n - 1。。。?？梢阅嫱疲? 就是 2^0, 1+ 2^0 = 2^1 , 2^1 + 2^1 =2^2…………你試著自己加加看，1+2^0 + 2^1 + …… + 2^(n-1) 就是 2^n。

2017-07-28 回復有任何疑惑可以回復我~

查看1條回復

舉報

0/150

提交

取消

初識Python

參與學習 758383 人
解答問題 8967 個

學python入門視頻教程，讓你快速入門并能編寫簡單的Python程序

進入課程

簡化漢諾塔

我要回答關注問題

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

簡化漢諾塔

1 回答

簡化漢諾塔