快捷導(dǎo)航

C語(yǔ)言遞歸思想實(shí)現(xiàn)漢諾塔詳解

更新時(shí)間：2022年01月21日 11:49:50 作者：weixin_58165485

大家好，本篇文章主要講的是C語(yǔ)言遞歸思想實(shí)現(xiàn)漢諾塔詳解，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下

1.遞歸思想簡(jiǎn)介

在c語(yǔ)言中，程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。

遞歸的定義看上去似乎很抽象，使用代碼描述能夠讓人容易理解，下面是一個(gè)函數(shù)遞歸的例子。

/*                                遞歸求n的階乘                        */
 
 
int factorial(int n)  //定義一個(gè)求階乘的函數(shù)叫做factorial(),需要一個(gè)整形參數(shù)，返回一個(gè)整形值
{
	if (n <= 1)       //遞歸結(jié)束的條件
	{
		return 1;
	}
	else
	{
		return n * factorial(n - 1);//在factorial()中再次調(diào)用自身，只不過參數(shù)由n變成n-1
	}	
}

在這個(gè)例子中，函數(shù) factorial()接收到一個(gè)整形數(shù)n，如n=5，暫時(shí)稱作F(5)，這時(shí)n!=F(5)，而函數(shù)的功能如下：

判斷5是否小于或等于1，如果是，將1返回；不是，進(jìn)到else執(zhí)行語(yǔ)句返回（這里可以將return看作等于）5× factorial(n - 1)，等價(jià)于 F(5)=5×F(4)用上面的方法計(jì)算F(4)=4×F(3)....以此類推直到達(dá)到限制條件n=1時(shí)有，F(xiàn)(1)=1

遞歸算法的實(shí)質(zhì)：是把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題。

由于每個(gè)小問題處理起來都有與大問題類似的行為邏輯，因此我們可以“大事化小”，而遞歸說白了，就是不斷地在套娃。

但是，計(jì)算機(jī)的內(nèi)存是有限的，由于每次調(diào)用函數(shù)都需要在棧區(qū)開辟一個(gè)空間，使得遞歸不能無(wú)限制地進(jìn)行下去，沒有遞歸結(jié)束的條件，當(dāng)操作系統(tǒng)為進(jìn)程分配的虛擬地址空間當(dāng)中的?？臻g被耗盡時(shí)，會(huì)發(fā)生堆棧溢出，產(chǎn)生段錯(cuò)誤(segmentation fault)。

因此，使用遞歸時(shí)應(yīng)注意：

必須存在限制條件，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)每次遞歸調(diào)用之后越來越接近這個(gè)限制條件

遞歸的好處在于：

代碼簡(jiǎn)潔在某些特定問題上求解方便

遞歸的缺點(diǎn)在于

消耗大量時(shí)間和空間資源——效率較低可能伴隨許多重復(fù)計(jì)算，工作量大——影響性能

2.漢諾塔問題

以下內(nèi)容來自維基百科

最早發(fā)明這個(gè)問題的人是法國(guó)數(shù)學(xué)家愛德華·盧卡斯。

傳說越南河內(nèi)某間寺院有三根銀棒，上串 64 個(gè)金盤。寺院里的僧侶依照一個(gè)古老的預(yù)言，以上述規(guī)則移動(dòng)這些盤子；預(yù)言說當(dāng)這些盤子移動(dòng)完畢，世界就會(huì)滅亡。這個(gè)傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創(chuàng)的這個(gè)傳說，還是他受他人啟發(fā)。

若傳說屬實(shí)，僧侶們需要 $2^{64}-1$ 步才能完成這個(gè)任務(wù)；若他們每秒可完成一個(gè)盤子的移動(dòng)，就需要 5849 億年才能完成。整個(gè)宇宙現(xiàn)在也不過 137 億年。

這個(gè)傳說有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點(diǎn)眾說紛紜，其中一說是位于越南的河內(nèi)，所以被命名為“河內(nèi)塔”。另外亦有“金盤是創(chuàng)世時(shí)所造”、“僧侶們每天移動(dòng)一盤”之類的背景設(shè)定

漢諾塔基本的玩法如圖，其規(guī)則是：將圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

當(dāng)圓盤數(shù)量只有3個(gè)的時(shí)候，求解的方法顯而易見，但當(dāng)數(shù)量增多時(shí)，問題變得有些棘手起來。但不管怎么移動(dòng)，核心思想都是遞歸：

先從n塊圓盤中將最大的一塊移動(dòng)到最后的柱子上接著從剩下n-1找到最大的一塊移到柱子上......

3.漢諾塔遞歸的c語(yǔ)言實(shí)現(xiàn)

C語(yǔ)言代碼如下：

/*                            漢諾塔問題（遞歸實(shí)現(xiàn)）                     */
 
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
void move(char, char); // 聲明一個(gè)函數(shù)move，函數(shù)定義在下方，用于表示圓盤的交換
 
void Towers_Of_Hanoi(int n,char a,char b,char c) 
{
	if (1 == n)                        //遞歸結(jié)束標(biāo)志：當(dāng)柱子上只有一塊圓盤
	{
		move(a, c);                    //從a移動(dòng)到c
	}
	else
		Towers_Of_Hanoi(n - 1, a, c, b);    //將最上面n-1個(gè)圓盤移動(dòng)到b柱上
		move(a, c);                         //將a上面最后一塊圓盤移動(dòng)到c柱上
		Towers_Of_Hanoi(n - 1, b, a, c);    //將b柱上n-1個(gè)圓盤移動(dòng)到a柱上
	}
}
 
void move(char x, char y)
{
	printf("%c-->%c\n", x, y);
}
 
int main()
{
	int n = 0;
	scanf("%d", &n);
	Towers_Of_Hanoi(n, 'A', 'B', 'C');//n為A柱子上圓盤的數(shù)量，A,B,C代表三根柱子
	return 0;
}

程序運(yùn)行結(jié)果為：