簡介

也翻譯作漢諾塔,這是根據一個傳說演變而成的題目,題目的規則如下:

  1. 有三根竿子,例如編號為A、B和C,竿子上面可串中空圓盤。
  2. 於A竿子放入N個盤子開始,盤子由下至上變小。
  3. 一次只能移動一個盤子。
  4. 大盤子不能再小盤子上面。
  5. 目標將全部盤子移動到C竿子。

imagesCAE2X6WV   

補充資料

移動次數的數學公式為2N - 1

題目

現在我們嘗試上面的問題撰寫成程式解決,依據上面的說明,寫出程式印出移動的步驟。

解法

此題目一般可使用Divide and Conquer來解,當有N個盤子的時候很難思考,我們假設只有兩個盤子的時候,就很好思考,只需要:

  1. 將上面的盤子移到暫時擺放的竿子。
  2. 將下面的盤子移到目標竿子。
  3. 將原來上面的盤子移到目標竿子。

而當盤子N個的時候,其實也是依照同樣的邏輯進行即可,但上面N-1個盤子要如何移到暫時擺放的竿子,這時候我們用遞迴的方式交給下一次呼叫自己去處理。

未命名  

虛擬碼

function move(disks, from, to)
	if disks == 1
		自訂的移動動作
	else
		move(disks - 1, from, 另一竿子)
		move(1, from, to)
		move(disks - 1, 另一竿子, to)
	end if
end function

語法

這邊簡單將竿子用1,2,3編號

C#

        static void Move(int disks, int from, int to)
        {
            if (disks == 1)
            {
                Console.WriteLine("Move from {0} to {1}", from, to);
                return;
            }

            int relay = 6 - from - to;
            Move(disks - 1, from, relay);
            Move(1, from, to);
            Move(disks - 1, relay, to);
        }

Java

	public static void Move(int disks, int from, int to)
	{
		if(disks == 1)
		{
			System.out.println("Move from " + from + " to " + to);
			return;
		}
		
		int relay = 6 - from - to;
		Move(disks - 1, from, relay);
		Move(1, from, to);
		Move(disks - 1, relay, to);
	}

C++

void move(int disks, int from, int to)
{
    if(disks == 1)
    {
        cout << "Move from " << from << " to " << to << endl;
        return;
    }
    int relay = 6 - from - to;
    move(disks - 1, from, relay);
    move(1, from, to);
    move(disks - 1, relay, to);
}

下載

VS2010 C# 版本

Eclipse Java 版本

Code::Blocks C++ 版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()