第9章-函數(shù)的高級(jí)應(yīng)用課件

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院蘇小紅

sxh@第9章函數(shù)的高級(jí)應(yīng)用

C語(yǔ)言大學(xué)實(shí)用教程1哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第9章函數(shù)的高級(jí)應(yīng)用C語(yǔ)本章內(nèi)容遞歸與遞歸函數(shù)指向函數(shù)的指針?lè)祷刂羔樦档暮瘮?shù)本章內(nèi)容遞歸與遞歸函數(shù)遞歸問(wèn)題的提出“漢諾塔”（Hanoi）這是一個(gè)必須用遞歸方法才能解決的問(wèn)題n=64時(shí)，18,446,744,073,709,551,615次1844億億次每次1微秒，需要60萬(wàn)年遞歸問(wèn)題的提出“漢諾塔”（Hanoi）遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn=3遞歸問(wèn)題的提出ABCn=3遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問(wèn)題的提出ABC遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問(wèn)題的提出ABC遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問(wèn)題的提出ABC遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn更大些怎么辦？遞歸問(wèn)題的提出ABCn更大些遞歸問(wèn)題的提出第一步：將問(wèn)題簡(jiǎn)化。假設(shè)A桿上只有2個(gè)圓盤(pán)，即漢諾塔有2層，n＝2。ABC遞歸問(wèn)題的提出第一步：將問(wèn)題簡(jiǎn)化。ABC遞歸問(wèn)題的提出對(duì)于一個(gè)有n（n>1）個(gè)圓盤(pán)的漢諾塔，將n個(gè)圓盤(pán)分為兩部分：上面的n-1個(gè)圓盤(pán)和最下面的n號(hào)圓盤(pán)。將“上面的n-1個(gè)圓盤(pán)”看成一個(gè)整體。將n-1個(gè)盤(pán)子從一根木樁移到另一根木樁上將1個(gè)盤(pán)子從一根木樁移到另一根木樁上ACB遞歸問(wèn)題的提出對(duì)于一個(gè)有n（n>1）個(gè)圓盤(pán)的漢諾塔，將n個(gè)遞歸問(wèn)題的提出將n個(gè)盤(pán)子從一根木樁移到另一根木樁上問(wèn)題分解為：將n-1個(gè)盤(pán)子從一根木樁上移到另一根木樁上將1個(gè)盤(pán)子從一根木樁移到另一根木樁上設(shè)計(jì)一個(gè)函數(shù)，入口參數(shù)為n：將n個(gè)盤(pán)子從一根木樁移到另一根木樁上將n-1個(gè)盤(pán)子從一根木樁上移到另一根木樁上也要調(diào)用這個(gè)函數(shù)來(lái)實(shí)現(xiàn)出現(xiàn)了函數(shù)調(diào)用自己的問(wèn)題遞歸調(diào)用（RecursiveCall）遞歸問(wèn)題的提出將n個(gè)盤(pán)子從一根木樁移到另一根木樁上遞歸（Recursion）函數(shù)遞歸函數(shù)函數(shù)直接或間接調(diào)用自己直接調(diào)用方式：

intf(x)

{

inty,z;

….

z=f(x);

……

}遞歸（Recursion）函數(shù)遞歸函數(shù)例9.1求整數(shù)n的階乘n！計(jì)算n！=n*(n-1)*(n-2)*…*1迭代法用遞歸的方法例9.1求整數(shù)n的階乘n！計(jì)算n！=n*(n-1)*(例9.1求整數(shù)n的階乘n！#include<stdio.h>main(){ intn,i; longresult=1; printf("Inputn:"); scanf("%d",&n);

result=1; for(i=1;i<=n;i++) result*=i;

printf("%d!=%ld",n,result);}迭代法例9.1求整數(shù)n的階乘n！#include<stdio.hlongfact(longn)

{ longresult; if(n<0) return–1; elseif(n==0||n==1)/*遞歸終止條件*/

return1; else return(n*fact(n-1));/*遞歸調(diào)用*/}例9.1求整數(shù)n的階乘n！遞歸法longfact(longn) #include<stdio.h>longfact(longn); main(){ int n; longresult; printf("Inputn:"); scanf("%d",&n); result=fact(n); if(result==-1) printf("n<0,dataerror!\n"); else printf("%d!=%ld\n",n,result);}例9.1求整數(shù)n的階乘n！遞歸法#include<stdio.h>例9.1求整數(shù)n的階乘n遞歸調(diào)用過(guò)程執(zhí)行過(guò)程：

