《算法競(jìng)賽》課件1第3章 函數(shù)

目錄主要內(nèi)容函數(shù)的定義與使用內(nèi)聯(lián)函數(shù)函數(shù)重載使用C++系統(tǒng)函數(shù)學(xué)習(xí)建議用調(diào)試工具跟蹤函數(shù)的調(diào)用與返回分析遞歸函數(shù)的執(zhí)行過程完成本章習(xí)題與實(shí)驗(yàn)1函數(shù)定義函數(shù)定義的語(yǔ)法形式類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表）{

語(yǔ)句序列}<type1>name1,<type2>name2,...,<typen>namen是被初始化的內(nèi)部變量，壽命和可見性僅限于函數(shù)內(nèi)部表示返回值類型，由return語(yǔ)句給出返回值若無(wú)返回值，寫void，不必寫return語(yǔ)句。2函數(shù)的調(diào)用調(diào)用前先聲明函數(shù)：若函數(shù)定義在調(diào)用點(diǎn)之前，可以不另外聲明；若函數(shù)定義在調(diào)用點(diǎn)之后，必須要在調(diào)用函數(shù)前聲明函數(shù)原型：類型標(biāo)識(shí)符被調(diào)用函數(shù)名（含類型說明的形參表）;調(diào)用形式函數(shù)名（實(shí)參列表）嵌套調(diào)用在一個(gè)函數(shù)的函數(shù)體中，調(diào)用另一函數(shù)。遞歸調(diào)用函數(shù)直接或間接調(diào)用自身。3例3-1編寫一個(gè)求x的n次方的函數(shù)#include<iostream>usingnamespacestd;//計(jì)算x的n次方double

power(doublex,intn){ doubleval=1.0; while(n--)

val*=x; returnval;}intmain(){ cout<<"5tothepower2is"

<<power(5,2)<<endl; return0;}例3-2數(shù)制轉(zhuǎn)換題目：輸入一個(gè)8位二進(jìn)制數(shù)，將其轉(zhuǎn)換為十進(jìn)制數(shù)輸出。例如：11012=1(23)+1(22)+0(21)+1(20)=1310

所以，如果輸入1101，則應(yīng)輸出135例3-2（續(xù)）#include<iostream>usingnamespacestd;doublepower(doublex,intn);//計(jì)算x的n次方intmain(){ intvalue=0; cout<<"Enteran8bitbinarynumber"; for(inti=7;i>=0;i--){ charch; cin>>ch; if(ch=='1') value+=static_cast<int>(power(2,i)); } cout<<"Decimalvalueis"<<value<<endl; return0;}doublepower(doublex,intn){ doubleval=1.0; while(n--)

val*=x; returnval;}運(yùn)行結(jié)果：Enteran8bitbinarynumber01101001Decimalvalueis105例3-3編寫程序求π的值Π的計(jì)算公式如下：其中arctan用如下形式的級(jí)數(shù)計(jì)算：直到級(jí)數(shù)某項(xiàng)絕對(duì)值不大于10-15為止；π和x均為double型。...7例3-3（續(xù)）#include<iostream>usingnamespacestd;doublearctan(doublex){ doublesqr=x*x; doublee=x; doubler=0; inti=1; while(e/i>1e-15){ doublef=e/i;

r=(i%4==1)?r

+

f:r

-

f; e=e*sqr;

i+=2; } returnr;}累加和arctanx：r累加項(xiàng)f：初始x/1每項(xiàng)分子：在前一項(xiàng)基礎(chǔ)上*x2每項(xiàng)分母：在前一項(xiàng)基礎(chǔ)上+2每項(xiàng)符號(hào)：

