第6單元函數(shù)PPT課件

1、高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+） 高等教育出版社高等教育出版社 第第 6 單元單元 函數(shù)函數(shù)信息學奧賽信息學奧賽高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）第第 1 課課 模塊化編程思想模塊化編程思想學習目標學習目標1. 體會模塊化編程思想。體會模塊化編程思想。2. 了解函數(shù)的功能和調用。了解函數(shù)的功能和調用。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）一個一個 C+ 程序無論大小，都由一個或者多個程序無論大小，都由一個或者多個“函數(shù)函數(shù)”組成，而且其中必須有且只有一個函數(shù)組成，而且其中必須有且只有一個函

2、數(shù)main（），稱之（），稱之為為“主函數(shù)主函數(shù)”，由函數(shù)，由函數(shù) main（）調用其他函數(shù)來完成程（）調用其他函數(shù)來完成程序的特定功能。當然，其他函數(shù)之間也可以按照規(guī)則互序的特定功能。當然，其他函數(shù)之間也可以按照規(guī)則互相調用。相調用。C+ 中的函數(shù)由一段相對獨立的代碼組成，這段代中的函數(shù)由一段相對獨立的代碼組成，這段代碼能實現(xiàn)某一項具體、獨立、完整的功能。碼能實現(xiàn)某一項具體、獨立、完整的功能。函數(shù)在程序設計中的作用主要有兩個，一是函數(shù)在程序設計中的作用主要有兩個，一是“代碼代碼重用重用”；二是；二是“問題分解問題分解”。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）代

3、碼重用是保證同一個函數(shù)可以被一個或多個函數(shù)調用代碼重用是保證同一個函數(shù)可以被一個或多個函數(shù)調用任意多次，從而減少重復代碼的編寫。問題分解可以保證任意多次，從而減少重復代碼的編寫。問題分解可以保證一個大的程序（或者說軟件），按照模塊化編程思想，由一個大的程序（或者說軟件），按照模塊化編程思想，由大化小，分解成若干個結構清晰、功能獨立、調試方便的大化小，分解成若干個結構清晰、功能獨立、調試方便的函數(shù)，甚至給若干人合作完成，從而提高開發(fā)效率函數(shù)，甚至給若干人合作完成，從而提高開發(fā)效率。 C+提供了很多常用的系統(tǒng)函數(shù)，如輸入單個字符的函數(shù)提供了很多常用的系統(tǒng)函數(shù)，如輸入單個字符的函數(shù)getchar()

4、等。但是有些函數(shù)，必須要加上相關頭文件才能使用等。但是有些函數(shù)，必須要加上相關頭文件才能使用，例如整數(shù)取絕對值的函數(shù)，例如整數(shù)取絕對值的函數(shù)abs()、求算術平方根的函數(shù)、求算術平方根的函數(shù)sqrt()等，必須要包含等，必須要包含“cmath”。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例1、曼哈頓距離、曼哈頓距離【問題描述問題描述】平面直角坐標系中位于坐標（平面直角坐標系中位于坐標（x1，y1）的）的 i 點與位于坐標（點與位于坐標（x2，y2）的）的 j 點的曼哈頓距離為點的曼哈頓距離為 d（i，j） = |x1-x2| + |y1-y2|。請編程輸入兩個點的

5、。請編程輸入兩個點的坐標，輸出它們之間的曼哈頓距離。坐標，輸出它們之間的曼哈頓距離。【輸入格式輸入格式】一行四個整數(shù)（一行四個整數(shù)（100 以內），分別表示兩個點的坐標（以內），分別表示兩個點的坐標（x1，y1）和（）和（x2，y2）。）?！据敵龈袷捷敵龈袷健恳恍幸粋€整數(shù)，表示兩個點之間的曼哈頓距離。一行一個整數(shù)，表示兩個點之間的曼哈頓距離。【輸入樣例輸入樣例】10 5 6 20【輸出樣例輸出樣例】19高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-1-1#include#includeusing namespace std;int main() long lon

