C語言遞歸思想實(shí)現(xiàn)漢諾塔詳解
1.遞歸思想簡介
在c語言中,程序調(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í)行語句返回(這里可以將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ī)??s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題。
由于每個(gè)小問題處理起來都有與大問題類似的行為邏輯,因此我們可以“大事化小”,而遞歸說白了,就是不斷地在套娃。
但是,計(jì)算機(jī)的內(nèi)存是有限的,由于每次調(diào)用函數(shù)都需要在棧區(qū)開辟一個(gè)空間,使得遞歸不能無限制地進(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è)限制條件
遞歸的好處在于:
代碼簡潔在某些特定問題上求解方便
遞歸的缺點(diǎn)在于
消耗大量時(shí)間和空間資源——效率較低可能伴隨許多重復(fù)計(jì)算,工作量大——影響性能
2.漢諾塔問題
以下內(nèi)容來自維基百科
最早發(fā)明這個(gè)問題的人是法國數(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í),僧侶們需要
步才能完成這個(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語言實(shí)現(xiàn)
C語言代碼如下:
/* 漢諾塔問題(遞歸實(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é)果為:
總結(jié)
到此這篇關(guān)于C語言遞歸思想實(shí)現(xiàn)漢諾塔詳解的文章就介紹到這了,更多相關(guān)C語言漢諾塔內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
QT利用QPdfWriter實(shí)現(xiàn)繪制PDF(支持表單輸出)
這篇文章主要為大家詳細(xì)介紹了QT如何利用QPdfWriter實(shí)現(xiàn)繪制PDF,并可以支持表單輸出。文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-01-01探討:將兩個(gè)鏈表非降序合并為一個(gè)鏈表并依然有序的實(shí)現(xiàn)方法
本篇文章是對將兩個(gè)鏈表非降序合并為一個(gè)鏈表并依然有序的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實(shí)例
這篇文章主要介紹了Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實(shí)例,本文代碼中包含注釋來講解CCControlPotentiometer控件類的使用,需要的朋友可以參考下2014-09-09C++11中l(wèi)ambda、std::function和std:bind詳解
大家都知道C++11中增加了許多的新特性,下面在這篇文中我們就來聊一下lambda表達(dá)式,閉包,std::function以及std::bind。文中介紹的很詳細(xì),相信對大家具有一定的參考價(jià)值,有需要的朋友們下面來一起看看吧。2017-01-01C語言數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度及空間復(fù)雜度簡要分析
我們在進(jìn)行編程時(shí),往往會(huì)開發(fā)諸多的算法,那么我們怎么在那么多算法中找到最好的那個(gè)呢?本文主要介紹時(shí)間和空間復(fù)雜度概念及時(shí)間復(fù)雜度的求解,預(yù)祝讀者學(xué)習(xí)愉快2021-10-10