i%4==1時(shí)為正，其他情況為負(fù)例3-3（續(xù)）intmain(){ doublea=16.0*arctan(1/5.0); doubleb=4.0*arctan(1/239.0);

//注意：因?yàn)檎麛?shù)相除結(jié)果取整，如果參數(shù)寫1/5，1/239，結(jié)果就都是0 cout<<"PI="<<a-b<<endl; return0;}運(yùn)行結(jié)果：PI=3.14159例3-4尋找并輸出11~999之間的數(shù)m，它滿足m、m2和m3均為回文數(shù)?；匚模焊魑粩?shù)字左右對(duì)稱的整數(shù)。

例如：11滿足上述條件

112=121，113=1331。分析：用除以10取余的方法，從最低位開始，依次取出該數(shù)的各位數(shù)字。按反序重新構(gòu)成新的數(shù)，比較與原數(shù)是否相等，若相等，則原數(shù)為回文。10例3-4（續(xù)）#include<iostream>usingnamespacestd;//判斷n是否為回文數(shù)boolsymm(unsignedn){unsignedi=n; unsignedm=0; while(i>0){ m=m*10+i%10;

i/=10;}returnm==n;}例3-4（續(xù)）intmain(){ for(unsignedm=11;m<1000;m++) if(symm(m)&&symm(m*m)&&

symm(m*m*m)){ cout<<"m="<<m; cout<<"m*m="<<m*m; cout<<"m*m*m=" <<m*m*m<<endl; } return0;}例3-4（續(xù)）運(yùn)行結(jié)果：m=11m*m=121m*m*m=1331m=101m*m=10201m*m*m=1030301m=111m*m=12321m*m*m=1367631例3-5計(jì)算如下公式，并輸出結(jié)果：其中r、s的值由鍵盤輸入。sinx的近似值按如下公式計(jì)算，計(jì)算精度為10-10：...14例3-5（續(xù)）#include<iostream>#include<cmath>//對(duì)標(biāo)準(zhǔn)庫(kù)中數(shù)學(xué)函數(shù)的說明usingnamespacestd;

constdoubleTINY_VALUE=1e-10;

doubletsin(doublex){doubleg=0;doublet=x;intn=1;do{g+=t;n++;t=-t*x*x/(2*n-1)/(2*n-2); }while(fabs(t)>=TINY_VALUE);returng;}

計(jì)算精度為10-10例3-5（續(xù)）intmain(){doublek,r,s;cout<<"r=";cin>>r;cout<<"s=";cin>>s;if(r*r<=s*s) k=sqrt(tsin(r)*tsin(r)+tsin(s)*tsin(s));else k=tsin(r*s)/2;cout<<k<<endl;return0;}運(yùn)行結(jié)果：r=5s=81.37781例3-6投骰子的隨機(jī)游戲每個(gè)骰子有六面，點(diǎn)數(shù)分別為1、2、3、4、5、6。游戲者在程序開始時(shí)輸入一個(gè)無(wú)符號(hào)整數(shù)，作為產(chǎn)生隨機(jī)數(shù)的種子。每輪投兩次骰子，第一輪如果和數(shù)為7或11則為勝，游戲結(jié)束；和數(shù)為2、3或12則為負(fù)，游戲結(jié)束；和數(shù)為其它值則將此值作為自己的點(diǎn)數(shù)，繼續(xù)第二輪、第三輪...直到某輪的和數(shù)等于點(diǎn)數(shù)則取勝，若在此前出現(xiàn)和數(shù)為7則為負(fù)。由rolldice函數(shù)負(fù)責(zé)模擬投骰子、計(jì)算和數(shù)并輸出和數(shù)。17例3-6（續(xù)）rand函數(shù)原型：intrand(void);所需頭文件：<cstdlib>功能和返回值：求出并返回一個(gè)偽隨機(jī)數(shù)srand函數(shù)原型：voidsrand(unsignedintseed);參數(shù)：seed產(chǎn)生隨機(jī)數(shù)的種子。所需頭文件：<cstdlib>功能：為使rand()產(chǎn)生一序列偽隨機(jī)整數(shù)而設(shè)置起始點(diǎn)。使用1作為seed參數(shù)，可以重新初化rand()。18例3-6（續(xù)）#include<iostream>#include<cstdlib>usingnamespacestd;

enumGameStatus{WIN,LOSE,PLAYING};

