第6單元函數(shù)作者：林厚從信息學奧賽課課通（C++）第1頁第1課模塊化編程思想學習目標1.體會模塊化編程思想。2.了解函數(shù)功效和調用。第2頁一個C++程序不論大小，都由一個或者多個“函數(shù)”組成，而且其中必須有且只有一個函數(shù)main（），稱之為“主函數(shù)”，由函數(shù)main（）調用其它函數(shù)來完成程序特定功效。當然，其它函數(shù)之間也能夠按照規(guī)則相互調用。C++中函數(shù)由一段相對獨立代碼組成，這段代碼能實現(xiàn)某一項詳細、獨立、完整功效。函數(shù)在程序設計中作用主要有兩個，一是“代碼重用”；二是“問題分解”。第3頁代碼重用是確保同一個函數(shù)能夠被一個或多個函數(shù)調用任意屢次，從而降低重復代碼編寫。問題分解能夠確保一個大程序（或者說軟件），按照模塊化編程思想，由大化小，分解成若干個結構清楚、功效獨立、調試方便函數(shù)，甚至給若干人合作完成，從而提升開發(fā)效率。C++提供了很多慣用系統(tǒng)函數(shù)，如輸入單個字符函數(shù)getchar()等。不過有些函數(shù)，必須要加上相關頭文件才能使用，比如整數(shù)取絕對值函數(shù)abs()、求算術平方根函數(shù)sqrt()等，必須要包含“cmath”。第4頁例1、曼哈頓距離【問題描述】平面直角坐標系中位于坐標（x1，y1）i點與位于坐標（x2，y2）j點曼哈頓距離為d（i，j）=|x1-x2|+|y1-y2|。請編程輸入兩個點坐標，輸出它們之間曼哈頓距離?！据斎敫袷健恳恍兴膫€整數(shù)（100以內(nèi)），分別表示兩個點坐標（x1，y1）和（x2，y2）。【輸出格式】一行一個整數(shù)，表示兩個點之間曼哈頓距離?！据斎霕永?05620【輸出樣例】19第5頁//p6-1-1#include<iostream>#include<cmath>usingnamespacestd;intmain(){longlongx1,y1,x2,y2,mht;cin>>x1>>y1>>x2>>y2;

mht=abs(x1-x2)+abs(y1-y2);cout<<mht<<endl;return0;}第6頁例2、回文數(shù)個數(shù)【問題描述】輸入一個正整數(shù)n，求1~n之間“回文數(shù)”個數(shù)?；匚臄?shù)是指一個數(shù)倒過來和原數(shù)一樣，如12121、11、1221、1是回文數(shù)，而1231不是回文數(shù)。【輸入格式】一行一個正整數(shù)n，1≤n≤10000?！据敵龈袷健恳恍幸粋€正整數(shù)，表示1~n之間回文數(shù)個數(shù)?！据斎霕永?2【輸出樣例】10第7頁【問題分析】定義一個計數(shù)器變量并初始化為0，然后窮舉1~n中每一個整數(shù)i，判斷是否是回文數(shù)，是則計數(shù)器加一。怎樣判斷i是回文數(shù)呢？C++系統(tǒng)函數(shù)里沒有，只能自己編寫一個。第8頁//p6-1-2#include<cstdio>usingnamespacestd;//在此自定義一個函數(shù)check()，假如i是回文數(shù)返回true，不然返回falseintmain(){intn,i,ans=0;scanf(“%d”,&n);for(i=1;i<=n;i++)if(check(i))ans++;printf(“%d\n”,ans);return0;}第9頁實踐鞏固第10頁第2課函數(shù)定義和調用學習目標1.學會函數(shù)定義和調用。2.應用函數(shù)處理一些實際問題。第11頁C++要求函數(shù)必須先定義、后使用。定義函數(shù)，就是要說明函數(shù)返回值類型、函數(shù)名、函數(shù)參數(shù)，以及完成特定功效語句組合（函數(shù)體）。函數(shù)定義和調用第12頁1.函數(shù)定義定義函數(shù)格式以下：返回值類型函數(shù)名（參數(shù)列表）{