6、g x1,y1,x2,y2,mht; cin x1 y1 x2 y2; mht = abs(x1 - x2) + abs(y1 - y2); cout mht endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例2、回文數(shù)個數(shù)回文數(shù)個數(shù)【問題描述問題描述】輸入一個正整數(shù)輸入一個正整數(shù) n，求，求 1n 之間之間“回文數(shù)回文數(shù)”的個數(shù)?；匚臄?shù)的個數(shù)?；匚臄?shù)是指一個數(shù)倒過來和原數(shù)一樣，如是指一個數(shù)倒過來和原數(shù)一樣，如 12121、11、1221、1 是是回文數(shù)，而回文數(shù)，而 1231 不是回文數(shù)。不是回文數(shù)。【輸入格式輸入格式】一行一個正整數(shù)一行

7、一個正整數(shù) n，1n10000?！据敵龈袷捷敵龈袷健恳恍幸粋€正整數(shù)，表示一行一個正整數(shù)，表示 1n 之間回文數(shù)的個數(shù)。之間回文數(shù)的個數(shù)?！据斎霕永斎霕永?2【輸出樣例輸出樣例】10高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）【問題分析問題分析】定義一個計數(shù)器變量并初始化為定義一個計數(shù)器變量并初始化為 0，然后窮舉，然后窮舉 1n 中的每一中的每一個整數(shù)個整數(shù) i，判斷是否是回文數(shù)，是則計數(shù)器加一。如何判斷，判斷是否是回文數(shù)，是則計數(shù)器加一。如何判斷 i 是回文數(shù)呢？是回文數(shù)呢？ C+ 系統(tǒng)函數(shù)里沒有，只能自己編寫一個。系統(tǒng)函數(shù)里沒有，只能自己編寫一個。高等教育出版

8、社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6 -1-2#includeusing namespace std;/ 在此自定義一個函數(shù)在此自定義一個函數(shù) check()，如果，如果 i 是回文數(shù)返回是回文數(shù)返回 true，否則返回否則返回 falseint main() int n,i,ans = 0; scanf( “ %d ” ,&n); for(i = 1; i = n; i+) if(check(i) ans+; printf( “ %dn ” ,ans); return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）實踐鞏固實踐鞏

9、固高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）第第 2 課課 函數(shù)的定義和調用函數(shù)的定義和調用學習目標學習目標1. 學會函數(shù)的定義和調用。學會函數(shù)的定義和調用。2. 應用函數(shù)解決一些實際問題。應用函數(shù)解決一些實際問題。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）C+ 要求函數(shù)必須先定義、后使用。定義函數(shù)，就是要要求函數(shù)必須先定義、后使用。定義函數(shù)，就是要說明函數(shù)的返回值類型、函數(shù)名、函數(shù)參數(shù)，以及完成特說明函數(shù)的返回值類型、函數(shù)名、函數(shù)參數(shù)，以及完成特定功能的語句組合（函數(shù)體）。定功能的語句組合（函數(shù)體）。函數(shù)的定義和調用函數(shù)的定義和調用高等

10、教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）1. 函數(shù)的定義函數(shù)的定義定義函數(shù)的格式如下：定義函數(shù)的格式如下：返回值類型返回值類型 函數(shù)名（參數(shù)列表）函數(shù)名（參數(shù)列表） 函數(shù)體函數(shù)體其中，第一行稱為函數(shù)頭部。函數(shù)名是標識這個函數(shù)的其中，第一行稱為函數(shù)頭部。函數(shù)名是標識這個函數(shù)的合法標識符。返回值類型是指一個函數(shù)結束后返回給調用合法標識符。返回值類型是指一個函數(shù)結束后返回給調用者的一個者的一個“返回值返回值”的數(shù)據(jù)類型。的數(shù)據(jù)類型。有些函數(shù)的功能是執(zhí)行有些函數(shù)的功能是執(zhí)行一系列操作，而不返回任何值，這種情況下，返回值類型一系列操作，而不返回任何值，這種情況下，返回值類型是關

