信息學(xué)奧賽課課通-第6單元 電子課件

第6單元函數(shù)信息學(xué)奧賽課課通（C++）2021/5/91第1課模塊化編程思想學(xué)習(xí)目標(biāo)1.體會模塊化編程思想。2.了解函數(shù)的功能和調(diào)用。2021/5/92一個C++程序無論大小，都由一個或者多個“函數(shù)”組成，而且其中必須有且只有一個函數(shù)main（），稱之為“主函數(shù)”，由函數(shù)main（）調(diào)用其他函數(shù)來完成程序的特定功能。當(dāng)然，其他函數(shù)之間也可以按照規(guī)則互相調(diào)用。C++中的函數(shù)由一段相對獨立的代碼組成，這段代碼能實現(xiàn)某一項具體、獨立、完整的功能。函數(shù)在程序設(shè)計中的作用主要有兩個，一是“代碼重用”；二是“問題分解”。2021/5/93代碼重用是保證同一個函數(shù)可以被一個或多個函數(shù)調(diào)用任意多次，從而減少重復(fù)代碼的編寫。問題分解可以保證一個大的程序（或者說軟件），按照模塊化編程思想，由大化小，分解成若干個結(jié)構(gòu)清晰、功能獨立、調(diào)試方便的函數(shù)，甚至給若干人合作完成，從而提高開發(fā)效率。C++提供了很多常用的系統(tǒng)函數(shù)，如輸入單個字符的函數(shù)getchar()等。但是有些函數(shù)，必須要加上相關(guān)頭文件才能使用，例如整數(shù)取絕對值的函數(shù)abs()、求算術(shù)平方根的函數(shù)sqrt()等，必須要包含“cmath”。2021/5/94例1、曼哈頓距離【問題描述】平面直角坐標(biāo)系中位于坐標(biāo)（x1，y1）的i點與位于坐標(biāo)（x2，y2）的j點的曼哈頓距離為d（i，j）=|x1-x2|+|y1-y2|。請編程輸入兩個點的坐標(biāo)，輸出它們之間的曼哈頓距離。【輸入格式】一行四個整數(shù)（100以內(nèi)），分別表示兩個點的坐標(biāo)（x1，y1）和（x2，y2）?！据敵龈袷健恳恍幸粋€整數(shù)，表示兩個點之間的曼哈頓距離?！据斎霕永?05620【輸出樣例】192021/5/95//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;}2021/5/96例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【輸出樣例】102021/5/97【問題分析】定義一個計數(shù)器變量并初始化為0，然后窮舉1~n中的每一個整數(shù)i，判斷是否是回文數(shù)，是則計數(shù)器加一。如何判斷i是回文數(shù)呢？C++系統(tǒng)函數(shù)里沒有，只能自己編寫一個。2021/5/98//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;}2021/5/99實踐鞏固2021/5/910第2課函數(shù)的定義和調(diào)用學(xué)習(xí)目標(biāo)1.學(xué)會函數(shù)的定義和調(diào)用。2.應(yīng)用函數(shù)解決一些實際問題。2021/5/911C++要求函數(shù)必須先定義、后使用。定義函數(shù)，就是要說明函數(shù)的返回值類型、函數(shù)名、函數(shù)參數(shù)，以及完成特定功能的語句組合（函數(shù)體）。函數(shù)的定義和調(diào)用2021/5/9121.函數(shù)的定義定義函數(shù)的格式如下：返回值類型函數(shù)名（參數(shù)列表）{

函數(shù)體}其中，第一行稱為函數(shù)頭部。函數(shù)名是標(biāo)識這個函數(shù)的合法標(biāo)識符。返回值類型是指一個函數(shù)結(jié)束后返回給調(diào)用者的一個“返回值”的數(shù)據(jù)類型。有些函數(shù)的功能是執(zhí)行一系列操作，而不返回任何值，這種情況下，返回值類型是關(guān)鍵字void。參數(shù)列表是當(dāng)函數(shù)被調(diào)用時，調(diào)用者向函數(shù)傳遞的各種“參數(shù)”，此處的參數(shù)稱為形式參數(shù)，參數(shù)列表包括參數(shù)的數(shù)據(jù)類型和參數(shù)名，參數(shù)是可選的，沒有參數(shù)就是“無參”函數(shù)，但是括號不能省略。2021/5/9131.函數(shù)的定義

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

input();（2）函數(shù)調(diào)用的結(jié)果作為表達式的一部分。例如：intt=compute(i,j)

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