fact(5)=5*fact(4)=120 fact(4)=4*fact(3)=24

fact(3)=3*fact(2)=6fact(2)=2*fact(1)=2fact(1)=1

mainfact(5)fact(4)fact(3)fact(2)fact(1)遞歸調(diào)用過(guò)程執(zhí)行過(guò)程：mainfact(5)fact(4)f遞歸函數(shù)遞歸方法的基本原理將復(fù)雜問(wèn)題逐步化簡(jiǎn)，最終轉(zhuǎn)化為一個(gè)最簡(jiǎn)單的問(wèn)題最簡(jiǎn)單問(wèn)題的解決，就意味著整個(gè)問(wèn)題的解決遞歸調(diào)用應(yīng)該能夠在有限次數(shù)內(nèi)終止遞歸遞歸調(diào)用如果不加以限制，將無(wú)數(shù)次的循環(huán)調(diào)用必須在函數(shù)內(nèi)部加控制語(yǔ)句，只有當(dāng)滿(mǎn)足一定條件時(shí)，遞歸終止有時(shí)將其稱(chēng)為條件遞歸遞歸函數(shù)遞歸方法的基本原理遞歸函數(shù)任何一個(gè)遞歸調(diào)用程序必須包括兩部分遞歸循環(huán)繼續(xù)的過(guò)程遞歸調(diào)用結(jié)束的過(guò)程

if(遞歸終止條件成立)

return遞歸公式的初值;elsereturn遞歸函數(shù)調(diào)用返回的結(jié)果值;

遞歸函數(shù)任何一個(gè)遞歸調(diào)用程序必須包括兩部分遞歸函數(shù)思考：下面程序有什么問(wèn)題階乘函數(shù)的遞歸實(shí)現(xiàn)unsigned

long

Fac(unsigned

intn)

{

if(n<0) printf("dataerror!");

elseif(n==0||n==1)

return1;

else

returnn*Fac(n-1);

}編譯這個(gè)程序也會(huì)給出警告，提示“非所有控制分支都有返回值”。同時(shí)，運(yùn)行程序后如果我們輸入了一個(gè)負(fù)數(shù)，那么程序運(yùn)行結(jié)果為：Inputa:-1↙Inputdataerror!a!=11如果某個(gè)函數(shù)需要返回值的話(huà)，那么一定要確保該函數(shù)中的所有控制分支都有返回值。

遞歸函數(shù)思考：下面程序有什么問(wèn)題如果某個(gè)函數(shù)需要返回值的話(huà)，返回指針值的函數(shù)

數(shù)據(jù)類(lèi)型*函數(shù)名(參數(shù)表){……}例9.3:編一個(gè)函數(shù)連接兩個(gè)字符串，然后返回連接后字符串的首地址返回指針值的函數(shù)數(shù)據(jù)類(lèi)型*函數(shù)名(參數(shù)表)返回指針值的函數(shù)char*MyStrcat(char*dstStr,char*srcStr){ char*pStr=dstStr;

while(*dstStr!='\0') { dstStr++; }

for(;*srcStr!='\0';dstStr++,srcStr++) { *dstStr=*srcStr; } *dstStr='\0'; returnpStr;}返回指針值的函數(shù)char*MyStrcat(char*d返回指針值的函數(shù)#include<stdio.h>#defineARR_SIZE80char*MyStrcat(char*dstStr,char*srcStr);main(){ charfirst[ARR_SIZE]="Hello"; charsecond[ARR_SIZE]="world"; char*result=NULL;

result=MyStrcat(first,second); printf("\nTheresultis:%s\n",result);}這個(gè)字符數(shù)組應(yīng)該保證足夠大返回指針值的函數(shù)#include<stdio.h>這個(gè)字符數(shù)函數(shù)指針（FunctionPointers）編譯器將不帶()的函數(shù)名解釋為該程序的入口地址換句話(huà)說(shuō)，函數(shù)名是指向程序入口的指針數(shù)據(jù)類(lèi)型(*指針名)();例如：int(*p)();幾個(gè)容易犯的錯(cuò)誤：忘記了前一個(gè)()，寫(xiě)成int*p();聲明一個(gè)返回值是整型指針的函數(shù)，函數(shù)名為p忘掉了后一個(gè)()，寫(xiě)成int(*p);定義了一個(gè)整型指針定義時(shí)后一個(gè)括號(hào)內(nèi)參數(shù)類(lèi)型與指向的函數(shù)不匹配函數(shù)指針（FunctionPointers）編譯器將不函數(shù)指針求下列函數(shù)的定積分函數(shù)指針求下列函數(shù)的定積分函數(shù)指針不用函數(shù)指針的編程方法floatIntegralFun1(floata,floatb){ floats,h,y; intn,i;