11、鍵字是關鍵字void。參數(shù)列表是當函數(shù)被調用時，調用者向函數(shù)。參數(shù)列表是當函數(shù)被調用時，調用者向函數(shù)傳遞的各種傳遞的各種“參數(shù)參數(shù)”，此處的參數(shù)稱為形式參數(shù)，參數(shù)列，此處的參數(shù)稱為形式參數(shù)，參數(shù)列表包括參數(shù)的數(shù)據(jù)類型和參數(shù)名，參數(shù)是可選的，沒有參表包括參數(shù)的數(shù)據(jù)類型和參數(shù)名，參數(shù)是可選的，沒有參數(shù)就是數(shù)就是“無參無參”函數(shù)，但是括號不能省略。函數(shù)，但是括號不能省略。 高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）1. 函數(shù)的定義函數(shù)的定義 大括號之間的部分稱為大括號之間的部分稱為“函數(shù)體函數(shù)體”，主要包括變量說，主要包括變量說明語句、表達式語句等。如果有返回值，則函數(shù)體

12、內至少明語句、表達式語句等。如果有返回值，則函數(shù)體內至少有一條語句有一條語句“return 表達式表達式”。在執(zhí)行函數(shù)體的過程中，一。在執(zhí)行函數(shù)體的過程中，一旦遇到旦遇到return語句，執(zhí)行完就立刻退出函數(shù)，不再執(zhí)行后續(xù)語句，執(zhí)行完就立刻退出函數(shù)，不再執(zhí)行后續(xù)的語句。無返回值函數(shù)不需要的語句。無返回值函數(shù)不需要return語句。語句。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）2. 函數(shù)的調用函數(shù)的調用在程序中以任何方式對函數(shù)的使用，都稱為函數(shù)的調用。在程序中以任何方式對函數(shù)的使用，都稱為函數(shù)的調用。函數(shù)調用是通過函數(shù)調用是通過“函數(shù)名函數(shù)名”進行的，進行的，一般格

13、式為：一般格式為：函數(shù)名（參數(shù)列表）函數(shù)名（參數(shù)列表）此處的參數(shù)列表稱為此處的參數(shù)列表稱為“實際參數(shù)實際參數(shù)”，是傳遞給調用函數(shù)，是傳遞給調用函數(shù)的，必須嚴格對應函數(shù)定義時函數(shù)頭部的形式參數(shù)列表，的，必須嚴格對應函數(shù)定義時函數(shù)頭部的形式參數(shù)列表，包括參數(shù)個數(shù)、參數(shù)順序、數(shù)據(jù)類型。調用無參函數(shù)時參包括參數(shù)個數(shù)、參數(shù)順序、數(shù)據(jù)類型。調用無參函數(shù)時參數(shù)列表可以沒有，但括號不能省略。如果參數(shù)列表包含多數(shù)列表可以沒有，但括號不能省略。如果參數(shù)列表包含多個參數(shù)，則各參數(shù)間用逗號隔開。個參數(shù)，則各參數(shù)間用逗號隔開。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）函數(shù)調用方式函數(shù)調用方式

14、以函數(shù)在程序中出現(xiàn)的位置和形式來看，函數(shù)調用方式以函數(shù)在程序中出現(xiàn)的位置和形式來看，函數(shù)調用方式分為三種。分為三種。（1）函數(shù)調用作為一條獨立語句，完成一件事情（一）函數(shù)調用作為一條獨立語句，完成一件事情（一系列操作），沒有任何返回值。例如：系列操作），沒有任何返回值。例如：print (n); doit(dep,total); input( );（2）函數(shù)調用的結果作為表達式的一部分。例如：）函數(shù)調用的結果作為表達式的一部分。例如：int t = compute(i,j) + i*j;（3）以實參形式出現(xiàn)在其他函數(shù)調用中。例如：）以實參形式出現(xiàn)在其他函數(shù)調用中。例如：number = min

15、(sum(-5,100),n); num = max(max(a,b), c);高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例1、閱讀程序，寫出程序的運行結果，體會、閱讀程序，寫出程序的運行結果，體會“代碼代碼重用重用”和和“有返回值函數(shù)有返回值函數(shù)”的調用。的調用。/p6-2-1#include using namespace std;int fac(int n) int z = 1; for(int i = 1; i = n; i+) z = z * i; return z;int main() int x = fac(5) + fac(4);/ 函數(shù)調用出現(xiàn)在

