遞歸法與問題解決算法與問題解決

也許有人要問，計(jì)算機(jī)運(yùn)行速度發(fā)展那么快，為什么還需要刻意設(shè)計(jì)高效率的程序？原因很簡單，人類的雄心與能力是一起增長的，技術(shù)進(jìn)步再快也快不過人們對需求的增長。計(jì)算速度和存儲容量上的革新僅僅提供了處理更復(fù)雜問題的有效工具，所以高效率的程序永遠(yuǎn)不會過時。或許，我們開發(fā)的軟件會表現(xiàn)出很多不良現(xiàn)象，不要過多埋怨計(jì)算機(jī)或系統(tǒng)環(huán)境差，應(yīng)考慮設(shè)計(jì)一種更快、更好的算法，這才是解決問題的實(shí)質(zhì)?！按笫禄?、小事化了”。生活中的平安哲理，在程序設(shè)計(jì)中也在使用，遞歸算法就是按照這種思路來處理的，找到一個遞歸關(guān)系式將大問題轉(zhuǎn)化為小問題，將小問題的解決方案作為問題解決的出口，大問題也就“迎刃而解”了。本節(jié)通過階乘的遞歸調(diào)用和梵塔問題的求解，學(xué)習(xí)使用遞歸法解決問題的基本方法。

1.問題分析階乘的計(jì)算就是一種典型的遞歸問題。階乘通常定義為：一、計(jì)算階乘

2.算法設(shè)計(jì)為了計(jì)算f(5)的值，應(yīng)計(jì)算5×f(4)，所以應(yīng)先計(jì)算f(4)的值；而要求f(4)，又得先求f(3)；欲求(3)，又得先求f(2)；求f(2)，又得先求(1)；求f(1)，又得先求f(0)。而f(0)的值為遞歸邊界值，它是f(O)=0!=1。3.編程實(shí)現(xiàn)一、計(jì)算階乘1.問題提出梵塔(Hanoi)問題是一個著名的數(shù)學(xué)問題。相傳在古印度北部一個佛教圣地的貝拿勒斯圣廟，安放著一個黃銅板，板上插著三根寶石針。每根針高約一腕尺(約合0.5米)，像韭菜葉那樣粗細(xì)。梵天(印度教的主神)在創(chuàng)造世界的時候，在其中的一根針上，從下到上放了由大到小的六十四片金片。這就是所謂的梵塔。二、梵塔問題

不論白天黑夜，都有一個值班的僧侶按照梵天不渝的法則，把這些金片在三根針上移來移去：一次只能移一片，并且要求不管在哪一根針上，小片永遠(yuǎn)在大片的上面。當(dāng)所有六十四片都從梵天創(chuàng)造世界時所放的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅。這個可怕而神奇的傳說真的會降臨嗎？讓我們開動腦筋、仔細(xì)分析，算一算移完梵塔的示意圖全部的六十四片金片究竟需要多少時間。二.梵塔問題2.問題分析盤片在移動過程中有兩個要求：◆每次只能移動一個金盤?！粼谝粋€柱子上任何時候都不能把大盤放在小盤上面。3.算法描述4.編程實(shí)現(xiàn)二.梵塔問題獲得圖靈獎的第一位華裔科學(xué)家獲得200年圖靈獎的美國科學(xué)院院士、計(jì)算機(jī)科學(xué)理論學(xué)家姚期智博士，是迄今為止獲得圖靈獎的惟一一位華裔科學(xué)家。姚期智博士因在計(jì)算理論方面的基礎(chǔ)性貢獻(xiàn)獲得此獎。姚期智祖籍湖北，1946年圣誕節(jié)前夜出生于上海，1967年，姚期智以優(yōu)異的成績畢業(yè)于臺灣大學(xué)，之后赴美深造。在1972年取得哈佛大學(xué)物理學(xué)博士學(xué)位以后，姚期智來到伊利諾斯大學(xué)研究生院繼續(xù)學(xué)習(xí)，而伊利諾斯大學(xué)一向以計(jì)算機(jī)科學(xué)研究領(lǐng)域的深厚積淀而聞名全美。1975年，姚期智在伊利諾斯大學(xué)拿到了他的第二個博士學(xué)位——計(jì)算機(jī)科學(xué)博士學(xué)位。小資料

之后，他曾先后在省理工學(xué)院、斯坦福大學(xué)、加州大學(xué)伯克利分校等美國一流高等學(xué)府從事教學(xué)和研究，1986年至今則一直任普林斯頓大學(xué)計(jì)算機(jī)科學(xué)系教授。姚期智博士在數(shù)據(jù)組織、基于復(fù)雜性的偽隨機(jī)數(shù)生成理論、密碼學(xué)、通信復(fù)雜性乃至量子通信和計(jì)算等多個尖端科研領(lǐng)域，都做出了巨大的、獨(dú)到的貢獻(xiàn)。小資料

求兩個自然數(shù)m、n的最大公約數(shù)的算法最早來自算術(shù)中的輾轉(zhuǎn)相除法，人們稱之為歐幾里得算法。方法如下：用m除以n，若余數(shù)r為0，則此時n就是m、n的最大公約數(shù)；若余數(shù)r不為0，則將上次的除數(shù)n作為被除數(shù)、上次的余數(shù)r作為除數(shù)，再次相除后求余數(shù)。如