2021年12月14日 星期二

Python 程式練習 5 ─ 河內塔

http://4rdp.blogspot.com/2021/12/python-5.html?m=0

如左圖所示,有一碟盤子尺寸由下而上依次變小,然後要搬移這些盤子從最左搬到最右邊,中間有一個緩衝區,所以共有三處可以放盤子,搬動的規則如下:
一、每次只能搬一個盤子
二、大盤子不能疊在小盤子上面

請用遞迴的方法,寫出 N 個盤子,需要幾步才能完成所有盤子的搬移?

有些特定的問題需要用特定的方法才能解,比如河內塔就需要遞迴解題。

所有的 FOR loop 都可以用遞迴來處理,若說傳統 FOR loop 是以正向思考解決問題,那遞迴就是逆向思考來解問題,不過它有個前提,這問題須能在有限步驟內解決,而且處理問題也不能中途停止,因為這將會沒有解答可以逆推出結果。

最近 Andy 計算機概論課程上了遞迴 (Recursion),這對資工的同學是非常重要的程式設計技巧,老師出了 一些作業,他寫的唉唉叫,問我會不會,雖然我有多年程式經驗,但遞迴不是我熟悉的程式技巧,因此沒辦法幫他甚麼忙,他看了同學程式範例兩天,然後親自寫河內塔程式,才充分悟道,因此他建議學習這個單元的同學,一定要寫一遍河內塔程式,就可以搞清楚遞迴機制,他學習遞迴這方法後的心得是分而治之 (Divide and Conquer),就是要切割問題,然後一塊一塊處理掉。

2 則留言:

  1. that's a classic coding question! tks for sharing.

    回覆刪除
    回覆
    1. You are welcome to visit my blog. If you have any questions, I will be happy to answer them.

      刪除