第五講(3)基本程序設(shè)計(jì)技術(shù)(遞歸程序設(shè)計(jì))

1、第五講 遞歸程序設(shè)計(jì)技術(shù)學(xué)習(xí)程序設(shè)計(jì)需要注意規(guī)律性的東西2本章內(nèi)容n遞歸與循環(huán)n遞歸函數(shù)的執(zhí)行過(guò)程n遞歸函數(shù)效率3回憶函數(shù)定義與函數(shù)調(diào)用函數(shù)頭部函數(shù)體函數(shù)返回值類型 函數(shù)名(參數(shù)表)double DoSomething(double x) int i; double sum; sum = x; return sum; 參數(shù)和函數(shù)體內(nèi)定義的變量都稱為內(nèi)內(nèi)部變量或部變量或局部變量局部變量特殊語(yǔ)句return：計(jì)算表達(dá)式值，結(jié)束函數(shù)的執(zhí)行，返回表達(dá)式結(jié)果。4函數(shù)調(diào)用、執(zhí)行n函數(shù)調(diào)用n函數(shù)名(實(shí)際參數(shù)表)，如func(a,b,c);n多個(gè)參數(shù)之間用逗號(hào)分隔n函數(shù)的執(zhí)行過(guò)程n先計(jì)算各個(gè)參數(shù)(表達(dá)式)的值

2、n進(jìn)入函數(shù)體順序執(zhí)行函數(shù)體語(yǔ)句n直到碰到return語(yǔ)句或執(zhí)行到最后一條語(yǔ)句。5函數(shù)的調(diào)用、執(zhí)行與返回t調(diào)用者程序執(zhí)行函數(shù)調(diào)用點(diǎn)，控制權(quán)轉(zhuǎn)移到被調(diào)用函數(shù)，原程序等待函數(shù)執(zhí)行完畢，控制返回主程序，原程序繼續(xù)被調(diào)用函數(shù)執(zhí)行6循環(huán)與遞歸n循環(huán)程序n用于描述需要重復(fù)進(jìn)行計(jì)算的操作n高級(jí)語(yǔ)言里，也常見(jiàn)用遞歸來(lái)實(shí)現(xiàn)重復(fù)的計(jì)算。n遞歸n函數(shù)調(diào)用自身nC語(yǔ)言允許遞歸，可以在函數(shù)內(nèi)調(diào)用自身，常常使程序更簡(jiǎn)單清晰。71. 階乘和乘冪n例：定義計(jì)算整數(shù)階乘的函數(shù)n12(n - 1)nn本例中，乘的次數(shù)依賴于n，計(jì)算所需的次數(shù)定義時(shí)無(wú)法確定。n這是一種典型循環(huán)情況n計(jì)算“次數(shù)”依賴某些參數(shù)的值。8函數(shù)(for循環(huán)方式

3、實(shí)現(xiàn))long fact1(long n) long fac, i; for (fac = 1, i = 1; i = n; i+) fac *= i; return fac;9階乘函數(shù)的精確數(shù)學(xué)定義n是一種遞歸定義的形式n要解決規(guī)模為n的問(wèn)題，要先解決規(guī)模為n-1的子問(wèn)題，依此類推。n如果高級(jí)語(yǔ)言允許遞歸定義函數(shù)，就可以直接翻譯為程序。nC允許遞歸定義n在函數(shù)定義內(nèi)直接或間接地調(diào)用被定義函數(shù)本身。nnnnn!()!101010寫成遞歸函數(shù)第一種實(shí)現(xiàn)方式：long fact (long n) return n = 0 ? 1 : n * fact(n-1);第二種實(shí)現(xiàn)方式：long fact(

4、long n)if (n = 1) return 1;return n * fact(n - 1);11long fact(1)if (1 = 1) return 1;return 1 * fact(1 - 1);long fact(2)if (2 = 1) return 1;return 2 * fact(2 - 1);long fact(3)if (3 = 1) return 1;return 3 * fact(3 - 1);void main(void) printf(“%d”, fact(3);藍(lán)線：函數(shù)調(diào)用線路黃線：函數(shù)內(nèi)部執(zhí)行路線紅線：函數(shù)執(zhí)行結(jié)束返回主調(diào)函數(shù)的路線long fac

5、t(long n) if (n 1)nF2=F1+F0nF3=F2+F1nnn= 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,nFn=1, 1, 2, 3, 5, 8, 13, 21, 34, 65, 99, 16用遞歸程序?qū)崿F(xiàn)long fib (int n) return n 2 ? 1 : fib(n - 1) + fib(n - 2);問(wèn)題分析：這個(gè)程序好不好？問(wèn)題分析：這個(gè)程序好不好？一方面，很好！程序與數(shù)學(xué)定義的關(guān)系很清晰，一方面，很好！程序與數(shù)學(xué)定義的關(guān)系很清晰，正確性容易確認(rèn)，定義易讀易理解正確性容易確認(rèn)，定義易讀易理解17例fib(5)調(diào)用過(guò)程fib(5)