函數(shù)體}其中，第一行稱為函數(shù)頭部。函數(shù)名是標識這個函數(shù)正當標識符。返回值類型是指一個函數(shù)結束后返回給調用者一個“返回值”數(shù)據(jù)類型。有些函數(shù)功效是執(zhí)行一系列操作，而不返回任何值，這種情況下，返回值類型是關鍵字void。參數(shù)列表是當函數(shù)被調用時，調用者向函數(shù)傳遞各種“參數(shù)”，此處參數(shù)稱為形式參數(shù)，參數(shù)列表包含參數(shù)數(shù)據(jù)類型和參數(shù)名，參數(shù)是可選，沒有參數(shù)就是“無參”函數(shù)，不過括號不能省略。第13頁1.函數(shù)定義

大括號之間部分稱為“函數(shù)體”，主要包含變量說明語句、表示式語句等。假如有返回值，則函數(shù)體內(nèi)最少有一條語句“return表示式”。在執(zhí)行函數(shù)體過程中，一旦碰到return語句，執(zhí)行完就立刻退出函數(shù)，不再執(zhí)行后續(xù)語句。無返回值函數(shù)不需要return語句。第14頁2.函數(shù)調用在程序中以任何方式對函數(shù)使用，都稱為函數(shù)調用。函數(shù)調用是經(jīng)過“函數(shù)名”進行，普通格式為：函數(shù)名（參數(shù)列表）此處參數(shù)列表稱為“實際參數(shù)”，是傳遞給調用函數(shù)，必須嚴格對應函數(shù)定義時函數(shù)頭部形式參數(shù)列表，包含參數(shù)個數(shù)、參數(shù)次序、數(shù)據(jù)類型。調用無參函數(shù)時參數(shù)列表能夠沒有，但括號不能省略。假如參數(shù)列表包含多個參數(shù)，則各參數(shù)間用逗號隔開。第15頁函數(shù)調用方式以函數(shù)在程序中出現(xiàn)位置和形式來看，函數(shù)調用方式分為三種。（1）函數(shù)調用作為一條獨立語句，完成一件事情（一系列操作），沒有任何返回值。比如：print(n);doit(dep,total);

input();（2）函數(shù)調用結果作為表示式一部分。比如：intt=compute(i,j)

+i*j;（3）以實參形式出現(xiàn)在其它函數(shù)調用中。比如：number=min(sum(-5,100),n);num=max(max(a,b),

c);第16頁例1、閱讀程序，寫出程序運行結果，體會“代碼重用”和“有返回值函數(shù)”調用。//p6-2-1#include<iostream>usingnamespacestd;intfac(intn){intz=1;for(inti=1;i<=n;i++)z=z*i;returnz;}intmain(){intx=fac(5)+fac(4);//函數(shù)調用出現(xiàn)在表示式中cout<<x<<endl;return0;}第17頁例2、閱讀程序，寫出程序運行結果，體會“無返回值函數(shù)”調用。//p6-2-2#include<iostream>usingnamespacestd;voidmaxnum(intx,inty){intw=x>y?x:y;cout<<w<<endl;}intmain(){inta=5,b=22;maxnum(a,b);//函數(shù)調用作為一條獨立語句return0;}第18頁例3、閱讀程序，寫出程序運行結果，體會函數(shù)“提前申明”。//p6-2-3#include<iostream>usingnamespacestd;intbig(intx,inty);//函數(shù)提前申明intmain(){intx,y,z;cin>>x>>y>>z;cout<<big(big(x,y),z)<<endl;//函數(shù)調用返回值又作為其它函數(shù)調用實際參數(shù)return0;}intbig(intx,inty){//函數(shù)定義if(x>y)returnx;elsereturny;}第19頁例4、統(tǒng)計閏年【問題描述】輸入兩個年份x和y，統(tǒng)計并輸出公元x年到公元y年之間全部閏年數(shù)（包含x年和y年），1≤x≤y≤3000?！据斎敫袷健恳恍袃蓚€正整數(shù)表示x和y，之間用一個空格隔開。【輸出格式】一行一個正整數(shù)，表示公元x年到公元y年之間全部閏年數(shù)。【輸入樣例】

