C語言怎么實現漢諾塔

這篇文章主要介紹了C語言怎么實現漢諾塔的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C語言怎么實現漢諾塔文章都會有所收獲，下面我們一起來看看吧。

1.遞歸思想簡介

在c語言中，程序調用自身的編程技巧稱為遞歸（ recursion）。

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

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

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

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

遞歸算法的實質：是把問題轉化為規模縮小了的同類問題的子問題。然后遞歸調用函數(或過程)來表示問題。

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

但是，計算機的內存是有限的，由于每次調用函數都需要在棧區開辟一個空間，使得遞歸不能無限制地進行下去，沒有遞歸結束的條件，當操作系統為進程分配的虛擬地址空間當中的棧空間被耗盡時，會發生堆棧溢出，產生段錯誤(segmentation fault)。

因此，使用遞歸時應注意：

必須存在限制條件，當滿足這個限制條件的時候，遞歸便不再繼續每次遞歸調用之后越來越接近這個限制條件 

遞歸的好處在于：

代碼簡潔在某些特定問題上求解方便

遞歸的缺點在于

消耗大量時間和空間資源——效率較低可能伴隨許多重復計算，工作量大——影響性能

2.漢諾塔問題

以下內容來自維基百科

最早發明這個問題的人是法國數學家愛德華·盧卡斯。

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

若傳說屬實，僧侶們需要步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。

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

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

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

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

3.漢諾塔遞歸的c語言實現

C語言代碼如下：

/*                            漢諾塔問題（遞歸實現）                     */
 
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
void move(char, char); // 聲明一個函數move，函數定義在下方，用于表示圓盤的交換
 
void Towers_Of_Hanoi(int n,char a,char b,char c) 
{
	if (1 == n)                        //遞歸結束標志：當柱子上只有一塊圓盤
	{
		move(a, c);                    //從a移動到c
	}
	else
		Towers_Of_Hanoi(n - 1, a, c, b);    //將最上面n-1個圓盤移動到b柱上
		move(a, c);                         //將a上面最后一塊圓盤移動到c柱上
		Towers_Of_Hanoi(n - 1, b, a, c);    //將b柱上n-1個圓盤移動到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柱子上圓盤的數量，A,B,C代表三根柱子
	return 0;
}

程序運行結果為：

關于“C語言怎么實現漢諾塔”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C語言怎么實現漢諾塔”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。