16、表達式中函數(shù)調用出現(xiàn)在表達式中 cout x endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例2、閱讀程序，寫出程序的運行結果，體會、閱讀程序，寫出程序的運行結果，體會“無返無返回值函數(shù)回值函數(shù)”的調用。的調用。/p6-2-2#include using namespace std;void maxnum(int x,int y) int w = x y ? x : y; cout w endl;int main() int a = 5,b = 22; maxnum(a,b);/ 函數(shù)調用作為一條獨立語句函數(shù)調用作為一條獨立語句 retu

17、rn 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例3、閱讀程序，寫出程序的運行結果，體會函數(shù)的、閱讀程序，寫出程序的運行結果，體會函數(shù)的“提前聲明提前聲明”。/p6-2-3#includeusing namespace std;int big(int x,int y);/ 函數(shù)的提前聲明函數(shù)的提前聲明int main() int x,y,z; cin x y z; cout big(big(x,y),z) y) return x; else return y;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例4、統(tǒng)計閏年、統(tǒng)計閏年【問題

18、描述問題描述】輸入兩個年份輸入兩個年份 x 和和 y，統(tǒng)計并輸出公元，統(tǒng)計并輸出公元 x 年到公元年到公元 y 年之間的年之間的所有閏年數(shù)（包括所有閏年數(shù)（包括 x 年和年和 y 年），年），1xy3000?！据斎敫袷捷斎敫袷健恳恍袃蓚€正整數(shù)表示一行兩個正整數(shù)表示 x 和和 y，之間用一個空格隔開。，之間用一個空格隔開?！据敵龈袷捷敵龈袷健恳恍幸粋€正整數(shù)，表示公元一行一個正整數(shù)，表示公元 x 年到公元年到公元 y 年之間的所有閏年年之間的所有閏年數(shù)。數(shù)?！据斎霕永斎霕永?000 2004【輸出樣例輸出樣例】2高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-2-

19、4#include using namespace std;bool rn(int n) if(n % 4 = 0) & (n % 100 != 0) | (n % 400 = 0) return true; else return false;int main() int x,y,t = 0; cin x y; for(int i = x; i = y; i+) if(rn(i) t+; cout t endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例5、數(shù)的分離、數(shù)的分離【問題描述問題描述】定義一函數(shù)定義一函數(shù) digit (n

20、,k) 分離出整數(shù)分離出整數(shù) n 從右邊數(shù)第從右邊數(shù)第 k 個數(shù)字。個數(shù)字。如如 digit(2076,1) 等于等于 6，而，而 digit(2076,5) 等于等于 0。main 函數(shù)輸函數(shù)輸入入 n 和和 k，調用，調用 digit(n,k) 輸出答案，輸出答案，n 在在 long long 范圍內。范圍內?！据斎敫袷捷斎敫袷健恳恍袃蓚€整數(shù)分別表示一行兩個整數(shù)分別表示 n 和和 k，之間用一個空格隔開。，之間用一個空格隔開?！据敵龈袷捷敵龈袷健恳恍幸粋€整數(shù)，表示整數(shù)一行一個整數(shù)，表示整數(shù) n 從右邊數(shù)第從右邊數(shù)第 k 個數(shù)字。個數(shù)字?！据斎霕永斎霕永?1859 3【輸出樣例輸出樣例】

21、8高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-2-5#include using namespace std;int digit(long long n,int k) int tmp; for(int i = 1; i n k; cout digit(n,k) endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）實踐鞏固實踐鞏固高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）第第 3 課課 函數(shù)的參數(shù)函數(shù)的參數(shù)學習目標學習目標1. 理解形式參數(shù)與實際參數(shù)。理解形式參數(shù)與實際參數(shù)。2. 理解參

22、數(shù)傳遞的三種方式。理解參數(shù)傳遞的三種方式。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）函數(shù)的參數(shù)函數(shù)的參數(shù)參數(shù)是函數(shù)與函數(shù)之間實現(xiàn)通信的數(shù)據(jù)參數(shù)是函數(shù)與函數(shù)之間實現(xiàn)通信的數(shù)據(jù)“接口接口”。函數(shù)。函數(shù)調用的過程就是調用者帶著實際參數(shù)（如果有）執(zhí)行函數(shù)，調用的過程就是調用者帶著實際參數(shù)（如果有）執(zhí)行函數(shù)，將實際參數(shù)將實際參數(shù)“傳遞傳遞”給形式參數(shù)，執(zhí)行完函數(shù)體后再將計給形式參數(shù)，執(zhí)行完函數(shù)體后再將計算得到的返回值傳遞給調用者（如果有）。算得到的返回值傳遞給調用者（如果有）。 在未調用函數(shù)前，函數(shù)中的形式參數(shù)并不分配內存在未調用函數(shù)前，函數(shù)中的形式參數(shù)并不分配內存空間。只有