【輸出樣例】2第20頁//p6-2-4#include<iostream>usingnamespacestd;boolrn(intn){if((n%4==0)&&(n%100!=0)||(n%400==0))returntrue;elsereturnfalse;}intmain(){intx,y,t=0;cin>>x>>y;for(inti=x;i<=y;i++)if(rn(i))t++;cout<<t<<endl;return0;}第21頁例5、數(shù)分離【問題描述】定義一函數(shù)digit(n,k)分離出整數(shù)n從右邊數(shù)第k個數(shù)字。如digit(2076,1)等于6，而digit(2076,5)等于0。main函數(shù)輸入n和k，調用digit(n,k)輸出答案，n在longlong范圍內(nèi)?！据斎敫袷健恳恍袃蓚€整數(shù)分別表示n和k，之間用一個空格隔開?！据敵龈袷健恳恍幸粋€整數(shù)，表示整數(shù)n從右邊數(shù)第k個數(shù)字。【輸入樣例】318593【輸出樣例】8第22頁//p6-2-5#include<iostream>usingnamespacestd;intdigit(longlongn,intk){inttmp;for(inti=1;i<=k;i++){tmp=n%10;n=n/10;}returntmp;}intmain(){longlongn;intk;cin>>n>>k;cout<<digit(n,k)<<endl;return0;}第23頁實踐鞏固第24頁第3課函數(shù)參數(shù)學習目標1.了解形式參數(shù)與實際參數(shù)。2.了解參數(shù)傳遞三種方式。第25頁函數(shù)參數(shù)參數(shù)是函數(shù)與函數(shù)之間實現(xiàn)通信數(shù)據(jù)“接口”。函數(shù)調用過程就是調用者帶著實際參數(shù)（假如有）執(zhí)行函數(shù)，將實際參數(shù)“傳遞”給形式參數(shù)，執(zhí)行完函數(shù)體后再將計算得到返回值傳遞給調用者（假如有）。

在未調用函數(shù)前，函數(shù)中形式參數(shù)并不分配內(nèi)存空間。只有在被調用執(zhí)行時，才被分配暫時存放空間。函數(shù)調用結束后，形式參數(shù)內(nèi)存空間將被操作系統(tǒng)立刻收回。第26頁函數(shù)參數(shù)實際參數(shù)能夠是任何符合形式參數(shù)類型常量、變量、表示式。函數(shù)參數(shù)傳遞過程就是實際參數(shù)和形式參數(shù)相結合過程，必須恪守三個一致。（1）個數(shù)一致。（2）次序一致。（3）類型一致。第27頁例1、打印字符三角形【問題描述】

編寫一個函數(shù)print(n,ch)，表示打印一行n個英文字母ch，并換行。然后，在函數(shù)main()中輸入n和ch，調用函數(shù)print()打印一個字符三角形。【輸入格式】一行一個整數(shù)n和一個英文字母ch，之間用一個空格隔開，1≤n≤20?！据敵龈袷健縩行，第i行有i個字母ch?！据斎霕永?a【輸出樣例】aaaaaa第28頁//p6-3-1#include<iostream>usingnamespacestd;voidprint(inti,charch){for(intj=1;j<=i;j++)cout<<ch;cout<<endl;}intmain(){intn;charch;cin>>n>>ch;for(inti=1;i<=n;i++)print(i,ch);return0;}第29頁函數(shù)參數(shù)傳遞方式依據(jù)不一樣應用需求，函數(shù)參數(shù)傳遞方式，或者說函數(shù)參數(shù)調用方式分為三種：（1）傳值（調用）：參見例2；（2）傳址（調用）：參見例3；（3）引用（調用）：參見例4、例5；第30頁例2、閱讀程序，寫出程序運行結果，體會函數(shù)傳值(調用)。//p6-3-2#include<iostream>usingnamespacestd;voidswap(intx,inty){inttemp;temp=x;x=y;y=temp;cout<<x<<““<<y<<endl;}intmain(){inta=10,b=50;swap(a,b);cout<<a<<““<<b<<endl;return0;}第31頁例3、閱讀程序，寫出程序運行結果，體會函數(shù)傳址(調用)。//p6-3-3#include<iostream>usingnamespacestd;voidswap(int*x,int*y){//形式參數(shù)類型定義為指針inttemp;temp=*x;*x=*y;*y=temp;cout<<*x<<““<<*y<<endl;}intmain(){inta=10,b=50;swap(&a,&b);//實際參數(shù)必須是地址cout<<a<<““<<b<<endl;return0;}第32頁例4、閱讀程序，寫出程序運行結果，體會變量及其引用操作。//p6-3-4//#include<iostream>usingnamespacestd;intmain(){intk=32;

