第六章函數(shù)、遞推與遞歸清華大學(xué)清華大學(xué)C9函數(shù)的概念、定義、調(diào)用和返回帶自定義函數(shù)的程序設(shè)計遞推算法遞歸思想及算法實現(xiàn)內(nèi)容要點

清華大學(xué)C9為什么需要函數(shù)？——滿足實際應(yīng)用需求6.1函數(shù)

函數(shù)是組成C/C++程序的基礎(chǔ)

C/C++庫中已經(jīng)為用戶提供了許多標準庫函數(shù)用戶可以根據(jù)自己的需要選用合適的庫函數(shù)如果沒有所需函數(shù)，用戶可自己定義和編寫一些函數(shù)清華大學(xué)C9函數(shù)概述函數(shù)是模塊化的基本單位主調(diào)函數(shù)與被調(diào)函數(shù)程序、源文件與函數(shù)關(guān)系程序中各模塊關(guān)系main(){}fun1(){}fun2(){}fun3(){}fun4(){}fun5(){}program清華大學(xué)C9……intmain(){inta,b,sum;

……

sum=Add(a,b);//函數(shù)調(diào)用

……}intAdd(intx,inty);

//函數(shù)聲明intAdd(intx,inty)//函數(shù)定義{…………}

//函數(shù)體取代函數(shù)聲明尾部的分號

要使用C++函數(shù)，必須完成如下工作：

提供函數(shù)定義

提供函數(shù)聲明（原型）

調(diào)用函數(shù)清華大學(xué)C9函數(shù)定義：有返回值的函數(shù)沒有返回值的函數(shù)（void函數(shù)）voidfunctionName(parameterList)//沒有返回值{……

return;//可選}typeNamefunctionName(parameterList)//有返回值{……

returnvalue;}清華大學(xué)C9【任務(wù)6.1】素數(shù)判定思路：設(shè)計一個函數(shù)

intcheckprime(inta)，負責(zé)檢查a是否為素數(shù)：如果是素數(shù)，該函數(shù)返回1；否則，該函數(shù)返回0。清華大學(xué)C9#include<iostream>

#include<cmath>usingnamespacestd;intmain()

{inta=0;cout<<"請輸入一個整數(shù)：a=";cin>>a;

if(

checkprime(a)

)//函數(shù)調(diào)用 cout<<a<<"是素數(shù)"<<endl;else cout<<a<<"不是素數(shù)"<<endl;return0;}int

checkprime(

intn);

//函數(shù)聲明intcheckprime(intn)

//函數(shù)定義，n為形式參數(shù){intk=0;

for(k=2;k<=sqrt(n);k=k+1) {if(n%k==0)//如果

n能被k整除則返回0 return0; }return1; //n

不能被k整除則返回1}有何問題？清華大學(xué)C9函數(shù)原型

intcheckprime(intn);提高算法效率只要在1和n

之間存在一個因子就可終止，并返回n不是素數(shù)若n可被2整除，不需檢驗其它數(shù)，程序終止并返回n不是素數(shù)；若否，則所有偶數(shù)都不是因子，程序只需檢驗奇數(shù)程序不必檢驗因子一直到n，只需到sqrt(n)即可清華大學(xué)C9intcheckprime(intn){inti;if(n%2

==0)return0;for(i=3;i<=sqrt(n);

i+=2){if(n%i==0)return0;}return1;}問題1：本算法效率？每次迭代都需要計算平方根，很費時問題2：本算法正確性？n=1n=2時結(jié)果錯誤清華大學(xué)C9intcheckprime(intn){intlimit,i;

limit=sqrt(n);if(n%2

==0)return0;for(i=3;i<=limit;i+=2){if(n%i==0)return0;}return1;}問題：本算法正確性？浮點數(shù)的存儲有誤差，程序的正確性依賴于機器的表示精度清華大學(xué)C9intcheckprime(intn){intlimit,i;

limit=sqrt(n)+1;if(n%2

==0)return0;for(i=3;i<=limit;i+=2){if(n%i==0)return0;}return1;}if(n<=1)return0;if(n==2)return1;改進后的正確函數(shù)：清華大學(xué)C9函數(shù)定義:intcheckprime(intn) checkprime為函數(shù)名

int是函數(shù)返回值的數(shù)據(jù)類型

