第9章函數(shù)的高級應用.ppt

1、第9章 函數(shù)的高級應用,C語言大學實用教程,本章內(nèi)容,遞歸與遞歸函數(shù) 返回指針值的函數(shù) 指向函數(shù)的指針,遞歸問題的提出,“漢諾塔”（Hanoi） 這是一個必須用遞歸方法才能解決的問題 n=64時， 18,446,744,073,709,551,615次 1844億億次 每次1微秒，需要60萬年,遞歸問題的提出,AC，AB，CB， AC，BA，BC，AC,A,B,C,n=3,遞歸問題的提出,AC，AB，CB， AC，BA，BC，AC,A,B,C,遞歸問題的提出,AC，AB，CB， AC，BA，BC，AC,A,B,C,遞歸問題的提出,AC，AB，CB， AC，BA，BC，AC,A,B,C,遞歸問題

2、的提出,AC，AB，CB， AC，BA，BC，AC,A,B,C,n更大些 怎么辦？,遞歸問題的提出,先考慮簡單情形 假設A桿上只有2個圓盤，即漢諾塔有2層，n2。,A,B,C,步驟：1.AB 2. AC 3. BC,遞歸問題的提出,一般情形：有 n（n1）個圓盤的漢諾塔 思路：將n個圓盤分為兩部分，上面的 n-1 個圓盤和最下面的n號圓盤。將“上面的n-1個圓盤”看成一個整體。,A,C,B,遞歸問題的提出,問題：將 n個盤子從A木樁借助B木樁移到C木樁 問題分解為： 將 n-1個盤子從A木樁借助C木樁移到B木樁上 將1個盤子從A木樁移到C木樁上 將n-1個盤子從B木樁借助A木樁移到C木樁上 設

3、計一個函數(shù)，入口參數(shù)為n ： 將 n個盤子從一根木樁移到另一根木樁上 將 n-1個盤子從一根木樁上移到另一根木樁上 也要調(diào)用這個函數(shù)來實現(xiàn) 出現(xiàn)了函數(shù)調(diào)用自己的問題 遞歸調(diào)用（Recursive Call）,遞歸（Recursion）函數(shù),遞歸函數(shù) 函數(shù)直接或間接調(diào)用自己 直接調(diào)用方式： int f(x) int y,z; . z=f(x); ,例9.1求整數(shù)n的階乘n！,計算n！= n *(n-1)*(n-2)*1 迭代法 用遞歸的方法,例9.1求整數(shù)n的階乘n！,#include main() int n, i; long result=1; printf(Input n:); scanf