int&k_adr=k;cout<<“k=”<<k<<“k_adr=”<<k_adr<<endl;k++;cout<<“k=”<<k<<“k_adr=”<<k_adr<<endl;k_adr=-5;cout<<“k=”<<k<<“k_adr=”<<k_adr<<endl;inti=100;k_adr+=i;cout<<“k=”<<k<<“k_adr=”<<k_adr<<endl;return0;}第33頁例5、閱讀程序，寫出程序運行結果，體會函數(shù)引用調用。//p6-3-5#include<iostream>usingnamespacestd;voidswap(int&a,int&b){inttemp;temp=a;a=b;b=temp;cout<<a<<““<<b<<endl;}intmain(){inta=10,b=50;swap(a,b);cout<<a<<““<<b<<endl;return0;}第34頁實踐鞏固第35頁第4課變量作用域學習目標1.了解變量作用域。2.熟練規(guī)范使用局部變量和全局變量。第36頁變量作用域變量按其在程序中作用范圍，分為全局變量和局部變量。全局變量是指定義在任何函數(shù)之外變量，也就是不被任何“｛函數(shù)體｝”所包含，能夠被源文件中其它函數(shù)所共用，用靜態(tài)數(shù)據(jù)區(qū)存放，作用域（有效范圍）是從定義變量位置開始到源文件（整個程序）結束。局部變量是指在一個函數(shù)（包含main函數(shù)）內(nèi)部定義變量，它只在本函數(shù)內(nèi)部有效，其它函數(shù)不能使用這些變量，用動態(tài)數(shù)據(jù)區(qū)存放，函數(shù)參數(shù)也是局部變量。第37頁例1、以下程序中，哪些是全局變量，哪些是局部變量，并指出它們作用域。intx,y;floata,b;floatfind(intc,d){floate,f;inti,j;…}intz;voiddoit(){…}intmain(){intg,h;…}第38頁例2、找出程序中錯誤。假如去掉錯誤，程序輸出什么。//p6-4-2#include<iostream>usingnamespacestd;intf(){intb=0,c=1;b=b+1;c=c+1;return(b+c);}intmain(){for(inti=1;i<4;i++)cout<<i<<“.sum=”<<f()<<endl;cout<<“b=”<<b<<“c=”<<c<<endl;return0;}第39頁C++允許在更多地方定義變量，比如for第一個子句，if、for或者while語句塊{}內(nèi)。這些變量只在當前語句塊內(nèi)有效。一個語句塊內(nèi)只能定義一個同名變量。不一樣函數(shù)內(nèi)部能夠使用相同名稱變量，它們代表不一樣對象，相互獨立，互不干擾。訪問同名變量時、只能訪問到當前有效、且最近定義該變量。尤其地，在變量前加“::”能夠指定訪問全局變量。在寫復雜代碼時，能夠利用這些特征，調整暫時變量定義位置和作用域，以躲避變量重名帶來編譯錯誤。第40頁例3、找出程序中錯誤。假如去掉錯誤，程序輸出什么。//p6-4-3#include<iostream>usingnamespacestd;intx=233;intmain(){intx;cin>>x;for(inti=1;i<=x;++i){intx,y;cin>>x>>y;cout<<x+y<<endl;}cout<<x<<endl;cout<<::x<<endl;cout<<i<<““<<y<<endl;return0;}第41頁例4、閱讀程序，寫出程序運行結果。//p6-4-4#include<iostream>usingnamespacestd;intx=10,y=15;voidchange(inta,intb,intx){inttemp;x++;y++;temp=a;a=b;b=temp;}intmain(){inta=3,b=5;cout<<x<<“”<<y<<“”<<a<<“”<<b<<endl;change(a,b,x);cout<<x<<“”<<y<<“”<<a<<“”<<b<<endl;return0;}第42頁實踐鞏固第43頁第5課函數(shù)遞歸調用學習目標1.了解函數(shù)遞歸調用。2.應用遞歸法處理一些實際問題。第44頁函數(shù)遞歸調用函數(shù)調用自己，這種調用稱為“遞歸”調用，這么函數(shù)稱為“遞歸函數(shù)”。第45頁例1、閱讀程序，寫出程序運行結果。利用單步跟蹤，體會函數(shù)遞歸調用執(zhí)行過程。//p6-5-1#include<iostream>usingnamespacestd;voidp(intn){if(n>0){p(n-1);for(inti=0;i<n;i++)cout<<n;cout<<endl;}}intmain(){p(5);return0;}第46頁遞歸調用一個問題要想用遞歸方法（函數(shù)）來處理，必須要符合兩個條件。（1）能夠把這個問題轉化成一個新問題，而新問題解法和原問題解法完全相同，只是問題規(guī)模變小了；（2）必須要有一個明確遞歸結束條件（遞歸邊界）。第47頁例2、求階乘【問題描述】編程求n階乘值，n!=1×2×3×…×(n-1)×n?！据斎敫袷健恳恍幸粋€正整數(shù)n，1≤n≤20?！据敵龈袷健恳恍幸粋€正整數(shù)，表示n!值?！据斎霕永?【輸出樣例】120第48頁【問題分析】求n!值帶有顯著遞歸思想。要想求出n!，就要先求（n-1）!，因為（n-1）!乘以n就是n!；而要求（n-1）!又要先求出（n-2）!，因為（n-2）！乘以（n-1）就是（n-1）!；……要求2!又要先求出1!，因為2乘以1！就是2!；而1！是已知，就是1。所以，階乘問題遞歸公式為：第49頁//p6-5-2#include<iostream>usingnamespacestd;longlongjc(intn){if(n==1)return1;//遞歸邊界returnjc(n-1)*n;//遞歸公式}intmain(){intn;cin>>n;cout<<jc(n)<<endl;return0;}第50頁求5！遞歸調用過程以下:第51頁例3、求最大條約數(shù)【問題描述】輸入兩個正整數(shù)m和n，求它們最大條約數(shù)?！据斎敫袷健恳恍袃蓚€正整數(shù)m和n，用一個空格隔開，2≤m，n≤10000?！据敵龈袷健恳恍幸粋€正整數(shù)，表示m和n最大條約數(shù)?！据斎霕永?436【輸出樣例】12第52頁【問題分析】用歐幾里得“輾轉相除法”演示求最大條約數(shù)過程，發(fā)覺（m，n）最大條約數(shù)與（n，m%n）最大條約數(shù)是一樣，不過數(shù)據(jù)規(guī)模變小了。所以，最大條約數(shù)問題遞歸公式為：第53頁//p6-5-3#include<iostream>usingnamespacestd;intgcd(intm,intn){if(n==0)returnm;elsereturngcd(n,m%n);}intmain(){intm,n;cin>>m>>n;cout<<gcd(m,n)<<endl;return0;}第54頁例4、分解質因子【問題描述】輸入一個正整數(shù)n，用遞歸方法從小到大輸出它全部質因子（因子是質數(shù)）?！据斎敫袷健恳恍幸粋€正整數(shù)n，2≤n≤10000?！据敵龈袷健恳恍腥舾蓚€正整數(shù)，兩數(shù)之間用一個空格隔開，從小到大輸出?！据斎霕永?8【輸出樣例】233第55頁【問題分析】顯然，假如n等于1，就沒法再分解了。假如n大于1，從整數(shù)p（p從2開始）開始試除，假如能被p整除，就得到一個質因子p。問題就轉化成對于整數(shù)n/p，從p開始繼續(xù)分解質因子。假如不能被p整除，問題就轉化為對于整數(shù)n，從p+1開始分解質因子。所以，遞歸公式為：第56頁//p6-5-4#include<iostream>usingnamespacestd;boolfirst=true;voidzyz(intn,intp){if(n>1){if(n%p==0){if(first){cout<<p;first=false;}elsecout<<““<<p;zyz(n/p,p);}elsezyz(n,p+1);}}intmain(){intn;cin>>n;zyz(n,2);cout<<endl;return0;}第57頁例5、抽獎問題描述參見教材213頁?！締栴}分析】我們已經(jīng)學習過用循環(huán)語句實現(xiàn)“二分查找”，很顯著，也能夠采取“遞歸”思想實現(xiàn)二分查找。第58頁//p6-5-5#include<iostream>usingnamespacestd;intwin,g[101];

intbinsearch(intleft,intright){ if(left<=right){ intmid=(left+right)/2; if(g[mid]==win)returnmid;//找到 if(win<g[mid])returnbinsearch(left,mid-1);//在左半部分 if(win>g[mid])returnbinsearch(mid+1,right);//在右半部分 } elsereturn0;//沒找到

}

intmain(){ intn,i,f,left,right,mid; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&g[i]); cin>>win;