s=((1.0+a*a)+(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;

s+=1.0+y*y;

} returns*h;}函數(shù)指針不用函數(shù)指針的編程方法函數(shù)指針不用函數(shù)指針的編程方法floatIntegralFun2(floata,floatb){ floats,h,y; intn,i;

s=(a/(1.0+a*a)+b/(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;

s+=y/(1.0+y*y);

} returns*h;}函數(shù)指針不用函數(shù)指針的編程方法函數(shù)指針使用函數(shù)指針的編程方法floatIntegral(float(*f)(float),floata,floatb){ floats,h,y; intn,i;

s=((*f)(a)+(*f)(b))/2.0; n=100; h=(b-a)/n; for(i=0;i<n;i++) { y=a+i*h;

s+=(*f)(y); } returns*h;}y1=Integral(Fun2,0.0,3.0);y2=Integral(Fun1,0.0,1.0);

floatFun1(floatx){return1+x*x;}

floatFun2(floatx){returnx/(1+x*x)

;}

函數(shù)指針使用函數(shù)指針的編程方法y1=Integral(F函數(shù)指針應(yīng)用編寫(xiě)通用性更強(qiáng)的函數(shù)典型實(shí)例計(jì)算函數(shù)的定積分另一個(gè)典型實(shí)例既能按照升序排序，又能按降序排序見(jiàn)《C語(yǔ)言大學(xué)實(shí)用教程學(xué)習(xí)指導(dǎo)》P385-395函數(shù)指針應(yīng)用函數(shù)指針voidSort(inta[],intn,int(*compare)(inta,intb)){…… if((*compare)(a[i],max)…….}/*決定數(shù)據(jù)是否按升序排序,a<b為真,則按升序排序*/intAscending(inta,intb){ returna<b;}/*決定數(shù)據(jù)是否按降序排序,a>b為真,則按降序排序*/intDescending(inta,intb){ returna>b;}函數(shù)指針voidSort(inta[],intn,函數(shù)指針其他應(yīng)用函數(shù)指針通常用在菜單驅(qū)動(dòng)的系統(tǒng)中系統(tǒng)提示用戶(hù)從菜單中選擇一種操作（可能是1～6）對(duì)應(yīng)于用戶(hù)選擇的不同操作是由不同的函數(shù)來(lái)完成的先將指向每個(gè)函數(shù)的指針存儲(chǔ)在一個(gè)指針數(shù)組中調(diào)用函數(shù)完成相應(yīng)操作時(shí)將用戶(hù)輸入的選擇，作為該指針數(shù)組的下標(biāo)利用存儲(chǔ)于相應(yīng)數(shù)組元素中的函數(shù)指針，調(diào)用相應(yīng)的函數(shù)見(jiàn)《C語(yǔ)言大學(xué)實(shí)用教程學(xué)習(xí)指導(dǎo)》函數(shù)指針其他應(yīng)用見(jiàn)《C語(yǔ)言大學(xué)實(shí)用教程學(xué)習(xí)指導(dǎo)》作業(yè)P374~3769.1~9.3作業(yè)P374~376哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院蘇小紅

sxh@第9章函數(shù)的高級(jí)應(yīng)用

C語(yǔ)言大學(xué)實(shí)用教程33哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第9章函數(shù)的高級(jí)應(yīng)用C語(yǔ)本章內(nèi)容遞歸與遞歸函數(shù)指向函數(shù)的指針?lè)祷刂羔樦档暮瘮?shù)本章內(nèi)容遞歸與遞歸函數(shù)遞歸問(wèn)題的提出“漢諾塔”（Hanoi）這是一個(gè)必須用遞歸方法才能解決的問(wèn)題n=64時(shí)，18,446,744,073,709,551,615次1844億億次每次1微秒，需要60萬(wàn)年遞歸問(wèn)題的提出“漢諾塔”（Hanoi）遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn=3遞歸問(wèn)題的提出ABCn=3遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問(wèn)題的提出ABC遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問(wèn)題的提出ABC遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問(wèn)題的提出ABC遞歸問(wèn)題的提出

A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn更大些怎么辦？遞歸問(wèn)題的提出ABCn更大些遞歸問(wèn)題的提出第一步：將問(wèn)題簡(jiǎn)化。假設(shè)A桿上只有2個(gè)圓盤(pán)，即漢諾塔有2層，n＝2。ABC遞歸問(wèn)題的提出第一步：將問(wèn)題簡(jiǎn)化。ABC遞歸問(wèn)題的提出對(duì)于一個(gè)有n（n>1）個(gè)圓盤(pán)的漢諾塔，將n個(gè)圓盤(pán)分為兩部分：上面的n-1個(gè)圓盤(pán)和最下面的n號(hào)圓盤(pán)。將“上面的n-1個(gè)圓盤(pán)”看成一個(gè)整體。將n-1個(gè)盤(pán)子從一根木樁移到另一根木樁上將1個(gè)盤(pán)子從一根木樁移到另一根木樁上ACB遞歸問(wèn)題的提出對(duì)于一個(gè)有n（n>1）個(gè)圓盤(pán)的漢諾塔，將n個(gè)遞歸問(wèn)題的提出將n個(gè)盤(pán)子從一根木樁移到另一根木樁上問(wèn)題分解為：將n-1個(gè)盤(pán)子從一根木樁上移到另一根木樁上將1個(gè)盤(pán)子從一根木樁移到另一根木樁上設(shè)計(jì)一個(gè)函數(shù)，入口參數(shù)為n：將n個(gè)盤(pán)子從一根木樁移到另一根木樁上將n-1個(gè)盤(pán)子從一根木樁上移到另一根木樁上也要調(diào)用這個(gè)函數(shù)來(lái)實(shí)現(xiàn)出現(xiàn)了函數(shù)調(diào)用自己的問(wèn)題遞歸調(diào)用（RecursiveCall）遞歸問(wèn)題的提出將n個(gè)盤(pán)子從一根木樁移到另一根木樁上遞歸（Recursion）函數(shù)遞歸函數(shù)函數(shù)直接或間接調(diào)用自己直接調(diào)用方式：

intf(x)

{

inty,z;

….

z=f(x);

……

}遞歸（Recursion）函數(shù)遞歸函數(shù)例9.1求整數(shù)n的階乘n！計(jì)算n！=n*(n-1)*(n-2)*…*1迭代法用遞歸的方法例9.1求整數(shù)n的階乘n！計(jì)算n！=n*(n-1)*(例9.1求整數(shù)n的階乘n！#include<stdio.h>main(){ intn,i; longresult=1; printf("Inputn:"); scanf("%d",&n);

result=1; for(i=1;i<=n;i++) result*=i;

printf("%d!=%ld",n,result);}迭代法例9.1求整數(shù)n的階乘n！#include<stdio.hlongfact(longn)

{ longresult; if(n<0) return–1; elseif(n==0||n==1)/*遞歸終止條件*/

return1; else return(n*fact(n-1));/*遞歸調(diào)用*/}例9.1求整數(shù)n的階乘n！遞歸法longfact(longn) #include<stdio.h>longfact(longn); main(){ int n; longresult; printf("Inputn:"); scanf("%d",&n); result=fact(n); if(result==-1) printf("n<0,dataerror!\n"); else printf("%d!=%ld\n",n,result);}例9.1求整數(shù)n的階乘n！遞歸法#include<stdio.h>例9.1求整數(shù)n的階乘n遞歸調(diào)用過(guò)程執(zhí)行過(guò)程：

fact(5)=5*fact(4)=120 fact(4)=4*fact(3)=24

fact(3)=3*fact(2)=6fact(2)=2*fact(1)=2fact(1)=1

mainfact(5)fact(4)fact(3)fact(2)fact(1)遞歸調(diào)用過(guò)程執(zhí)行過(guò)程：mainfact(5)fact(4)f遞歸函數(shù)遞歸方法的基本原理將復(fù)雜問(wèn)題逐步化簡(jiǎn)，最終轉(zhuǎn)化為一個(gè)最簡(jiǎn)單的問(wèn)題最簡(jiǎn)單問(wèn)題的解決，就意味著整個(gè)問(wèn)題的解決遞歸調(diào)用應(yīng)該能夠在有限次數(shù)內(nèi)終止遞歸遞歸調(diào)用如果不加以限制，將無(wú)數(shù)次的循環(huán)調(diào)用必須在函數(shù)內(nèi)部加控制語(yǔ)句，只有當(dāng)滿(mǎn)足一定條件時(shí)，遞歸終止有時(shí)將其稱(chēng)為條件遞歸遞歸函數(shù)遞歸方法的基本原理遞歸函數(shù)任何一個(gè)遞歸調(diào)用程序必須包括兩部分遞歸循環(huán)繼續(xù)的過(guò)程遞歸調(diào)用結(jié)束的過(guò)程

if(遞歸終止條件成立)

return遞歸公式的初值;elsereturn遞歸函數(shù)調(diào)用返回的結(jié)果值;

遞歸函數(shù)任何一個(gè)遞歸調(diào)用程序必須包括兩部分遞歸函數(shù)思考：下面程序有什么問(wèn)題階乘函數(shù)的遞歸實(shí)現(xiàn)unsigned

long

Fac(unsigned

intn)

{

if(n<0) printf("dataerror!");

elseif(n==0||n==1)

return1;

else

returnn*Fac(n-1);

}編譯這個(gè)程序也會(huì)給出警告，提示“非所有控制分支都有返回值”。同時(shí)，運(yùn)行程序后如果我們輸入了一個(gè)負(fù)數(shù)，那么程序運(yùn)行結(jié)果為：Inputa:-1↙Inputdataerror!a!=11如果某個(gè)函數(shù)需要返回值的話(huà)，那么一定要確保該函數(shù)中的所有控制分支都有返回值。

遞歸函數(shù)思考：下面程序有什么問(wèn)題如果某個(gè)函數(shù)需要返回值的話(huà)，返回指針值的函數(shù)

數(shù)據(jù)類(lèi)型*函數(shù)名(參數(shù)表){……}例9.3:編一個(gè)函數(shù)連接兩個(gè)字符串，然后返回連接后字符串的首地址返回指針值的函數(shù)數(shù)據(jù)類(lèi)型*函數(shù)名(參數(shù)表)返回指針值的函數(shù)char*MyStrcat(char*dstStr,char*srcStr){ char*pStr=dstStr;

while(*dstStr!='\0') { dstStr++; }

for(;*srcStr!='\0';dstStr++,srcStr++) { *dstStr=*srcStr; } *dstStr='\0'; returnpStr;}返回指針值的函數(shù)char*MyStrcat(char*d返回指針值的函數(shù)#include<stdio.h>#defineARR_SIZE80char*MyStrcat(char*dstStr,char*srcStr);main(){ charfirst[ARR_SIZE]="Hello"; charsecond[ARR_SIZE]="world"; char*result=NULL;

result=MyStrcat(first,second); printf("\nTheresultis:%s\n",result);}這個(gè)字符數(shù)組應(yīng)該保證足夠大返回指針值的函數(shù)#include<stdio.h>這個(gè)字符數(shù)函數(shù)指針（FunctionPointers）編譯器將不帶()的函數(shù)名解釋為該程序的入口地址換句話(huà)說(shuō)，函數(shù)名是指向程序入口的指針數(shù)據(jù)類(lèi)型(*指針名)();例如：int(*p)();幾個(gè)容易犯的錯(cuò)誤：忘記了前一個(gè)()，寫(xiě)成int*p();聲明一個(gè)返回值是整型指針的函數(shù)，函數(shù)名為p忘掉了后一個(gè)()，寫(xiě)成int(*p);定義了一個(gè)整型指針定義時(shí)后一個(gè)括號(hào)內(nèi)參數(shù)類(lèi)型與指向的函數(shù)不匹配函數(shù)指針（FunctionPointers）編譯器將不函數(shù)指針求下列函數(shù)的定積分函數(shù)指針求下列函數(shù)的定積分函數(shù)指針不用函數(shù)指針的編程方法floatIntegralFun1(floata,floatb){ floats,h,y; intn,i;

s=((1.0+a*a)+(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;

s+=1.0+y*y;

} returns*h;}函數(shù)指針不用函數(shù)指針的編程方法函數(shù)指針不用函數(shù)指針的編程方法floatIntegralFun2(floata,floatb){ floats,h,y; intn,i;

s=(a/(1.0+a*a)+b/(1.0+b*b))/2.0; n=100; h=(b-a)/n;

for(i=0;i<n;i++) { y=a+i*h;