23、在被調用執(zhí)行時，才被分配臨時存儲空間。函空間。只有在被調用執(zhí)行時，才被分配臨時存儲空間。函數(shù)調用結束后，形式參數(shù)的內存空間將被操作系統(tǒng)立刻收數(shù)調用結束后，形式參數(shù)的內存空間將被操作系統(tǒng)立刻收回?；?。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）函數(shù)的參數(shù)函數(shù)的參數(shù)實際參數(shù)可以是任何符合形式參數(shù)類型的常量、變量、實際參數(shù)可以是任何符合形式參數(shù)類型的常量、變量、表達式。函數(shù)參數(shù)傳遞的過程就是實際參數(shù)和形式參數(shù)相表達式。函數(shù)參數(shù)傳遞的過程就是實際參數(shù)和形式參數(shù)相結合的過程，必須遵守三個一致。結合的過程，必須遵守三個一致。（1） 個數(shù)一致。個數(shù)一致。（2） 順序一致。順序一致。

24、（3） 類型一致。類型一致。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例1、打印字符、打印字符三角形三角形【問題描述問題描述】 編寫一個函數(shù)編寫一個函數(shù) print (n,ch)，表示打印一行，表示打印一行 n 個英文字母個英文字母 ch，并換，并換行。然后，在函數(shù)行。然后，在函數(shù) main() 中輸入中輸入 n 和和 ch，調用函數(shù)，調用函數(shù) print() 打印一個字打印一個字符三角形。符三角形?！据斎敫袷捷斎敫袷健恳恍幸粋€整數(shù)一行一個整數(shù) n 和一個英文字母和一個英文字母 ch，之間用一個空格隔開，之間用一個空格隔開，1n20?！据敵龈袷捷敵龈袷健縩 行，第

25、行，第 i 行有行有 i 個字母個字母 ch?！据斎霕永斎霕永? a【輸出樣例輸出樣例】aaaaaa高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-3-1#includeusing namespace std;void print(int i,char ch) for(int j = 1; j = i; j+) cout ch; cout n ch; for(int i = 1; i = n; i+) print(i,ch); return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）函數(shù)參數(shù)的傳遞方式函數(shù)參數(shù)的傳遞方式根據(jù)不同的

26、應用需求，函數(shù)參數(shù)的傳遞方式，或者說函根據(jù)不同的應用需求，函數(shù)參數(shù)的傳遞方式，或者說函數(shù)參數(shù)的調用方式分為三種：數(shù)參數(shù)的調用方式分為三種：（1） 傳值（調用）傳值（調用）：參見例參見例2；（2） 傳址（調用）傳址（調用）：參見例參見例3；（3） 引用（調用）引用（調用）：參見例參見例4、例、例5；高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例2、閱讀程序，寫出程序的運行結果，體會函數(shù)的傳值、閱讀程序，寫出程序的運行結果，體會函數(shù)的傳值(調用調用)。/p6-3-2#includeusing namespace std;void swap(int x,int y) in

27、t temp; temp = x; x = y; y = temp; cout x “ “ y endl; int main() int a = 10,b = 50; swap(a,b); cout a “ “ b endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例3、閱讀程序，寫出程序的運行結果，體會函數(shù)的傳址、閱讀程序，寫出程序的運行結果，體會函數(shù)的傳址(調調用用)。/p6-3-3#includeusing namespace std;void swap(int *x,int *y)/ 形式參數(shù)的類型定義為指針形式參數(shù)的類型定義為指針

28、int temp; temp = *x; *x = *y; *y = temp; cout *x “ “ *y endl;int main() int a = 10,b = 50; swap(&a,&b);/ 實際參數(shù)必須是地址實際參數(shù)必須是地址 cout a “ “ b endl; return 0 ;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例4、閱讀程序，寫出程序的運行結果，體會變量及其引用、閱讀程序，寫出程序的運行結果，體會變量及其引用的操作。的操作。/p6-3-4/#include using namespace std;int main