n

為函數(shù)的形式參數(shù)，形式參數(shù)也要定義其數(shù)據(jù)類型形式參數(shù)的特點：定義函數(shù)時放在函數(shù)名后的括號中函數(shù)未被調(diào)用時不占內(nèi)存空間函數(shù)被調(diào)用時系統(tǒng)為其分配內(nèi)存空間函數(shù)調(diào)用結(jié)束后釋放內(nèi)存空間作用域限定在函數(shù)內(nèi)，屬于局部變量清華大學(xué)C9函數(shù)聲明（原型）：例：intcheckprime(intn);

要放在主函數(shù)之前，告訴系統(tǒng)有自定義的函數(shù)可以被調(diào)用。函數(shù)原型確保：編譯器正確處理函數(shù)返回值編譯器檢查使用的參數(shù)數(shù)目是否正確編譯器檢查使用的參數(shù)類型是否正確清華大學(xué)C9函數(shù)調(diào)用：一個函數(shù)在調(diào)用子函數(shù)時，要將實在參數(shù)賦給形式參數(shù)。實在參數(shù)是一個具有確定值的表達式。例如：if(

checkprime(a)

)實在參數(shù)的個數(shù)及類型應(yīng)與形式參數(shù)一致，賦值時前后對應(yīng)關(guān)系不能改變。調(diào)用時1717實在參數(shù)a形式參數(shù)nintcheckprime(intn){…………}清華大學(xué)C9如何設(shè)計(定義)函數(shù)？函數(shù)名稱參數(shù)返回值求整數(shù)的絕對值

intabs(intx){……return…;}求兩個正整數(shù)的最小公倍數(shù)

intlcm(intx,inty){}計算n!unsignedlongFactorial(intn){}求Fibonacci數(shù)列的第n項

unsignedlongFibonacci(intn){}清華大學(xué)C9求一元二次方程的根

?Compute(doublea,doubleb,doublec){

?}判斷a是否為素數(shù)

intcheckPrime(intn)

{}計算整型數(shù)組元素的和

intSum(?)

{}將數(shù)組元素排序

?Sort(?)

{?}清華大學(xué)C9編寫函數(shù)Add，求兩個整數(shù)之和intAdd(intx,inty){intt;t=x+y;

returnt;}函數(shù)定義示例：Add函數(shù)intAdd(intx,inty){

returnx+y;}清華大學(xué)C9編寫函數(shù)Compare，比較兩個整型數(shù)據(jù)x、y的大小。若x等于y返回0，若x大于y返回1，若x小于y返回-1intCompare(intx,inty){intt;if(x==y)t=0;elseif(x>y)t=1;elset=-1;

returnt;}函數(shù)定義示例：

Compare函數(shù);多條return語句intCompare(intx,inty){if(x==y)

return0;

elseif(x>y)

return1;

else

return-1;}清華大學(xué)C9編寫函數(shù)Swap，互換兩個整型數(shù)據(jù)x、y的值void