intmain(){intsum,myPoint;GameStatusstatus;unsignedseed;introllDice();

cout<<"Pleaseenteranunsignedinteger:";

cin>>seed;//輸入隨機(jī)數(shù)種子

srand(seed);//將種子傳遞給rand()例3-6（續(xù)）sum=rollDice();//第一輪投骰子、計(jì)算和數(shù)switch(sum){case7://如果和數(shù)為7或11則為勝,狀態(tài)為WINcase11:status=WIN;break;case2://和數(shù)為2、3或12則為負(fù),狀態(tài)為L(zhǎng)OSEcase3:case12:status=LOSE;break;default://其它情況，尚無(wú)結(jié)果，狀態(tài)為PLAYING，記下點(diǎn)數(shù)

status=PLAYING;myPoint=sum;cout<<"pointis"<<myPoint<<endl;break;}例3-6（續(xù)）while(status==PLAYING){//只要狀態(tài)為PLAYING，繼續(xù)

sum=rollDice();if(sum==myPoint)//某輪的和數(shù)等于點(diǎn)數(shù)則取勝status=WIN;elseif(sum==7)//出現(xiàn)和數(shù)為7則為負(fù)status=LOSE;}//當(dāng)狀態(tài)不為PLAYING時(shí)循環(huán)結(jié)束，輸出游戲結(jié)果

if(status==WIN)cout<<"playerwins"<<endl;elsecout<<"playerloses"<<endl;return0;}例3-6（續(xù)）//投骰子、計(jì)算和數(shù)、輸出和數(shù)introllDice(){ intdie1=1+rand()%6; intdie2=1+rand()%6; intsum=die1+die2; cout<<"playerrolled"<<die1<<"+"<<die2<<"="<<sum<<endl; returnsum;}例3-6（續(xù)）運(yùn)行結(jié)果：Pleaseenteranunsignedinteger:23playerrolled6+3=9pointis9playerrolled5+4=9playerwins嵌套調(diào)用main{}調(diào)fun1()結(jié)束fun1()調(diào)fun2()返回fun2()返回①②③⑦④⑤⑥⑧⑨24例3-7輸入兩個(gè)整數(shù)，求平方和#include<iostream>usingnamespacestd;intfun2(intm){ returnm*m;}intfun1(intx,inty){ returnfun2(x)+fun2(y);}intmain(){ inta,b; cout<<"Pleaseentertwointegers(aandb):"; cin>>a>>b; cout<<"Thesumofsquareofaandb:"<<fun1(a,b)<<endl; return0;}運(yùn)行結(jié)果：Pleaseentertwointegers(aandb):34Thesumofsquareofaandb:25例3-8求n!分析：計(jì)算n!的公式如下：這是一個(gè)遞歸形式的公式，應(yīng)該用遞歸函數(shù)實(shí)現(xiàn)。26遞歸調(diào)用過程函數(shù)直接或間接地調(diào)用自身，稱為遞歸調(diào)用。例如：計(jì)算n!遞歸算法執(zhí)行的兩個(gè)階段：遞推：

4!=4×3!→3!=3×2!→2!=2×1!→1!=1×0!→0!=1未知已知回歸：4!=4×3!=24←3!=3×2!=6←2!=2×1!=2←1!=1×0!=1←0!=1未知已知27例3-8（續(xù)）#include<iostream>usingnamespacestd;unsignedfac(intn){ unsignedf;

if(n==0) f=1;else f=fac(n-1)*n;returnf;}intmain(){ unsignedn; cout<<"Enterapositiveinteger:"; cin>>n; unsignedy=fac(n); cout<<n<<"!="<<y<<endl; return0;}運(yùn)行結(jié)果：Enterapositiveinteger:88!=40320例3-9題目：用遞歸法計(jì)算從n個(gè)人中選擇k個(gè)人組成一個(gè)委員會(huì)的不同組合數(shù)。分析：由n個(gè)人里選k個(gè)人的組合數(shù)