6、fib(4)fib(3)fib(3)fib(2)fib(2)fib(1)fib(1)fib(0)fib(1)fib(0)fib(2)fib(1)fib(1)fib(0)存在什么問(wèn)題？18問(wèn)題n存在大量重復(fù)計(jì)算，參數(shù)越大重復(fù)計(jì)算越多。n重復(fù)計(jì)算會(huì)造成什么問(wèn)題？n隨著參數(shù)增大，計(jì)算中重復(fù)增長(zhǎng)迅速，最快的微機(jī)上一分鐘大約可以算出fib(45)n參數(shù)加1，fib多用近一倍時(shí)間(指數(shù)增長(zhǎng))。最快的微機(jī)一小時(shí)算不出fib(55)，算fib(100)要數(shù)萬(wàn)年n計(jì)算需要時(shí)間，復(fù)雜計(jì)算需要很長(zhǎng)時(shí)間。這是計(jì)算機(jī)的本質(zhì)特征和弱點(diǎn)。說(shuō)明它不是萬(wàn)能的，有些事情“不能”做。19計(jì)算復(fù)雜度n人們發(fā)現(xiàn)了許多實(shí)際問(wèn)題，理論上說(shuō)

7、可用計(jì)算機(jī)解決(可寫出計(jì)算它的程序)，但對(duì)規(guī)模大的情況(“大的參數(shù) n”)，人類永遠(yuǎn)等不到計(jì)算完成。n這時(shí)能說(shuō)問(wèn)題解決了嗎？n計(jì)算中有一大類問(wèn)題被稱為“難解問(wèn)題”，其中有許多很實(shí)際的問(wèn)題，如規(guī)劃、調(diào)度、優(yōu)化等。n解決這些問(wèn)題或獲得實(shí)用有效的算法，需要理論和實(shí)際技術(shù)的研究。20為計(jì)算過(guò)程計(jì)時(shí)n統(tǒng)計(jì)程序或程序片段的計(jì)算時(shí)間有助于理解程序性質(zhì)。許多語(yǔ)言或系統(tǒng)都提供了內(nèi)部計(jì)時(shí)功能。nC語(yǔ)言的有關(guān)函數(shù)在time.h，統(tǒng)計(jì)程序時(shí)間時(shí)程序頭部應(yīng)寫n#include n在程序里計(jì)時(shí)，通常寫表達(dá)式nclock() / CLOCKS_PER_SECn得到從程序開(kāi)始到表達(dá)式求值時(shí)所經(jīng)歷的秒數(shù)。21確定計(jì)算確定計(jì)算f

8、ib(45)fib(45)所需要的時(shí)間的程序所需要的時(shí)間的程序#include #include long fib (int n) return n=1 ? 1 : fib(n-1)+fib(n-2);int main () double x; x = clock() / CLOCKS_PER_SEC; fib(45); x = clock() / CLOCKS_PER_SEC - x; printf(Timing fib(45): %f.n, x); return 0;我的筆記本計(jì)算結(jié)果：Timing fib(45): 76.000000.22Fibonacci數(shù)的迭代計(jì)算 nFibonac