29、() int k = 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; int i = 100; k_adr += i; cout “ k= ” k “ k_adr= ” k_adr endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例5、閱讀程序，寫出程序的運行結果，體會函數(shù)的引用調用。、閱讀

30、程序，寫出程序的運行結果，體會函數(shù)的引用調用。/p6-3-5#includeusing namespace std;void swap(int &a,int &b) int temp; temp = a; a = b; b = temp; cout a “ “ b endl;int main() int a = 10,b = 50; swap(a,b); cout a “ “ b endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）實踐鞏固實踐鞏固高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）第第 4 課課

31、 變量的作用域變量的作用域學習目標學習目標1. 理解變量的作用域。理解變量的作用域。2. 熟練規(guī)范使用局部變量和全局變量。熟練規(guī)范使用局部變量和全局變量。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）變量的作用域變量的作用域變量按其在程序中的作用范圍，分為全局變量和局部變變量按其在程序中的作用范圍，分為全局變量和局部變量。量。全局變量是指定義在任何函數(shù)之外的變量，也就是不被全局變量是指定義在任何函數(shù)之外的變量，也就是不被任何任何“函數(shù)體函數(shù)體”所包含，可以被源文件中其他函數(shù)所所包含，可以被源文件中其他函數(shù)所共用，用靜態(tài)數(shù)據(jù)區(qū)存儲，作用域（有效范圍）是從定義共用，用靜態(tài)數(shù)

32、據(jù)區(qū)存儲，作用域（有效范圍）是從定義變量的位置開始到源文件（整個程序）結束。變量的位置開始到源文件（整個程序）結束。局部變量是指在一個函數(shù)（包括局部變量是指在一個函數(shù)（包括 main 函數(shù)）內部定義函數(shù)）內部定義的變量，它只在本函數(shù)內部有效，其他函數(shù)不能使用這些的變量，它只在本函數(shù)內部有效，其他函數(shù)不能使用這些變量，用動態(tài)數(shù)據(jù)區(qū)存儲，函數(shù)的參數(shù)也是局部變量。變量，用動態(tài)數(shù)據(jù)區(qū)存儲，函數(shù)的參數(shù)也是局部變量。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例1、以下程序中，哪些是全局變量，哪些是局部變量，并、以下程序中，哪些是全局變量，哪些是局部變量，并指出它們的作用域。指

33、出它們的作用域。int x,y;float a,b;float find(int c,d) float e,f; int i,j; int z;void doit() int main() int g,h; 高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例2、找出程序中的錯誤。如果去掉錯誤，程序輸出什么。、找出程序中的錯誤。如果去掉錯誤，程序輸出什么。/p6-4-2#includeusing namespace std;int f() int b = 0,c = 1; b = b + 1; c = c + 1; return (b+c);int main() for(

34、int i = 1; i 4; i+) cout i “ .sum= ” f() endl; cout “ b= ” b “ c= ” c endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+） C+允許在更多地方定義變量，例如允許在更多地方定義變量，例如for的第一個子句，的第一個子句，if、for或者或者while語句塊的語句塊的 內。這些變量只在當前語句塊內內。這些變量只在當前語句塊內有效。一個語句塊內只能定義一個同名變量。不同的函數(shù)內有效。一個語句塊內只能定義一個同名變量。不同的函數(shù)內部可以使用相同名稱的變量，它們代表不同的對象，相互獨部可

35、以使用相同名稱的變量，它們代表不同的對象，相互獨立，互不干擾。訪問同名變量時、只能訪問到當前有效、且立，互不干擾。訪問同名變量時、只能訪問到當前有效、且最近定義的該變量。特別地，在變量前加最近定義的該變量。特別地，在變量前加“:”可以指定訪問可以指定訪問全局變量。在寫復雜代碼時，可以利用這些特性，調整臨時全局變量。在寫復雜代碼時，可以利用這些特性，調整臨時變量的定義位置和作用域，以規(guī)避變量重名帶來的編譯錯誤變量的定義位置和作用域，以規(guī)避變量重名帶來的編譯錯誤。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例3、找出程序中的錯誤。如果去掉錯誤，程序輸出什么。、找出程序中