Swap(intx,inty){intt;t=x;x=y;y=t;

return;

//沒有返回值只需直接寫return語句}函數(shù)定義示例：Swap函數(shù)清華大學(xué)C9intIsDigit(charc){ if(c>='0'&&c<='9') return1; else return0; } intIsDigit(charc){if(c>=48&&c<=57)return1;else return0; } 函數(shù)定義示例：IsDigit函數(shù)清華大學(xué)C9charTransformIntoUpperCase(charc){if(c>='a'&&c<='z')//‘a(chǎn)’~’z’的ASCII值為61H~7AH//‘A’~’Z’的ASCII值為41H~5AHreturnc–'a'+'A';elsereturnc;}函數(shù)定義示例：TransformIntoUpperCase

函數(shù)清華大學(xué)C9編寫函數(shù)IsLeapYear，判斷某個給定年份是否為閏年intIsLeapYear(intyear){

returnyear%4==0&&year%100!=0||year%400==0;}函數(shù)定義示例：IsLeapYear

函數(shù)清華大學(xué)C9intmysqrt(intx){inti=1,sum=0,count=0;while(sum<=x){sum+=i;count++;i+=2;}returncount-1;}求整數(shù)的平方根，取其整數(shù)部分思考：參數(shù)的有效性、合法性判斷應(yīng)放在函數(shù)里?放在主程序里?intmysqrt(intx){inti=0;while(i*i<=x)i++;returni-1;}函數(shù)定義示例：我的平方根函數(shù)清華大學(xué)C9…… intmain() {inttimes;charch;cout<<"Enteracharater:";cin>>ch;while(ch!='q'){cout<<"Enteraninteger:";cin>>times;

n_chars(ch,times);

cout<<"Thevalueoftimesis"<<times<<endl;cout<<"Enteracharater:";cin>>ch;}cout<<"Bye!!!\n"; return0;}例：字符串輸出voidn_chars(char,int);voidn_chars(charc,intn){while(n-->0)cout<<c;cout<<"\n";}清華大學(xué)C9……doublecube(doublex);intmain() {doublep,q;p=1.2;q=cube(p);cout<<"p="<<p<<endl;cout<<"實參p的地址是"<<&p<<endl;cout<<"q="<<q<<endl;return0;}doublecube(doublex){cout<<"x="<<x<<endl;cout<<"形參x的地址是"<<&x<<endl;return(x*x*x); }例：清華大學(xué)C9……intmain(){intx,y;

cin>>x;cin>>y;

cout<<x<<““<<y<<endl;(1)

Swap(x,y);cout<<x<<““<<y<<endl;(4)return0;}例：互換兩個整數(shù)voidSwap(intx,inty){inttemp;cout<<x<<““<<y<<endl;(2)

temp=x;x=y;y=temp;cout<<x<<““<<y<<endl;(3)return;}輸入：1020輸出：1020(1)1020(2)2010(3)1020(4)清華大學(xué)C9函數(shù)調(diào)用?？蚣?清華大學(xué)C9值傳遞與數(shù)據(jù)互換問題值傳遞：值復(fù)制操作將實際參數(shù)值復(fù)制給形式參數(shù)此過程單向不可逆復(fù)制完成后，形參與實參沒有任何關(guān)聯(lián)如何解決數(shù)據(jù)值互換問題？使用全局變量作為函數(shù)通信的手段使用指針傳遞變量的地址

缺點：

將全局變量作為函數(shù)調(diào)用環(huán)境的一部分，沒有在函數(shù)聲明頭部顯式給出來，不易理解代碼邏輯。清華大學(xué)C9……inta,b;/*全局變量，保證所有函數(shù)都可以訪問到*/voidSwap();/*不再需要函數(shù)參數(shù)*/intmain(){

cin>>a;cin>>b;

cout<<a<<““<<b<<endl;

Swap();cout<<a<<““<<b<<endl;return0;}voidSwap(){inttemp;cout<<a<<““<<b<<endl;

temp=a;a=b;b=temp;cout<<a<<““<<b<<endl;return;}輸出：1020102020102010清華大學(xué)C9【任務(wù)6.2】給歌手打分

定義intMax(inta,intb)函數(shù)，返回a,b中的大者定義intMin(inta,intb)函數(shù)，返回a,b中的小者定義整型變量p，用以保存N個數(shù)中的最大值定義整型變量q，用以保存N個數(shù)中的最小值定義一個整型變量sum做累加用最終得分：(sum-p-q)/(N-2)

清華大學(xué)C9#include<iostream>#include<cmath>usingnamespacestd;intMax(int,int);intMin(int,int);intmain(){intp=0;intq=100;intsum=0，x=0;inti=1;for(i=1;i<=10;i=i+1){cout<<“請第”<<i<<“位裁判給分”<<endl;cin>>x;p=Max(x,p);q=Min(x,q);sum=sum+x;

}cout<<“選手得分”<<(sum-p-q)/(10-2);return0;}intMax(inta,intb){if(a>b)

returna;elsereturnb;}intMin(intc,intd){if(c<d)

returnc;elsereturnd;}清華大學(xué)C9#include<iostream>#include<iomanip>usingnamespacestd;voidprint(int[],int);

//voidprint(int*,int);intmain(){constintn=5;inta[n];cout<<"Entermatrixa:\n";for(inti=0;i<n;i++)cin>>a[i];cout<<"Youhaveenteredthematrixa:\n";print(a,n);return0;}voidprint(intarray[],intsize)