9、ci數(shù)的遞推計(jì)算，易見(jiàn) n1)f1和f2是1n2)知道fn-2和fn-1連續(xù)兩個(gè)Fibonacci數(shù)，就可算出下一個(gè)fnn遞推計(jì)算方式n逐個(gè)往后推，可用循環(huán)實(shí)現(xiàn)遞推方案long fib1 (int n) long f1 = 1, f2 = 1, f3, i; if (n = 1) return 1; for (f3 = f2 + f1, i = 2; i n; +i) f1 = f2; f2 = f3; f3 = f1 + f2; return f3;做一次遞推fnfn-1fn-224程序分析for (f3 = f2 + f1, i = 2; i n; +i) f1 = f2; f2 = f3

10、; f3 = f1 + f2; n循環(huán)結(jié)束時(shí)i等于n，這時(shí)f3的值是fn。n要得到此結(jié)論，可設(shè)法證明：每次判斷 i 的值時(shí)f3正是 Fi。25歸納證明n第一次判斷時(shí) i的值是2，f3 的值2，正是 F2(且 f1 的值是Fi-2 (F0) ，f2 的值是Fi-1(F1)。n若某次判斷時(shí) i 值是 k (小于n)，循環(huán)體中的語(yǔ)句使f1變成Fk-1 ，f2變成Fk ，f3變成Fk+1 。ni 值增 1 使我們又有f1為Fi-2 ，f2變成Fi-1 ，f3變成Fi 。n根據(jù)歸納法，每次判斷 i 的值時(shí)f3正是 Fi。26如何保證循環(huán)的正確執(zhí)行n循環(huán)實(shí)現(xiàn)重復(fù)性計(jì)算，循環(huán)體可能執(zhí)行多次。如何保證對(duì)各種數(shù)

11、據(jù)都能正確完成計(jì)算？n循環(huán)中變量不斷變化。寫循環(huán)要考慮變量間的關(guān)系，保證某些關(guān)系在循環(huán)中不變：循環(huán)的不變關(guān)系。n寫循環(huán)時(shí)最重要的就是想清循環(huán)中應(yīng)維持變量間的什么關(guān)系才能保證循環(huán)結(jié)束時(shí)變量能處在所需狀態(tài)。寫完循環(huán)后應(yīng)仔細(xì)檢查是否滿足要求。n循環(huán)不變關(guān)系(循環(huán)不變量)是理解循環(huán)、寫好循環(huán)的關(guān)鍵。27問(wèn)題 n本例中用循環(huán)的函數(shù)比用遞歸定義的好嗎？n新函數(shù)在計(jì)算時(shí)間上有極大優(yōu)越性。計(jì)算時(shí)間由循環(huán)次數(shù)確定。循環(huán)體執(zhí)行次數(shù)大致為n。fib(100)只需約100次循環(huán)，幾乎察覺(jué)不到所花費(fèi)時(shí)間。n新函數(shù)定義較復(fù)雜，有復(fù)雜的循環(huán)。要理解程序意義，確認(rèn)函數(shù)對(duì)任何參數(shù)都算出Fibonacci值，需要借助“循環(huán)不變關(guān)

12、系”的概念和細(xì)致分析。注意：這個(gè)例子并不是說(shuō)明遞歸比循環(huán)的效率低。完全可以寫出計(jì)算fib的同樣高效的遞歸定義的函數(shù)。28最大公約數(shù)n求兩個(gè)整數(shù)的最大公約數(shù)(greatest common divisor，GCD)，寫函數(shù) long gcd(long, long)n解法1n從某個(gè)數(shù)開(kāi)始，逐個(gè)判斷當(dāng)前數(shù)是否能同時(shí)整除m和n，在這個(gè)過(guò)程中記錄下能同時(shí)整除m和n的最大整數(shù)。n需要用一個(gè)輔助變量k記錄當(dāng)前需要判斷的數(shù)。n用一個(gè)循環(huán)實(shí)現(xiàn)k順序取值n初值設(shè)為1n每次判斷完后增1n直到k大于m和n中其中的一個(gè)為止n記下循環(huán)過(guò)程中出現(xiàn)的新的m和n的公約數(shù)，作為新的最大公約數(shù)n用變量d表示當(dāng)前的最大公約數(shù)n初值1

13、(是公約數(shù))，遇到新的公約數(shù)(一定更大)時(shí)記入d29程序有了d及其初值，k可以從2開(kāi)始循環(huán)。函數(shù)定義long gcd (long m, long n) long d = 1, k = 2; for ( ; k = m & k = n; k+) if (m % k = 0 & n % k = 0) d = k; return d;參數(shù)互素時(shí)初值1會(huì)留下來(lái)，能保證正確30計(jì)算過(guò)程示例mnkk = m & k = nm % k = 0 & n % k = 0d208212是是是是23是是否否24是是是是45是是否否46是是否否47是是否否48是是否否49否否431特殊

14、情況處理n一些特殊情況需要處理1）m和n都為0需特殊處理。令函數(shù)返回值0；2）若m和n中一個(gè)為0，gcd是另一個(gè)數(shù)。函數(shù)的返回值正確。也可直接判斷處理；3）m、n為負(fù)時(shí)函數(shù)返回1，可能不對(duì)。n應(yīng)在循環(huán)前加語(yǔ)句if (m = 0 & n = 0) return 0;if (m = 0) return n;if (n = 0) return m;if (m 0) m = -m;if (n n ? n : m); /把k設(shè)為n的較小者 m % k != 0 | n % k != 0; k-) ; /* 空循環(huán)體 */return k; /*循環(huán)結(jié)束時(shí)k是最大公約數(shù) */ 33過(guò)程示例mnkm

