C語言遞歸思想實現(xiàn)漢諾塔詳解
1.遞歸思想簡介
在c語言中,程序調(diào)用自身的編程技巧稱為遞歸( recursion)。
遞歸的定義看上去似乎很抽象,使用代碼描述能夠讓人容易理解,下面是一個函數(shù)遞歸的例子。
/* 遞歸求n的階乘 */ int factorial(int n) //定義一個求階乘的函數(shù)叫做factorial(),需要一個整形參數(shù),返回一個整形值 { if (n <= 1) //遞歸結(jié)束的條件 { return 1; } else { return n * factorial(n - 1);//在factorial()中再次調(diào)用自身,只不過參數(shù)由n變成n-1 } }
在這個例子中,函數(shù) factorial()接收到一個整形數(shù)n,如n=5,暫時稱作F(5),這時n!=F(5),而函數(shù)的功能如下:
判斷5是否小于或等于1,如果是,將1返回;不是,進(jìn)到else執(zhí)行語句返回(這里可以將return看作等于)5× factorial(n - 1),等價于 F(5)=5×F(4)用上面的方法計算F(4)=4×F(3)....以此類推直到達(dá)到限制條件n=1時有,F(xiàn)(1)=1
遞歸算法的實質(zhì):是把問題轉(zhuǎn)化為規(guī)??s小了的同類問題的子問題。然后遞歸調(diào)用函數(shù)(或過程)來表示問題。
由于每個小問題處理起來都有與大問題類似的行為邏輯,因此我們可以“大事化小”,而遞歸說白了,就是不斷地在套娃。
但是,計算機(jī)的內(nèi)存是有限的,由于每次調(diào)用函數(shù)都需要在棧區(qū)開辟一個空間,使得遞歸不能無限制地進(jìn)行下去,沒有遞歸結(jié)束的條件,當(dāng)操作系統(tǒng)為進(jìn)程分配的虛擬地址空間當(dāng)中的??臻g被耗盡時,會發(fā)生堆棧溢出,產(chǎn)生段錯誤(segmentation fault)。
因此,使用遞歸時應(yīng)注意:
必須存在限制條件,當(dāng)滿足這個限制條件的時候,遞歸便不再繼續(xù)每次遞歸調(diào)用之后越來越接近這個限制條件
遞歸的好處在于:
代碼簡潔在某些特定問題上求解方便
遞歸的缺點在于
消耗大量時間和空間資源——效率較低可能伴隨許多重復(fù)計算,工作量大——影響性能
2.漢諾塔問題
以下內(nèi)容來自維基百科
最早發(fā)明這個問題的人是法國數(shù)學(xué)家愛德華·盧卡斯。
傳說越南河內(nèi)某間寺院有三根銀棒,上串 64 個金盤。寺院里的僧侶依照一個古老的預(yù)言,以上述規(guī)則移動這些盤子;預(yù)言說當(dāng)這些盤子移動完畢,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創(chuàng)的這個傳說,還是他受他人啟發(fā)。
若傳說屬實,僧侶們需要
步才能完成這個任務(wù);若他們每秒可完成一個盤子的移動,就需要 5849 億年才能完成。整個宇宙現(xiàn)在也不過 137 億年。
這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位于越南的河內(nèi),所以被命名為“河內(nèi)塔”。另外亦有“金盤是創(chuàng)世時所造”、“僧侶們每天移動一盤”之類的背景設(shè)定
漢諾塔基本的玩法如圖,其規(guī)則是:將圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。
當(dāng)圓盤數(shù)量只有3個的時候,求解的方法顯而易見,但當(dāng)數(shù)量增多時,問題變得有些棘手起來。但不管怎么移動,核心思想都是遞歸:
先從n塊圓盤中將最大的一塊移動到最后的柱子上接著從剩下n-1找到最大的一塊移到柱子上......
3.漢諾塔遞歸的c語言實現(xiàn)
C語言代碼如下:
/* 漢諾塔問題(遞歸實現(xiàn)) */ #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> void move(char, char); // 聲明一個函數(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移動到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柱子上圓盤的數(shù)量,A,B,C代表三根柱子 return 0; }
程序運行結(jié)果為:
總結(jié)
到此這篇關(guān)于C語言遞歸思想實現(xiàn)漢諾塔詳解的文章就介紹到這了,更多相關(guān)C語言漢諾塔內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
QT利用QPdfWriter實現(xiàn)繪制PDF(支持表單輸出)
這篇文章主要為大家詳細(xì)介紹了QT如何利用QPdfWriter實現(xiàn)繪制PDF,并可以支持表單輸出。文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-01-01探討:將兩個鏈表非降序合并為一個鏈表并依然有序的實現(xiàn)方法
本篇文章是對將兩個鏈表非降序合并為一個鏈表并依然有序的實現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實例
這篇文章主要介紹了Cocos2d-x UI開發(fā)之CCControlPotentiometer控件類使用實例,本文代碼中包含注釋來講解CCControlPotentiometer控件類的使用,需要的朋友可以參考下2014-09-09C++11中l(wèi)ambda、std::function和std:bind詳解
大家都知道C++11中增加了許多的新特性,下面在這篇文中我們就來聊一下lambda表達(dá)式,閉包,std::function以及std::bind。文中介紹的很詳細(xì),相信對大家具有一定的參考價值,有需要的朋友們下面來一起看看吧。2017-01-01C語言數(shù)據(jù)結(jié)構(gòu)時間復(fù)雜度及空間復(fù)雜度簡要分析
我們在進(jìn)行編程時,往往會開發(fā)諸多的算法,那么我們怎么在那么多算法中找到最好的那個呢?本文主要介紹時間和空間復(fù)雜度概念及時間復(fù)雜度的求解,預(yù)祝讀者學(xué)習(xí)愉快2021-10-10