36、的錯誤。如果去掉錯誤，程序輸出什么。/p6-4-3#includeusing namespace std;int x = 233;int main() int x; cin x; for(int i = 1; i x y; cout x + y endl; cout x endl; cout :x endl; cout i “ “ y endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例4、閱讀程序，寫出程序的運行結果。、閱讀程序，寫出程序的運行結果。/p6-4-4#include using namespace std;int x = 10

37、, y = 15;void change(int a, int b, int x) int temp; x+;y+; temp = a;a = b;b = temp;int main() int a = 3, b = 5; cout x “ ” y “ ” a “ ” b endl; change(a,b,x); cout x “ ” y “ ” a “ ” b endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）實踐鞏固實踐鞏固高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）第第 5 課課 函數(shù)的遞歸調用函數(shù)的遞歸調用學習

38、目標學習目標1. 理解函數(shù)的遞歸調用。理解函數(shù)的遞歸調用。2. 應用遞歸法解決一些實際問題。應用遞歸法解決一些實際問題。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）函數(shù)的遞歸調用函數(shù)的遞歸調用函數(shù)調用自己，這種調用稱為函數(shù)調用自己，這種調用稱為“遞歸遞歸”調用，這樣的函調用，這樣的函數(shù)稱為數(shù)稱為“遞歸函數(shù)遞歸函數(shù)”。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例1、閱讀程序，寫出程序的運行結果。利用單步跟、閱讀程序，寫出程序的運行結果。利用單步跟蹤，體會函數(shù)遞歸調用執(zhí)行的過程。蹤，體會函數(shù)遞歸調用執(zhí)行的過程。/p6-5-1#includeu

39、sing namespace std;void p(int n) if(n 0) p(n-1); for(int i = 0; i n; i+) cout n; cout endl; int main() p(5); return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）遞歸的調用遞歸的調用一個問題要想用遞歸的方法（函數(shù)）來解決，必須要符一個問題要想用遞歸的方法（函數(shù)）來解決，必須要符合兩個條件。合兩個條件。（1） 可以把這個問題轉化成一個新問題，而新問題的可以把這個問題轉化成一個新問題，而新問題的解法和原問題的解法完全相同，只是問題規(guī)模變小了；解法和原問題的

40、解法完全相同，只是問題規(guī)模變小了；（2） 必須要有一個明確的遞歸結束條件（遞歸邊界）。必須要有一個明確的遞歸結束條件（遞歸邊界）。高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例2、求階乘、求階乘【問題描述問題描述】編程求編程求 n 階乘的值，階乘的值，n! = 123(n-1)n?！据斎敫袷捷斎敫袷健恳恍幸粋€正整數(shù)一行一個正整數(shù) n，1n20?！据敵龈袷捷敵龈袷健恳恍幸粋€正整數(shù)，表示一行一個正整數(shù)，表示 n! 的值。的值?！据斎霕永斎霕永?【輸出樣例輸出樣例】120高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）【問題分析問題分析】求求 n

41、! 的值帶有明顯的遞歸思想。要想求出的值帶有明顯的遞歸思想。要想求出 n!，就要先求，就要先求（n-1）!，因為（，因為（n-1）! 乘以乘以 n 就是就是 n!；而要求（；而要求（n-1）! 又又要先求出（要先求出（n-2）!，因為（，因為（n-2）！乘以（）！乘以（n-1）就是（）就是（n-1）!；要求要求 2! 又要先求出又要先求出 1!，因為，因為 2 乘以乘以 1 ！就是！就是 2!；而而 1 ！是已知的，就是！是已知的，就是 1。所以，階乘問題的遞歸公式為：。所以，階乘問題的遞歸公式為：高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-5-2#inclu

42、deusing namespace std;long long jc(int n) if(n = 1) return 1; / 遞歸邊界遞歸邊界 return jc(n-1) * n; / 遞歸公式遞歸公式int main() int n; cin n; cout jc(n) endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）求求 5 ！的遞歸調用過程如下！的遞歸調用過程如下:高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例3、求最大公約數(shù)、求最大公約數(shù)【問題描述問題描述】輸入兩個正整數(shù)輸入兩個正整數(shù) m 和和 n，求

