快捷導航

c#漢諾塔的遞歸算法與解析

更新時間：2013年03月07日 17:31:19 作者：

c#漢諾塔的遞歸算法與解析，需要的朋友可以參考一下

從左到右 A B C 柱大盤子在下, 小盤子在上, 借助B柱將所有盤子從A柱移動到C柱, 期間只有一個原則: 大盤子只能在小盤子的下面.

如果有3個盤子, 大中小號, 越小的越在上面, 從上面給盤子按順序編號 1(小),2(中),3(大), 后面的原理解析引用這里的編號.

小時候玩過這個游戲, 基本上玩到第7個,第8個就很沒有耐心玩了,并且操作的動作都幾乎相同覺得無聊. 后來學習編程, 認識到遞歸, 用遞歸解決漢諾塔的算法也是我除了簡單的排序算法后學習到的第一種算法.

至于遞歸,簡單來說就是方法內(nèi)部自己調(diào)用自己, 同時也一定有一個結(jié)束點. 如果對方法調(diào)用棧了解的話,其實是很容易理解方法的調(diào)用過程的, 就是從主線程開始調(diào)用方法進行不停的壓棧和出棧操作. 方法的調(diào)入就是將方法壓入棧中, 方法的結(jié)束就是方法出棧的過程, 這樣保證了方法調(diào)用的順序流. 如果跟蹤遞歸的調(diào)用情況會發(fā)現(xiàn)也是如此, 到最后一定是這個方法最后從棧中彈出回到主線程, 并且結(jié)束.

棧的特點:先進后出。比如一個方法 A 自己調(diào)用自己, 我用編號區(qū)分一下進棧過程:

A -> A(1) -> A(2) -> A(3)

在A(3)時滿足某種條件得以退出, 回到 A(2), A(2)結(jié)束回到A(1), 再回到A, 出棧過程:

A(3) -> A(2) -> A(1) -> A

對于遞歸,還有一個形象的認識,就是我小時候家里有一個柜子, 柜子兩端都是玻璃, 頭伸進柜子看一面鏡子,會看到鏡子里還有鏡子, 然后鏡子里還有鏡子, 但和遞歸的特點不同的是這鏡子的反射是沒有盡頭的, 只要眼睛一直能看到底的話.

了解完遞歸后, 再回頭來看如何用遞歸的方式解決漢諾塔的問題.

案例 1 - 假設(shè)只有一個盤子的時候, 盤子數(shù)量 N=1

只有一個步驟將第1個盤子從A移動到C, 為了對比方便我這樣來描述這個步驟：

步驟盤子編號從柱子移動移動到柱子

1 1 A C

案例 2 - 如果有兩個盤子, 盤子數(shù)量 N = 2

步驟盤子編號從柱子移動移動到柱子

1 1 A B

2 2 A C

3 1 B C

案例 3 - 如果有三個盤子, 盤子數(shù)量 N = 3

步驟盤子編號從柱子移動移動到柱子

1 1　　　 A C

2 2　　　 A　　　　 B

3 1 C B

4 3 A C

5 1 B A

6 2 B C

7 1 A C

如何找出盤子移動的規(guī)律？

我們要做的最重要的一件事情就是永遠要把最底下的一個盤子從 A 移動到 C

看看上面從1個盤子的移動到3個盤子的移動, 在移動記錄中,當盤子的編號和盤子數(shù)量相同的時候他們的步驟都是從A移動到C (看加粗的部分),其它的步驟對等.

再觀察第3個案例中的第 1-3 步和第 5-7步

第 1-3 步目的是從 A 移動到 B 如果我們把 B 當作終點, 那么這里的第 1-3 步理解起來和第2個案例的三個步驟完全相同, 都是通過一個柱子來移動,和第2個案例比起來在后面加括號來表示

1 1　　　 A C ( A -> B)

2 2　　　 A　 B ( A -> C)

3 1 C B ( B -> C)

總結(jié)：將盤子B變成C即可.

第 5-7 步目的是從 B 移動到 C 如果我們把 C 當作終點, 那么這里的 5-7 步理解起來和上面也是一樣的, 和第2個案例的三個步驟也完全相同.和第2個案例比起來就是:

5 1 B A ( A -> B)

6 2 B C ( A- > C)

7 1 A C ( B -> C)

總結(jié): 將盤子B變成A即可

根據(jù)這個演示可以明確幾點規(guī)律:

1. 當盤子只有一個的時候,只有一個動作從 A 移動到 C 即結(jié)束.

2. 當有N個盤子的時候, 中間的動作都是從 A 移動到 C, 那么表示最下面的第N個盤子移動完畢

3. 中間動作之上都可以認為是: 從 A 移動到 B

4. 中間動作之下都可以認為是: 從 B 移動到 C

2，3，4 可以表示為

1 1 A B

2 2 A C

3 1 B C

這種結(jié)構(gòu)一直在重復(fù)進行,C#不太熟悉,試著寫寫,就有了以下代碼:

復(fù)制代碼代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{
class HanoiTower
{

        public void MoveDisk(int DiskQuantity,string PositionA, string PositionB, string PositionC)
        {
            // If there's only one disk, then end.
            if (DiskQuantity == 1)
            {
                Console.WriteLine("Move disk from position {0} to {1}.", PositionA, PositionC);
                // Must return
                return;
            }
            else
            {
                // Step 1 - Change B to C (A --> B)
                MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
                // Step 2 - No changes     (A --> C)
                MoveDisk(1, PositionA, PositionB, PositionC);
                // Step 3 - Change B to A (A --> C)
                MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
            }
        }

        static void Main(string[] args)
        {
            HanoiTower hanoi = new HanoiTower();

Console.WriteLine("Please input Disk Quantity:");
int DiskQuantity = Convert.ToInt32(Console.ReadLine());

hanoi.MoveDisk(DiskQuantity, "A", "B", "C");

            Console.ReadKey();
        }
    }
}

結(jié)合上面的分析,最重要的就是這里的3步交換動作, 中間從 A到C的動作是最底層盤子的最終操作.

// Step 1 - Change B to C (A --> B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
// Step 2 - No changes (A --> C)
MoveDisk(1, PositionA, PositionB, PositionC);
// Step 3 - Change B to A (A --> C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
至于第1個參數(shù)為什么是DiskQuantity - 1,或者1 大家再回到上面看看是不是所有的步驟都是.. 1. 1,2,1. 1,2,1,3,1,2,1 這種以盤子數(shù)對稱的結(jié)構(gòu),而它前后都是重復(fù)1,2,1 的過程.