人人IT網

人人IT網

當前位置: 主頁 > 編程語言 > C >

每天一算法(雙色河內塔又叫漢諾塔)

時間:2012-12-19 13:52來源:Internet 作者:Internet 點擊:
說明 雙色河內塔是由之前所介紹過的河內塔規則衍生而來,雙色河內塔的目的是將下圖左上的圓環位置經移動成为右下的圓環位置: 解法 雙色河內塔或是原始的河內塔,其解法觀念與之前介紹過的河內塔是類

說明

雙色河內塔是由之前所介紹過的河內塔規則衍生而來,雙色河內塔的目的是將下圖左上的圓環位置經移動成为右下的圓環位置:


解法

雙色河內塔或是原始的河內塔,其解法觀念與之前介紹過的河內塔是類似的,同样也是使用遞回來解,不過這次遞回解法的目的不同,我們來看雙色的情況,這很簡單,
只要將第一柱的黃色移動至第二柱,而接下來第一柱的藍色移動至第三柱。再來是四個盤的情況,首先必須用遞回完成下圖左上至右下的移動:



接下來最底層的就不用管它們了,因为它們已經就定位,只要再處理第一柱的上面兩個盤子就可以了。那麼六個盤的情況呢?一样!首先必須用遞回完成下圖左上至右下的移動:



接下來最底層的就不用管它們了,因为它們已經就定位,只要再處理第一柱上面的四個盤子就可以了,這又與之前只有四盤的情況相同,接下來您就知道該如何進行解題了,無論是八個盤、十個盤以上等,都是用這個觀念來解題。

簡單的寫一下程序:


//將在B中最底下的兩個,,上邊一個移動到C
void Move1(char B,char C)
{
	cout<<"將一個從"<<B<<"移動到"<<C<<endl;
}
//將n個從A移動到C
void Move2(int n,char A,char B,char C)
{
	if (n<1)
	{
		return ;
	}
	
	if (1 == n)
	{
		cout<<"將兩個從"<<A<<"一個一個移動到"<<C<<endl;
	}
	else
	{
		Move2(n-1,A,C,B);
		Move2(1,A,B,C);
		Move2(n-1,B,A,C);
	}
	
}

void Move3(int n)
{
	if (n == 1)
	{
		Move2(1,'A','C','B');
		Move1('B','C');
		return;
	}
	

	Move2(n-1,'A','B','C');
	Move2(1,'A','C','B');
	Move2(n-1,'C','B','A');
	Move1('B','C');
	Move3(n-1);
	
}

int main()
{
	Move3(4);
}



From:CSDN
頂一下
(0)
0%
踩一下
(0)
0%
------分隔線----------------------------
發表評論
請自覺遵守互聯網相關的政策法規,嚴禁發布色情、暴力、反動的言論。
評價:
表情:
驗證碼:點擊我更換圖片
欄目列表
推薦內容