43、它們的最大公約數(shù)。，求它們的最大公約數(shù)?！据斎敫袷捷斎敫袷健恳恍袃蓚€正整數(shù)一行兩個正整數(shù) m 和和 n，用一個空格隔開，用一個空格隔開，2m，n10000?！据敵龈袷捷敵龈袷健恳恍幸粋€正整數(shù)，表示一行一個正整數(shù)，表示 m 和和 n 的最大公約數(shù)。的最大公約數(shù)?！据斎霕永斎霕永?4 36【輸出樣例輸出樣例】12高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）【問題分析問題分析】用歐幾里得用歐幾里得“輾轉相除法輾轉相除法”演示求最大公約數(shù)的過程，發(fā)演示求最大公約數(shù)的過程，發(fā)現(xiàn)（現(xiàn)（m，n）的最大公約數(shù)與（）的最大公約數(shù)與（n，m % n）的最大公約數(shù)是）的最大公約數(shù)是一樣

44、的，但是數(shù)據(jù)規(guī)模變小了。所以，最大公約數(shù)問題的一樣的，但是數(shù)據(jù)規(guī)模變小了。所以，最大公約數(shù)問題的遞歸公式為：遞歸公式為：高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-5-3#includeusing namespace std;int gcd(int m,int n) if(n = 0) return m; else return gcd(n,m % n);int main() int m,n; cin m n; cout gcd(m,n) endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例4、分解質因子、分

45、解質因子【問題描述問題描述】輸入一個正整數(shù)輸入一個正整數(shù) n，用遞歸方法從小到大輸出它的所有質因，用遞歸方法從小到大輸出它的所有質因子（因子是質數(shù)）。子（因子是質數(shù)）?！据斎敫袷捷斎敫袷健恳恍幸粋€正整數(shù)一行一個正整數(shù) n，2n10000。【輸出格式輸出格式】一行若干個正整數(shù)，兩數(shù)之間用一個空格隔開，從小到大一行若干個正整數(shù)，兩數(shù)之間用一個空格隔開，從小到大輸出。輸出?！据斎霕永斎霕永?8【輸出樣例輸出樣例】2 3 3高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）【問題分析問題分析】顯然，如果顯然，如果 n 等于等于 1，就沒法再分解了。如果，就沒法再分解了。如果 n

46、 大于大于 1，從整，從整數(shù)數(shù) p（p 從從 2 開始）開始試除，如果能被開始）開始試除，如果能被 p 整除，就得到一個整除，就得到一個質因子質因子 p。問題就轉化成對于整數(shù)。問題就轉化成對于整數(shù) n/p，從，從 p 開始繼續(xù)分解質開始繼續(xù)分解質因子。因子。如果不能被如果不能被 p 整除，問題就轉化為對于整數(shù)整除，問題就轉化為對于整數(shù) n，從，從 p+1 開始分開始分解質因子。所以，遞歸公式為：解質因子。所以，遞歸公式為：高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）/p6-5-4#includeusing namespace std;bool first = true

47、;void zyz(int n,int p) if(n 1) if(n % p = 0) if(first) cout p; first = false; else cout “ “ n; zyz(n,2); cout endl; return 0;高等教育出版社高等教育出版社信息學奧賽課課通（信息學奧賽課課通（C+）例例5、抽獎、抽獎問題描述問題描述參見教材參見教材213頁。頁?！締栴}分析問題分析】我們已經學習過用循環(huán)語句實現(xiàn)我們已經學習過用循環(huán)語句實現(xiàn)“二分查找二分查找”，很明顯，很明顯，也可以采用也可以采用“遞歸遞歸”思想實現(xiàn)二分查找。思想實現(xiàn)二分查找。高等教育出版社高等教育出版社信息學

48、奧賽課課通（信息學奧賽課課通（C+）/p6-5-5#includeusing namespace std;int win,g101; int binsearch(int left,int right)if(left = right)int mid = (left + right) / 2;if(gmid = win) return mid;/找到找到if(win gmid) return binsearch(mid + 1,right);/在右半部分在右半部分else return 0;/沒找到沒找到 int main()int n,i,f,left,right,mid;scanf(%d,&n);for(i = 1; i win; f = binsearch(1,n); c