15、 % k != 0 | n % k != 0d2088是是？7是是？6是是？5是是？4否否434兩種方式比較n本方法比前一方法簡(jiǎn)單一些。n兩種方法的共同點(diǎn)是重復(fù)測(cè)試。n這類方法的缺點(diǎn)是效率較低，參數(shù)大時(shí)循環(huán)次數(shù)很多。35解法2 輾轉(zhuǎn)相除法n求GCD有著名的歐幾里德算法(歐氏算法，輾轉(zhuǎn)相除法)。最大公約數(shù)的遞歸定義：gcd( , )modgcd( ,mod )modm nnmnn mnmn0036例n例1ngcd1(70, 30) m = 70, n = 30 m % n 10ngcd(30, 10) m = 30, n = 10 m % n 0n例2ngcd1(65, 15) m = 65,

16、n = 15 m % n 5ngcd1(15, 5) m = 15, n = 5 m % n 037遞歸程序解決n函數(shù)定義與數(shù)學(xué)定義直接對(duì)應(yīng)long gcd1 (long m, long n) return m % n = 0 ? n : gcd1(n, m % n); 假設(shè)第二個(gè)參數(shù)非0，且參數(shù)都不小于0。n對(duì)歐氏算法的研究保證了本函數(shù)能結(jié)束，對(duì)較大的數(shù)計(jì)算速度也很快，遠(yuǎn)遠(yuǎn)優(yōu)于順序檢查。38加入特殊情況處理long gcd(long m, long n) if (m 0) m = -m; if (n %cn, from, to); void henoi(int n,char from,cha

17、r to,char by) if (n = 1) moveone(from, to); else henoi(n-1, from, by, to); moveone(from, to); henoi(n-1, by, to, from); moveonemoveone定義為函數(shù)是為了方便。函數(shù)調(diào)用：定義為函數(shù)是為了方便。函數(shù)調(diào)用：henoi(6, a, b, c);henoi(6, a, b, c);48hanio(3, a, b, c); hanio(2, a, c, b); moveone(a, b); hanio(2, c, b, a);hanio(2, a, c, b) hanio(1, a, b, c); moveone(a, c); hanio(1, b, c, a);hanio(