c);2021/5/916例1、閱讀程序，寫出程序的運行結(jié)果，體會“代碼重用”和“有返回值函數(shù)”的調(diào)用。//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ù)調(diào)用出現(xiàn)在表達式中cout<<x<<endl;return0;}2021/5/917例2、閱讀程序，寫出程序的運行結(jié)果，體會“無返回值函數(shù)”的調(diào)用。//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ù)調(diào)用作為一條獨立語句return0;}2021/5/918例3、閱讀程序，寫出程序的運行結(jié)果，體會函數(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ù)調(diào)用的返回值又作為其他函數(shù)調(diào)用的實際參數(shù)return0;}intbig(intx,inty){//函數(shù)定義if(x>y)returnx;elsereturny;}2021/5/919例4、統(tǒng)計閏年【問題描述】輸入兩個年份x和y，統(tǒng)計并輸出公元x年到公元y年之間的所有閏年數(shù)（包括x年和y年），1≤x≤y≤3000。【輸入格式】一行兩個正整數(shù)表示x和y，之間用一個空格隔開。【輸出格式】一行一個正整數(shù)，表示公元x年到公元y年之間的所有閏年數(shù)?！据斎霕永?0002004【輸出樣例】22021/5/920//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;}2021/5/921例5、數(shù)的分離【問題描述】定義一函數(shù)digit(n,k)分離出整數(shù)n從右邊數(shù)第k個數(shù)字。如digit(2076,1)等于6，而digit(2076,5)等于0。main函數(shù)輸入n和k，調(diào)用digit(n,k)輸出答案，n在longlong范圍內(nèi)。【輸入格式】一行兩個整數(shù)分別表示n和k，之間用一個空格隔開?！据敵龈袷健恳恍幸粋€整數(shù)，表示整數(shù)n從右邊數(shù)第k個數(shù)字?！据斎霕永?18593【輸出樣例】82021/5/922//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;}2021/5/923實踐鞏固2021/5/924第3課函數(shù)的參數(shù)學(xué)習(xí)目標(biāo)1.理解形式參數(shù)與實際參數(shù)。2.理解參數(shù)傳遞的三種方式。2021/5/925函數(shù)的參數(shù)參數(shù)是函數(shù)與函數(shù)之間實現(xiàn)通信的數(shù)據(jù)“接口”。函數(shù)調(diào)用的過程就是調(diào)用者帶著實際參數(shù)（如果有）執(zhí)行函數(shù)，將實際參數(shù)“傳遞”給形式參數(shù)，執(zhí)行完函數(shù)體后再將計算得到的返回值傳遞給調(diào)用者（如果有）。

在未調(diào)用函數(shù)前，函數(shù)中的形式參數(shù)并不分配內(nèi)存空間。只有在被調(diào)用執(zhí)行時，才被分配臨時存儲空間。函數(shù)調(diào)用結(jié)束后，形式參數(shù)的內(nèi)存空間將被操作系統(tǒng)立刻收回。2021/5/926函數(shù)的參數(shù)實際參數(shù)可以是任何符合形式參數(shù)類型的常量、變量、表達式。函數(shù)參數(shù)傳遞的過程就是實際參數(shù)和形式參數(shù)相結(jié)合的過程，必須遵守三個一致。（1）個數(shù)一致。（2）順序一致。（3）類型一致。2021/5/927例1、打印字符三角形【問題描述】