//voidprint(int*array,intsize){for(intk=0;k<=size-1;k++)cout<<setw(10)<<array[k]<<endl;}問題：一維數(shù)組作為參數(shù)清華大學(xué)C9……voidbubble(int[],int);intmain(){ inta[10];……

bubble(a,10);……return0;}voidbubble(intarray[],intsize){for(intj=1;j<size;j++)for(inti=0;i<size-j;i++) if(array[i]<array[i+1]) {

intp=array[i];array[i]=array[i+1];array[i+1]=p; }}冒泡排序：清華大學(xué)C9#include<iostream>#include<iomanip>usingnamespacestd;voidprint(int[][4],int);intmain(){constintn=5;inta[n][4];cout<<"Entermatrixa:\n";for(inti=0;i<n;i++) for(intj=0;j<4;j++)cin>>a[i][j];cout<<"Youhaveenteredthematrixa:\n";print(a,n);return0;}voidprint(intarray[][4],intxsize){for(inti=0;i<=xsize-1;i++){ for(intj=0;j<4;j++)cout<<setw(10)<<array[i][j]; cout<<endl; }}問題：二維數(shù)組作為參數(shù)清華大學(xué)C96.2遞推

遞推是計算機數(shù)值計算中的一個重要算法，可將復(fù)雜運算化為若干重復(fù)的簡單運算，發(fā)揮計算機長于重復(fù)處理的特點?！救蝿?wù)6.3】五人分魚假定A、B、C、D、E五人的編號分別為1、2、3、4、5，整數(shù)數(shù)組fish[k]

表示第k個人所看到的魚數(shù)：

fish[1]A所看到的魚數(shù)，合伙捕到魚的總數(shù)

fish[2]=(fish[1]-1)*4/5B所看到的魚數(shù)

fish[3]=(fish[2]-1)*4/5C所看到的魚數(shù)

fish[4]=(fish[3]-1)*4/5D所看到的魚數(shù)

fish[5]=(fish[4]-1)*4/5E所看到的魚數(shù)清華大學(xué)C9寫成一般形式：

fish[i]=(fish[i-1]–1)*4/5i=2,3,…,5換一種寫法：

fish[i-1]=fish[i]*5/4+1 i=5,4,…,2分析：１.當(dāng)i=5時，fish[5]表示E醒來看到的魚數(shù)，該數(shù)應(yīng)滿足

fish[5]%5==12.當(dāng)i=5時，fish[i-1]表示D醒來看到的魚數(shù)，這個數(shù)要滿足

fish[4]=fish[5]*5/4+13.從小到大枚舉，可以把fish[5]初始化為6來試，之后每次增加

5再試，直至遞推到fish[1]得整數(shù)為止。清華大學(xué)C9【任務(wù)6.3】的程序框圖清華大學(xué)C9……intmain() {intfish[6]={1,1,1,1,1,1};

//記錄每人醒來后看到的魚數(shù)

inti=0;

do

{fish[5]=fish[5]+5;//讓E看到的魚數(shù)增5for(i=4;i>=1;i--){ if(fish[i+1]%4!=0) break; //跳出for循環(huán)

else fish[i]=fish[i+1]*5/4+1;//計算第i人看到的魚數(shù)

}

}while(i>=1);

for(i=1;i<=5;i++) cout<<fish[i]<<endl;return0;}清華大學(xué)C9……intmain() {intn=100,i=0;intq[101];q[0]=1;for(i=1;i<=n;i=i+1)q[i]=q[i-1]+i;cout<<“切100刀后最多可得”

<<q[n]<<"塊"<<endl;return0;}【任務(wù)6.4】王小二切餅124711切0刀切1刀切2刀切3刀切4刀

遞推公式：

q(0)=1q(n)=q(n-1)+n5051清華大學(xué)C9

遞歸算法在可計算性理論中占有重要地位，它是算法設(shè)計的有力工具，對于拓展編程思路非常有用。6.3遞歸及其實現(xiàn)遞歸的目的簡化復(fù)雜問題的手段：將問題逐步化簡（遞簡），在化簡過程中保持原問題的性質(zhì)不變，直到問題最簡，可以輕易地獲得答案；然后將簡化問題的答案組裝成原始問題的解（回歸）遞歸示例n!=123…n:n!=(n-1)!n;1!=1xn=xxx…x:xn=xn-1