=由n-1個(gè)人里選k個(gè)人的組合數(shù)+由n-1個(gè)人里選k-1個(gè)人的組合數(shù)當(dāng)n=k或k=0時(shí)，組合數(shù)為129例3-9（續(xù)）#include<iostream>usingnamespacestd;intcomm(intn,intk){ if(k>n) return0; elseif(n==k||k==0) return1; else returncomm(n-1,k)+comm(n-1,k-1);}intmain(){ intn,k; cout<<"Pleaseentertwointegersnandk:"; cin>>n>>k; cout<<"C(n,k)="<<comm(n,k)<<endl; return0;}運(yùn)行結(jié)果：1858568例3-10有三根針A、B、C。A針上有N個(gè)盤子，大的在下，小的在上，要求把這N個(gè)盤子從A針移到C針，在移動(dòng)過程中可以借助B針，每次只允許移動(dòng)一個(gè)盤，且在移動(dòng)過程中在三根針上都保持大盤在下，小盤在上。ABC31例3-10（續(xù)）將n個(gè)盤子從A針移到C針可以分解為三個(gè)步驟：①將A上n-1個(gè)盤子移到B針上（借助C針）;②把A針上剩下的一個(gè)盤子移到C針上;③將n-1個(gè)盤子從B針移到C針上（借助A針）;上面三個(gè)步驟包含兩種操作：①將多個(gè)盤子從一個(gè)針移到另一個(gè)針上，這是一個(gè)遞歸的過程。hanoi函數(shù)實(shí)現(xiàn)。②將1個(gè)盤子從一個(gè)針上移到另一針上。用move函數(shù)實(shí)現(xiàn)。32例3-10（續(xù)）#include<iostream>usingnamespacestd;//將src針的最上面一個(gè)盤子移動(dòng)到dest針上voidmove(charsrc,chardest){ cout<<src<<"-->"<<dest<<endl;}//將n個(gè)盤子從src針移動(dòng)到dest針，以medium針作為中轉(zhuǎn)voidhanoi(intn,charsrc,charmedium,chardest){if(n==1) move(src,dest);else{ hanoi(n-1,src,dest,medium); move(src,dest); hanoi(n-1,medium,src,dest);}}例3-10（續(xù)）intmain(){ intm; cout<<"Enterthenumberofdiskes:"; cin>>m; cout<<"thestepstomoving"<<m<<"diskes:"<<endl; hanoi(m,'A','B','C'); return0;}例3-10（續(xù)）運(yùn)行結(jié)果：Enterthenumberofdiskes:3thestepstomoving3diskes:A-->CA-->BC-->BA-->CB-->AB-->CA-->C函數(shù)的參數(shù)傳遞在函數(shù)被調(diào)用時(shí)才分配形參的存儲(chǔ)單元實(shí)參可以是常量、變量或表達(dá)式實(shí)參類型必須與形參相符或可隱式轉(zhuǎn)換為形參類型值傳遞是傳遞參數(shù)值，即單向傳遞引用傳遞可以實(shí)現(xiàn)雙向傳遞常引用作參數(shù)可以保障實(shí)參數(shù)據(jù)的安全36例3-11輸入兩個(gè)整數(shù)并交換（值傳遞）#include<iostream>usingnamespacestd;voidswap(inta,intb){ intt=a; a=b; b=t;}intmain(){ intx=5,y=10; cout<<"x="<<x<<"y="<<y<<endl;

swap(x,y); cout<<"x="<<x<<"y="<<y<<endl; return0;}運(yùn)行結(jié)果：x=5y=10x=5y=10a=b;5x10y5a10b執(zhí)行主函數(shù)中的函數(shù)調(diào)用swap(x,y);t=a;5x10y5a10b5tb=t;5x10y10a5b5t5x10y10a10b5t在swap子函數(shù)中返回主函數(shù)以后5x10y例3-11輸入兩個(gè)整數(shù)并交換（值傳遞）例3-12輸入兩個(gè)整數(shù)交換后輸出（引用傳遞）#include<iostream>usingnamespacestd;voidswap(int&a,int&b){ intt=a; a=b; b=t;}intmain(){ intx=5,y=10; cout<<"x="<<x<<"y="<<y<<endl;

swap(x,y); cout<<"x="<<x<<"y="<<y<<endl; return0;}運(yùn)行結(jié)果:x=5y=10x=10y=5t=a;x5t5x的引用axy510y的引用x的引用aby的引用x的引用abx10y10a=bb=t;y5t5y的引用bxy105swap(x,y);例3-12（續(xù)）引用類型引用(&)是標(biāo)識(shí)符的別名,例如:inti,j;

int&ri=i;//定義int引用ri，并初始化為變量i的引用

j=10;

ri=j;//相當(dāng)于i=j;聲明一個(gè)引用時(shí)，必須同時(shí)對(duì)它進(jìn)行初始化，使它指向一個(gè)已存在的對(duì)象。一旦一個(gè)引用被初始化后，就不能改為指向其它對(duì)象。引用可以作為形參

voidswap(int&a,int&b){...}41可變數(shù)量形參使用模板類initializer_list<T>（T為類模板，模板將于第9章介紹）可向函數(shù)傳遞同類型不定個(gè)數(shù)參數(shù),例如:

voidlog_info(initializer_list<string>lst){ for(auto

&info:

lst) cout<<info<<‘’; cout<<endl;

}

log_info({“Hello”,

”world”,

“!”});initializer_list<string>lst接受不定個(gè)數(shù)字符串實(shí)參注意，實(shí)參以大括號(hào)列表方式給出使用范圍for語(yǔ)句遍歷lst，auto自動(dòng)推斷元素為string類型42內(nèi)聯(lián)函數(shù)聲明時(shí)使用關(guān)鍵字inline。編譯時(shí)在調(diào)用處用函數(shù)體進(jìn)行替換,節(jié)省了參數(shù)傳遞、控制轉(zhuǎn)移等開銷。注意：內(nèi)聯(lián)函數(shù)體內(nèi)不能有循環(huán)語(yǔ)句和switch語(yǔ)句；內(nèi)聯(lián)函數(shù)的定義必須出現(xiàn)在內(nèi)聯(lián)函數(shù)第一次被調(diào)用之前；對(duì)內(nèi)聯(lián)函數(shù)不能進(jìn)行異常接口聲明。43例3-14內(nèi)聯(lián)函數(shù)應(yīng)用舉例#include<iostream>usingnamespacestd;constdoublePI=3.14159265358979;inlinedoublecalArea(doubleradius){ returnPI*radius*radius;}intmain(){ doubler=3.0;