編寫一個函數(shù)print(n,ch)，表示打印一行n個英文字母ch，并換行。然后，在函數(shù)main()中輸入n和ch，調(diào)用函數(shù)print()打印一個字符三角形?！据斎敫袷健恳恍幸粋€整數(shù)n和一個英文字母ch，之間用一個空格隔開，1≤n≤20?！据敵龈袷健縩行，第i行有i個字母ch?！据斎霕永?a【輸出樣例】aaaaaa2021/5/928//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;}2021/5/929函數(shù)參數(shù)的傳遞方式根據(jù)不同的應(yīng)用需求，函數(shù)參數(shù)的傳遞方式，或者說函數(shù)參數(shù)的調(diào)用方式分為三種：（1）傳值（調(diào)用）：參見例2；（2）傳址（調(diào)用）：參見例3；（3）引用（調(diào)用）：參見例4、例5；2021/5/930例2、閱讀程序，寫出程序的運行結(jié)果，體會函數(shù)的傳值(調(diào)用)。//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;}2021/5/931例3、閱讀程序，寫出程序的運行結(jié)果，體會函數(shù)的傳址(調(diào)用)。//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;}2021/5/932例4、閱讀程序，寫出程序的運行結(jié)果，體會變量及其引用的操作。//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;}2021/5/933例5、閱讀程序，寫出程序的運行結(jié)果，體會函數(shù)的引用調(diào)用。//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;}2021/5/934實踐鞏固2021/5/935第4課變量的作用域?qū)W習(xí)目標(biāo)1.理解變量的作用域。2.熟練規(guī)范使用局部變量和全局變量。2021/5/936變量的作用域變量按其在程序中的作用范圍，分為全局變量和局部變量。全局變量是指定義在任何函數(shù)之外的變量，也就是不被任何“｛函數(shù)體｝”所包含，可以被源文件中其他函數(shù)所共用，用靜態(tài)數(shù)據(jù)區(qū)存儲，作用域（有效范圍）是從定義變量的位置開始到源文件（整個程序）結(jié)束。局部變量是指在一個函數(shù)（包括main函數(shù)）內(nèi)部定義的變量，它只在本函數(shù)內(nèi)部有效，其他函數(shù)不能使用這些變量，用動態(tài)數(shù)據(jù)區(qū)存儲，函數(shù)的參數(shù)也是局部變量。2021/5/937例1、以下程序中，哪些是全局變量，哪些是局部變量，并指出它們的作用域。intx,y;floata,b;floatfind(intc,d){floate,f;inti,j;…}intz;voiddoit(){…}intmain(){intg,h;…}2021/5/938例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;}2021/5/939C++允許在更多地方定義變量，例如for的第一個子句，if、for或者while語句塊的{}內(nèi)。這些變量只在當(dāng)前語句塊內(nèi)有效。一個語句塊內(nèi)只能定義一個同名變量。不同的函數(shù)內(nèi)部可以使用相同名稱的變量，它們代表不同的對象，相互獨立，互不干擾。訪問同名變量時、只能訪問到當(dāng)前有效、且最近定義的該變量。特別地，在變量前加“::”可以指定訪問全局變量。在寫復(fù)雜代碼時，可以利用這些特性，調(diào)整臨時變量的定義位置和作用域，以規(guī)避變量重名帶來的編譯錯誤。2021/5/940例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;}2021/5/941例4、閱讀程序，寫出程序的運行結(jié)果。//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;}2021/5/942實踐鞏固2021/5/943第5課函數(shù)的遞歸調(diào)用學(xué)習(xí)目標(biāo)1.理解函數(shù)的遞歸調(diào)用。2.應(yīng)用遞歸法解決一些實際問題。2021/5/944函數(shù)的遞歸調(diào)用函數(shù)調(diào)用自己，這種調(diào)用稱為“遞歸”調(diào)用，這樣的函數(shù)稱為“遞歸函數(shù)”。2021/5/945例1、閱讀程序，寫出程序的運行結(jié)果。利用單步跟蹤，體會函數(shù)遞歸調(diào)用執(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;}2021/5/946遞歸的調(diào)用一個問題要想用遞歸的方法（函數(shù)）來解決，必須要符合兩個條件。（1）可以把這個問題轉(zhuǎn)化成一個新問題，而新問題的解法和原問題的解法完全相同，只是問題規(guī)模變小了；（2）必須要有一個明確的遞歸結(jié)束條件（遞歸邊界）。2021/5/947例2、求階乘【問題描述】編程求n階乘的值，n!=1×2×3×…×(n-1)×n?！据斎敫袷健恳恍幸粋€正整數(shù)n，1≤n≤20?！据敵龈袷健恳恍幸粋€正整數(shù)，表示n!的值?！据斎霕永?【輸出樣例】1202021/5/948【問題分析】求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。所以，階乘問題的遞歸公式為：2021/5/949//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;}2021/5/950求5！的遞歸調(diào)用過程如下:2021/5/951例3、求最大公約數(shù)【問題描述】輸入兩個正整數(shù)m和n，求它們的最大公約數(shù)。【輸入格式】一行兩個正整數(shù)m和n，用一個空格隔開，2≤m，n≤10000。【輸出格式】一行一個正整數(shù)，表示m和n的最大公約數(shù)?！据斎霕永?436【輸出樣例】122021/5/952【問題分析】用歐幾里得“輾轉(zhuǎn)相除法”演示求最大公約數(shù)的過程，發(fā)現(xiàn)（m，n）的最大公約數(shù)與（n，m%n）的最大公約數(shù)是一樣的，但是數(shù)據(jù)規(guī)模變小了。所以，最大公約數(shù)問題的遞歸公式為：2021/5/953//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;}2021/5/954例4、分解質(zhì)因子【問題描述】輸入一個正整數(shù)n，用遞歸方法從小到大輸出它的所有質(zhì)因子（因子是質(zhì)數(shù)）。【輸入格式】一行一個正整數(shù)n，2≤n≤10000?！据敵龈袷健恳恍腥舾蓚€正整數(shù)，兩數(shù)之間用一個空格隔開，從小到大輸出?！据斎霕永?8【輸出樣例】2332021/5/955【問題分析】顯然，如果n等于1，就沒法再分解了。如果n大于1，從整數(shù)p（p從2開始）開始試除，如果能被p整除，就得到一個質(zhì)因子p。問題就轉(zhuǎn)化成對于整數(shù)n/p，從p開始繼續(xù)分解質(zhì)因子。如果不能被p整除，問題就轉(zhuǎn)化為對于整數(shù)n，從p+1開始分解質(zhì)因子。所以，遞歸公式為：2021/5/956//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;}2021/5/957例5、抽獎問題描述參見教材213頁?！締栴}分析】我們已經(jīng)學(xué)習(xí)過用循環(huán)語句實現(xiàn)“二分查找”，很明顯，也可以采用“遞歸”思想實現(xiàn)二分查找。2021/5/958//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;f=