c#漢諾塔的遞歸算法與解析
從左到右 A B C 柱 大盤子在下, 小盤子在上, 借助B柱將所有盤子從A柱移動(dòng)到C柱, 期間只有一個(gè)原則: 大盤子只能在小盤子的下面.
如果有3個(gè)盤子, 大中小號(hào), 越小的越在上面, 從上面給盤子按順序編號(hào) 1(小),2(中),3(大), 后面的原理解析引用這里的編號(hào).
小時(shí)候玩過這個(gè)游戲, 基本上玩到第7個(gè),第8個(gè)就很沒有耐心玩了,并且操作的動(dòng)作都幾乎相同覺得無聊. 后來學(xué)習(xí)編程, 認(rèn)識(shí)到遞歸, 用遞歸解決漢諾塔的算法也是我除了簡單的排序算法后學(xué)習(xí)到的第一種算法.
至于遞歸,簡單來說就是方法內(nèi)部自己調(diào)用自己, 同時(shí)也一定有一個(gè)結(jié)束點(diǎn). 如果對(duì)方法調(diào)用棧了解的話,其實(shí)是很容易理解方法的調(diào)用過程的, 就是從主線程開始調(diào)用方法進(jìn)行不停的壓棧和出棧操作. 方法的調(diào)入就是將方法壓入棧中, 方法的結(jié)束就是方法出棧的過程, 這樣保證了方法調(diào)用的順序流. 如果跟蹤遞歸的調(diào)用情況會(huì)發(fā)現(xiàn)也是如此, 到最后一定是這個(gè)方法最后從棧中彈出回到主線程, 并且結(jié)束.
棧的特點(diǎn):先進(jìn)后出。 比如一個(gè)方法 A 自己調(diào)用自己, 我用編號(hào)區(qū)分一下進(jìn)棧過程:
A -> A(1) -> A(2) -> A(3)
在A(3)時(shí)滿足某種條件得以退出, 回到 A(2), A(2)結(jié)束回到A(1), 再回到A, 出棧過程:
A(3) -> A(2) -> A(1) -> A
對(duì)于遞歸,還有一個(gè)形象的認(rèn)識(shí),就是我小時(shí)候家里有一個(gè)柜子, 柜子兩端都是玻璃, 頭伸進(jìn)柜子看一面鏡子,會(huì)看到鏡子里還有鏡子, 然后鏡子里還有鏡子, 但和遞歸的特點(diǎn)不同的是這鏡子的反射是沒有盡頭的, 只要眼睛一直能看到底的話.
了解完遞歸后, 再回頭來看如何用遞歸的方式解決漢諾塔的問題.
案例 1 - 假設(shè)只有一個(gè)盤子的時(shí)候, 盤子數(shù)量 N=1
只有一個(gè)步驟 將第1個(gè)盤子從A移動(dòng)到C, 為了對(duì)比方便我這樣來描述這個(gè)步驟：
步驟 盤子編號(hào) 從柱子移動(dòng) 移動(dòng)到柱子
1 1 A C
案例 2 - 如果有兩個(gè)盤子, 盤子數(shù)量 N = 2
步驟 盤子編號(hào) 從柱子移動(dòng) 移動(dòng)到柱子
1 1 A B
2 2 A C
3 1 B C
案例 3 - 如果有三個(gè)盤子, 盤子數(shù)量 N = 3
步驟 盤子編號(hào) 從柱子移動(dòng) 移動(dòng)到柱子
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
如何找出盤子移動(dòng)的規(guī)律 ？
我們要做的最重要的一件事情就是永遠(yuǎn)要把最底下的一個(gè)盤子從 A 移動(dòng)到 C
看看上面從1個(gè)盤子的移動(dòng)到3個(gè)盤子的移動(dòng), 在移動(dòng)記錄中,當(dāng)盤子的編號(hào)和盤子數(shù)量相同的時(shí)候他們的步驟都是從A移動(dòng)到C (看加粗的部分),其它的步驟對(duì)等.
再觀察第3個(gè)案例中的第 1-3 步 和 第 5-7步
第 1-3 步 目的是從 A 移動(dòng)到 B 如果我們把 B 當(dāng)作終點(diǎn), 那么這里的第 1-3 步理解起來和 第2個(gè)案例的三個(gè)步驟完全相同, 都是通過一個(gè)柱子來移動(dòng),和第2個(gè)案例比起來在后面加括號(hào)來表示
1 1 A C ( A -> B)
2 2 A B ( A -> C)
3 1 C B ( B -> C)
總結(jié)：將盤子B變成C即可.
第 5-7 步 目的是從 B 移動(dòng)到 C 如果我們把 C 當(dāng)作終點(diǎn), 那么這里的 5-7 步理解起來和上面也是一樣的, 和第2個(gè)案例的三個(gè)步驟也完全相同.和第2個(gè)案例比起來就是:
5 1 B A ( A -> B)
6 2 B C ( A- > C)
7 1 A C ( B -> C)
總結(jié): 將盤子B變成A即可
根據(jù)這個(gè)演示可以明確幾點(diǎn)規(guī)律:
1. 當(dāng)盤子只有一個(gè)的時(shí)候,只有一個(gè)動(dòng)作 從 A 移動(dòng)到 C 即結(jié)束.
2. 當(dāng)有N個(gè)盤子的時(shí)候, 中間的動(dòng)作都是從 A 移動(dòng)到 C, 那么表示最下面的第N個(gè)盤子移動(dòng)完畢
3. 中間動(dòng)作之上都可以認(rèn)為是: 從 A 移動(dòng)到 B
4. 中間動(dòng)作之下都可以認(rèn)為是: 從 B 移動(dòng)到 C
2，3，4 可以表示為
1 1 A B
2 2 A C
3 1 B C
這種結(jié)構(gòu)一直在重復(fù)進(jìn)行,C#不太熟悉,試著寫寫,就有了以下代碼:
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步交換動(dòng)作, 中間從 A到C的動(dòng)作是最底層盤子的最終操作.
// 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個(gè)參數(shù)為什么是DiskQuantity - 1,或者1 大家再回到上面看看是不是所有的步驟都是.. 1. 1,2,1. 1,2,1,3,1,2,1 這種以盤子數(shù)對(duì)稱的結(jié)構(gòu),而它前后都是重復(fù)1,2,1 的過程.
相關(guān)文章
c#項(xiàng)目實(shí)現(xiàn)發(fā)布到服務(wù)器全過程
這篇文章主要介紹了c#項(xiàng)目實(shí)現(xiàn)發(fā)布到服務(wù)器全過程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-04-04
C#難點(diǎn)逐個(gè)擊破（3）:params數(shù)組參數(shù)
注意，這里的paras全稱是array parameter，也就是數(shù)組參數(shù)。 paras類型參數(shù)主要用于在對(duì)數(shù)組長度未知（可變）的情況下進(jìn)行函數(shù)聲明。2010-02-02
C# 讀寫自定義的Config文件的實(shí)現(xiàn)方法
本文主要介紹了C# 讀寫自定義的Config文件的實(shí)現(xiàn)方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
這篇文章介紹了在WPF中使用FontAwesome字體圖標(biāo)的方法，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
通過C#和RTSPClient實(shí)現(xiàn)簡易音視頻解碼功能
在多媒體應(yīng)用中,實(shí)時(shí)傳輸協(xié)議（RTSP）用于流媒體服務(wù),特別是音視頻?監(jiān)控系統(tǒng),通過?C#?和?RTSPClient?庫,可以輕松實(shí)現(xiàn)簡易的音視頻解碼和播放功能,本文將詳細(xì)介紹如何使用?C#?和?RTSPClient?構(gòu)建一個(gè)簡易但高效的音視頻解碼器,需要的朋友可以參考下2024-12-12
C#讀取XML中元素和屬性值的實(shí)現(xiàn)代碼
用C#讀取xml有很多方式，這里我就先使用XmlDocument讀取Xml，用一段代碼遍歷所有元素，并打印student的所有屬性和子節(jié)點(diǎn)的值2013-04-04
基于C#實(shí)現(xiàn)的仿windows左側(cè)伸縮菜單效果