doublearea=calArea(r); cout<<area<<endl; return0;}帶默認(rèn)參數(shù)值的函數(shù)可以預(yù)先設(shè)置默認(rèn)的參數(shù)值，調(diào)用時(shí)如給出實(shí)參，則采用實(shí)參值，否則采用預(yù)先設(shè)置的默認(rèn)參數(shù)值。例如：intadd(intx=5,inty=6){ returnx+y;}intmain(){ add(10,20);//10+20 add(10);//10+6 add();//5+6}45默認(rèn)參數(shù)值的說明次序有默認(rèn)參數(shù)的形參必須列在形參列表的最右，即默認(rèn)參數(shù)值的右面不能有無(wú)默認(rèn)值的參數(shù)調(diào)用時(shí)實(shí)參與形參的結(jié)合次序是從左向右例：intadd(intx,inty=5,intz=6);//正確intadd(intx=1,inty=5,intz);//錯(cuò)誤intadd(intx=1,inty,intz=6);//錯(cuò)誤46默認(rèn)參數(shù)值與函數(shù)的調(diào)用位置如果一個(gè)函數(shù)有原型聲明，且原型聲明在定義之前，則默認(rèn)參數(shù)值必須在函數(shù)原型聲明中給出；而如果只有函數(shù)的定義，或函數(shù)定義在前，則默認(rèn)參數(shù)值需在函數(shù)定義中給出。例：intadd(intx=5,inty=6){//只有定義，沒有原型聲明returnx+y;}intmain(){add();}intadd(intx=5,inty=6);//原型聲明在前intmain(){add();}intadd(intx,inty){//此處不能再指定默認(rèn)值returnx+y;}47例3-15計(jì)算長(zhǎng)方體的體積函數(shù)getVolume計(jì)算體積有三個(gè)形參：length（長(zhǎng)）、width（寬）、height（高），其中width和height帶有默認(rèn)值。主函數(shù)中以不同形式調(diào)用getVolume函數(shù)48例3-15（續(xù)）//3_15.cpp#include<iostream>#include<iomanip>usingnamespacestd;

intgetVolume(intlength,intwidth=2,intheight=3);

intmain(){ constintX=10,Y=12,Z=15; cout<<"Someboxdatais"; cout<<getVolume(X,Y,Z)<<endl; cout<<"Someboxdatais"; cout<<getVolume(X,Y)<<endl; cout<<"Someboxdatais"; cout<<getVolume(X)<<endl; return0;}intgetVolume(intlength,intwidth,intheight){ cout<<setw(5)<<length<<setw(5)<<width<<setw(5)<<height<<'\t'; returnlength*width*height;}

函數(shù)重載C++允許功能相近的函數(shù)在相同的作用域內(nèi)以相同函數(shù)名聲明，從而形成重載。方便使用，便于記憶。例：形參類型不同intadd(int

x,

int

y);floatadd(floatx,floaty);形參個(gè)數(shù)不同intadd(intx,inty);intadd(intx,inty,intz);50注意事項(xiàng)不要將不同功能的函數(shù)聲明為重載函數(shù)，以免出現(xiàn)調(diào)用結(jié)果的誤解、混淆。這樣不好：intadd(intx,inty);intadd(inta,intb);編譯器不以形參名來(lái)區(qū)分intadd(intx,inty);voidadd(intx,inty);編譯器不以返回值來(lái)區(qū)分intadd(intx,inty){returnx+

y;}floatadd(floatx,floaty){returnx-

y;}重載函數(shù)的形參必須不同:個(gè)數(shù)不同或類型不同。編譯程序?qū)⒏鶕?jù)實(shí)參和形參的類型及個(gè)數(shù)的最佳匹配來(lái)選擇調(diào)用哪一個(gè)函數(shù)。51例3-16重載函數(shù)應(yīng)用舉例編寫兩個(gè)名為sumOfSquare的重載函數(shù)，分別求兩整數(shù)的平方和及兩實(shí)數(shù)的平方和。52例3-16（續(xù)）#include<iostream>usingnamespacestd;intsumOfSquare(inta,intb){returna*a+b*b;}doublesumOfSq