x;x0=1清華大學(xué)C9或結(jié)點和與結(jié)點：ABC條件Z條件!ZABGZ1Z2ZnC……條件為Z1,Z2,…,Zn

A

取值為B

或C,…或

G或結(jié)點清華大學(xué)C9A

為與結(jié)點，A

的最終取值為C

結(jié)點的值，為了求得C的值，先求出B結(jié)點的值，C

是B的函數(shù)。ABCABDC與結(jié)點A

結(jié)點的值最終為

D

的值，為了求D

需要先求B

和C。先求左邊的點才能求最右邊的點。清華大學(xué)C9例如：求n!的與或圖直接可解結(jié)點清華大學(xué)C9C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=6例如：求3!的與或圖清華大學(xué)C9求3!的遞歸調(diào)用與返回清華大學(xué)C9求3!的程序框圖1清華大學(xué)C9求3!的程序框圖2清華大學(xué)C9……unsignedlongfact(unsignedint);intmain(){ intn=0; cout<<"請輸入n="; cin>>n; cout<<n<<"的階乘為"<<fact(n)<<endl; return0;}unsignedlongfact(unsignedintn){unsignedlongresult;if(n==1) result=1;else result=n*fact(n-1);returnresult;}【任務(wù)6.5】求n!清華大學(xué)C93nmainmain函數(shù)?？蚣芎瘮?shù)調(diào)用?？蚣芮迦A大學(xué)C9mainfact第一次以3為參數(shù)調(diào)用fact，進入函數(shù)時3nresult清華大學(xué)C9mainfact第二次以2為參數(shù)調(diào)用fact，進入函數(shù)時fact2nresult清華大學(xué)C9mainfact第三次以1為參數(shù)調(diào)用fact，進入函數(shù)時factfact1nresult清華大學(xué)C9mainfact第三次以1為參數(shù)調(diào)用fact，退出函數(shù)前factfact11nresult清華大學(xué)C9mainfact第二次以2為參數(shù)調(diào)用fact，退出函數(shù)前fact22nresult清華大學(xué)C9mainfact第一次以3為參數(shù)調(diào)用fact，退出函數(shù)前36nresult清華大學(xué)C93nmain遞歸調(diào)用結(jié)束后的main函數(shù)棧框架清華大學(xué)C9遞歸與遞推的比較（以求n!為例）遞推：從已知的初始條件出發(fā)，逐次去求所需要的階乘值。

fact(1)=1 fact(2)=2*fact(1)=2 fact(3)=3*fact(2)=6……遞歸：出發(fā)點不在初始條件上，而在求解目標上。從所求的未知項出發(fā)，逐次調(diào)用自身，直到遞歸的邊界（初始條件）。遞歸算法比較符合人的思維方式，邏輯性強，易于理解。清華大學(xué)C9遞歸與遞推的相似之處：

都基于控制結(jié)構(gòu)，均涉及循環(huán)遞推：使用顯式循環(huán)結(jié)構(gòu)遞歸：使用選擇結(jié)構(gòu)，通過重復(fù)性的函數(shù)調(diào)用實現(xiàn)循環(huán)

均涉及終止測試，都有可能發(fā)生無限循環(huán)遞推：在循環(huán)條件不滿足時終止遞歸：遇到初始條件時終止

理論上，能用遞歸解決的問題也能用遞推解決。清華大學(xué)C9計算xnlongdoubleCalPower(longdoublex,intn){longdoubleresult;if(n==0)result=1;elseresult=x*CalPower(x,n–1)

;returnresult;}算法舉例(1)清華大學(xué)C9求兩個正整數(shù)的最大公約數(shù)算法舉例(2)unsignedintgcd(unsignedintx,unsignedinty){unsignedintt;t=x<y?x:y;while(x%t!=0||y%t!=0)t--;returnt;}窮舉法清華大學(xué)C9歐氏算法步驟1：x整除以y，記余數(shù)為r步驟2：若r為0，則最大公約數(shù)即為y，算法結(jié)束步驟3：否則將y作為新x，將r作為新y，重復(fù)上述步驟unsignedintgcd(unsignedintx,unsignedinty){unsignedintr;while(1){r=x%y;if(r==0)returny;x=y;y=r;}}求兩個正整數(shù)的最大公約數(shù)unsi