4、(%d, ,迭代法,#include long fact(int n); main() int n; long result; printf(Input n: ); scanf(%d, ,例9.1求整數(shù)n的階乘n！,遞歸法,long fact(int n) long result; if (n=0 | n=1) /*遞歸終止條件*/ return 1; else return (n * fact(n-1);/*遞歸調(diào)用*/ ,例9.1求整數(shù)n的階乘n！,遞歸法,fact(5)=5*fact(4) fact(4)=4*fact(3) fact(3)=3*fact(2) fact(2)=2*fac

5、t(1) fact(1)=1,遞歸調(diào)用過程,執(zhí)行過程：,main,fact(5),fact(4),fact(3),fact(2),fact(1),=120,=24,=6,=2,#include long fact(int n); main() int n; long result; printf(Input n: ); scanf(%d, ,long fact(int n) /n=5 long result; if (n=0 | n=1) return 1; else return (n * fact(n-1); ,long fact(int n) /n=4 long result; if (

6、n=0 | n=1) return 1; else return (n * fact(n-1); ,long fact(int n) /n=3 long result; if (n=0 | n=1) return 1; else return (n * fact(n-1); ,long fact(int n) /n=2 long result; if (n=0 | n=1) return 1; else return (n * fact(n-1); ,long fact(int n) /n=1 long result; if (n=0 | n=1) return 1; else return

7、(n * fact(n-1); ,#include long fact(int n); main() int n; long result; printf(Input n: ); scanf(%d, ,例9.1求整數(shù)n的階乘n！,遞歸法,long fact(int n) long result; if (n 0) return 1; else if (n=0 | n=1) /*遞歸終止條件*/ return 1; else return (n * fact(n-1);/*遞歸調(diào)用*/ ,例9.1求整數(shù)n的階乘n！,遞歸法,遞歸函數(shù),遞歸方法的基本原理 將復雜問題逐步化簡，最終轉化為一個最簡單的

8、問題 最簡單問題的解決，就意味著整個問題的解決 遞歸調(diào)用應該能夠在有限次數(shù)內(nèi)終止遞歸 遞歸調(diào)用如果不加以限制，將無數(shù)次的循環(huán)調(diào)用 必須在函數(shù)內(nèi)部加控制語句，只有當滿足一定條件時，遞歸終止 有時將其稱為條件遞歸,遞歸函數(shù),任何一個遞歸調(diào)用程序必須包括兩部分 遞歸循環(huán)繼續(xù)的過程 遞歸調(diào)用結束的過程 if (遞歸終止條件成立) return 遞歸公式的初值; else return 遞歸函數(shù)調(diào)用返回的結果值;,遞歸函數(shù),思考：下面程序有什么問題 階乘函數(shù)的遞歸實現(xiàn) unsigned long Fac(unsigned int n) if (n 0) printf(data error!); else

9、 if (n=0 | n=1) return 1;else return n * Fac(n-1); 編譯這個程序也會給出警告，提示“非所有控制分支都有返回值”。 同時，運行程序后如果我們輸入了一個負數(shù)，那么程序運行結果為： Input a:-1 Input data error! a! = 11,如果某個函數(shù)需要返回值的話，那么一定要確保該函數(shù)中的所有控制分支都有返回值。,例9.2編程解Hanoi問題,問題：將 n個盤子從A木樁借助B木樁移到C木樁 問題分解為： 將 n-1個盤子從A木樁借助C木樁移到B木樁上 將1個盤子從A木樁移到C木樁上 將n-1個盤子從B木樁借助A木樁移到C木樁上 設計

10、一個函數(shù)，入口參數(shù)為： 盤子數(shù)int n; 源char a; 借助char b; 目標char c; 函數(shù)原型：void Hanoi(int n, char a, char b, char c);,例9.2編程解Hanoi問題,#include void Hanoi(int n,char a,char b,char c); main( ) int n; printf(Input the number of disk : ); scanf(%d, ,void Hanoi(int n,char a,char b,char c) if(n=1) printf(From %c to %cn, a, c

11、); else Hanoi(n-1,a,c,b); printf(From %c to %cn, a, c); Hanoi(n-1,b,a,c); ,問題：將 n個盤子從A木樁借助B木樁移到C木樁 問題分解為： 將 n-1個盤子從A木樁借助C木樁移到B木樁上 將1個盤子從A木樁移到C木樁上 將n-1個盤子從B木樁借助A木樁移到C木樁上,練習,問題1：用遞歸方法求135n(n為奇數(shù))的乘積。 問題2：用遞歸方法求兩正整數(shù)a, b的最大公約數(shù)。 問題3：編程打印出任意自然數(shù)的質因子分解式。如72的質因子分解式為2*2*2*3*3 問題4：用遞歸法將任意一個自然數(shù)n轉換成字符串輸出。例如，輸入483

12、，應輸出字符串“483”。n的位數(shù)不確定。,返回指針值的函數(shù),數(shù)據(jù)類型 * 函數(shù)名(參數(shù)表) 例9.3: 編一個函數(shù)連接兩個字符串，然后返回連接后字符串的首地址,返回指針值的函數(shù),char *MyStrcat(char *dstStr, char *srcStr) char *pStr = dstStr; while (*dstStr != 0) dstStr+; for(; *srcStr!=0; dstStr+, srcStr+) *dstStr = *srcStr; *dstStr = 0; return pStr; ,返回指針值的函數(shù),#include #define ARR_SIZE

13、 80 char *MyStrcat(char *dstStr, char *srcStr); main() char firstARR_SIZE = Hello ; char secondARR_SIZE = world; char *result = NULL; result = MyStrcat(first, second); printf(nThe result is : %sn, result); ,這個字符數(shù)組應該保證足夠大,函數(shù)指針 （Function Pointers）,編譯器將不帶()的函數(shù)名解釋為該程序的入口地址 換句話說，函數(shù)名是指向程序入口的指針 數(shù)據(jù)類型 (* 指針名

14、)(); 例如：int (*p)(); 幾個容易犯的錯誤： 忘記了前一個()，寫成 int *p(); 聲明一個返回值是整型指針的函數(shù)，函數(shù)名為p 忘掉了后一個()，寫成 int (*p); 定義了一個整型指針 定義時后一個括號內(nèi)參數(shù)類型與指向的函數(shù)不匹配,函數(shù)指針,求下列函數(shù)的定積分,函數(shù)指針,不用函數(shù)指針的編程方法 float IntegralFun1(float a, float b) float s,h,y; int n,i; s = (1.0+a*a) + (1.0+b*b) / 2.0; n = 100; h = (b - a) / n; for (i=0; in; i+) y =

15、 a + i * h; s += 1.0 + y * y; return s * h; ,函數(shù)指針,不用函數(shù)指針的編程方法 float IntegralFun2(float a, float b) float s,h,y; int n,i; s = (a/(1.0+a*a) + b/(1.0+b*b) / 2.0; n = 100; h = (b - a) / n; for (i=0; in; i+) y = a + i * h; s += y / (1.0 + y * y); return s * h; ,函數(shù)指針,使用函數(shù)指針的編程方法 float Integral(float (*f)(

16、float), float a, float b) float s, h, y; int n, i; s = (*f)(a) + (*f)(b) / 2.0; n = 100; h = (b - a) / n; for (i=0; in; i+) y = a + i * h; s += (*f)(y); return s * h; ,y1 = Integral(Fun2, 0.0, 3.0); y2 = Integral(Fun1, 0.0, 1.0);,float Fun1(float x) return 1+x*x; ,float Fun2(float x) return x/(1+x*x) ; ,函數(shù)指針,應用 編寫通用性更強的函數(shù) 典型實例 計算函數(shù)的定積分 另一個典型實例 既能按照升序排序，又能按降序排序 見C語言大學實用教程學習指導P385-395,函數(shù)指針,void Sort(int a, int n, int (*compare)(int a, int b) if (*compare)(ai,max)