1、程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 1v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 2v函數(shù)是程序設(shè)計(jì)語言中最重要的部分，是模函數(shù)是程序設(shè)計(jì)語言中最重要的部分，是模塊化設(shè)計(jì)的主要工具。每一個(gè)塊化設(shè)計(jì)的主要工具。每一個(gè)c+程序都要用程序都要用到函數(shù)。到函數(shù)。v即使你自己不定義新的函數(shù)即使你自己不定義新的函數(shù)

2、, 在每一個(gè)完整的在每一個(gè)完整的c+程序中都必須有一個(gè)程序中都必須有一個(gè)main() 函數(shù)。函數(shù)。v在在c+語言中，字符處理、字符串處理和數(shù)學(xué)語言中，字符處理、字符串處理和數(shù)學(xué)計(jì)算都是用函數(shù)的方式提供的。計(jì)算都是用函數(shù)的方式提供的。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 3v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序

3、設(shè)計(jì) - 4v函數(shù)定義函數(shù)定義v函數(shù)的返回值：返回值類型應(yīng)與定義中的類型標(biāo)識(shí)符函數(shù)的返回值：返回值類型應(yīng)與定義中的類型標(biāo)識(shí)符一致。一致。c+的函數(shù)只能有一個(gè)返回值。的函數(shù)只能有一個(gè)返回值。v表示一個(gè)函數(shù)沒有返回值，類型標(biāo)識(shí)符用表示一個(gè)函數(shù)沒有返回值，類型標(biāo)識(shí)符用void。沒有。沒有返回值的函數(shù)也稱為過程返回值的函數(shù)也稱為過程 類型標(biāo)識(shí)符類型標(biāo)識(shí)符 函數(shù)名（形式參數(shù)表）函數(shù)名（形式參數(shù)表） 變量定義部分變量定義部分 語句部分語句部分 return 返回值；返回值； 或或 return（返回值）；（返回值）；eg. int max(int a, int b) if (ab) return(a) e

4、lse return(b); 函數(shù)體函數(shù)體程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 5v函數(shù)名是一個(gè)標(biāo)識(shí)符，符合標(biāo)識(shí)符命名函數(shù)名是一個(gè)標(biāo)識(shí)符，符合標(biāo)識(shí)符命名規(guī)范規(guī)范v函數(shù)名要有意義函數(shù)名要有意義v函數(shù)名一般是一個(gè)動(dòng)詞短語，表示函數(shù)函數(shù)名一般是一個(gè)動(dòng)詞短語，表示函數(shù)的行為的行為程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 6函數(shù)舉例函數(shù)舉例無參數(shù)、無返回值的函數(shù)無參數(shù)、無返回值的函數(shù) v打印一個(gè)由五行組成的三角形打印一個(gè)由五行組成的三角形 * * * * *void printstar() cout “ *n”; cout “ *n”; cout “ *n”; cout “ *n

5、”; cout “*n”;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 7函數(shù)舉例函數(shù)舉例有參數(shù)、無返回值的函數(shù)有參數(shù)、無返回值的函數(shù)v打印一個(gè)由打印一個(gè)由n行組成的三角形行組成的三角形void printstar(int numofline) int i , j; for (i = 1; i = numofline; +i) cout endl; for (j = 1; j = numofline - i; +j) cout ; for (j = 1; j = 2 * i - 1; +j) cout num; if (num = 1 & num = 10) return num

6、; 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 9函數(shù)舉例函數(shù)舉例有參數(shù)、有返回值的函數(shù)有參數(shù)、有返回值的函數(shù) v計(jì)算計(jì)算n! int p(int n) int s=1, i; if (n 0) return(0); for (i = 1; i = n; +i) s *= i; return(s); 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 10函數(shù)舉例函數(shù)舉例返回布爾量的函數(shù)返回布爾量的函數(shù)v判斷某一年是否為潤年的函數(shù)判斷某一年是否為潤年的函數(shù)bool isleapyear(int year) bool leapyear; leapyear = (year %4 = 0)

7、&(year % 100 != 0) | (year % 400 = 0); return (leapyear);程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 11v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 12v所有函數(shù)在使用前必須被聲明，以便讓編譯器知道所有函數(shù)在使用前必須被聲明，以便讓編譯器知道用戶

8、的用法是否正確。用戶的用法是否正確。v函數(shù)聲明包括下列內(nèi)容：函數(shù)聲明包括下列內(nèi)容：函數(shù)名函數(shù)名函數(shù)的參數(shù)類型函數(shù)的參數(shù)類型函數(shù)的返回類型函數(shù)的返回類型v函數(shù)的聲明被稱為函數(shù)的原型，它的形式為：函數(shù)的聲明被稱為函數(shù)的原型，它的形式為： 返回類型返回類型 函數(shù)名（參數(shù)表）；函數(shù)名（參數(shù)表）； 參數(shù)表中的每個(gè)參數(shù)說明可以是類型，也可以是類參數(shù)表中的每個(gè)參數(shù)說明可以是類型，也可以是類型后面再接一個(gè)參數(shù)名。如：型后面再接一個(gè)參數(shù)名。如： int max(int, int); int max(int a, int b);程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 13v庫函數(shù)在調(diào)用前需要庫函數(shù)在調(diào)

9、用前需要include相應(yīng)的頭文件。相應(yīng)的頭文件。v自定義的函數(shù)在調(diào)用時(shí)需要進(jìn)行函數(shù)原型說明。自定義的函數(shù)在調(diào)用時(shí)需要進(jìn)行函數(shù)原型說明。v函數(shù)原型說明與函數(shù)首部寫法上需要保持一致，函數(shù)原型說明與函數(shù)首部寫法上需要保持一致，即函數(shù)類型、函數(shù)名、參數(shù)個(gè)數(shù)和參數(shù)順序必即函數(shù)類型、函數(shù)名、參數(shù)個(gè)數(shù)和參數(shù)順序必須相同。須相同。v如果被調(diào)函數(shù)的定義在主調(diào)函數(shù)之前，可以不如果被調(diào)函數(shù)的定義在主調(diào)函數(shù)之前，可以不必加聲明。必加聲明。v如果在所有函數(shù)定義之前，在函數(shù)外部已經(jīng)做如果在所有函數(shù)定義之前，在函數(shù)外部已經(jīng)做了函數(shù)聲明，則在主調(diào)函數(shù)中無須再作聲明。了函數(shù)聲明，則在主調(diào)函數(shù)中無須再作聲明。程序設(shè)計(jì) cs.s

10、jtu 2011.9程序設(shè)計(jì) - 14#include int max(int a, int b); main() int x, y; cin x y; cout b) return(a); else return(b); 函數(shù)原型說明函數(shù)原型說明函數(shù)調(diào)用函數(shù)調(diào)用函數(shù)實(shí)現(xiàn)函數(shù)實(shí)現(xiàn)程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 15#include int max(int a, int b) if (a b) return(a); else return(b); main() int x, y; cin x y; cout x y; cout max(x, y);int p( int n )

11、 int s =1, i; if (n 0) return(0); for (i=1;in2? n1: n2); mainx(2)y(3)mainx(2)y(3)maxa(2)b(3)n1n2mainx(2)y(3)maxa(2)b(3)n1n2pn(2)simainx(2)y(3)maxa(2)b(3)n1(2)n2pn(3)simainx(2)y(3)maxa(2)b(3)n1(2)n2(6)mainx(2)y(3)程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 20v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)

12、函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模板函數(shù)模板v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 21v設(shè)計(jì)一函數(shù)，統(tǒng)計(jì)設(shè)計(jì)一函數(shù)，統(tǒng)計(jì)10位同學(xué)的平均成績位同學(xué)的平均成績v設(shè)計(jì)考慮：如何傳遞參數(shù)設(shè)計(jì)考慮：如何傳遞參數(shù)參數(shù)是參數(shù)是10位同學(xué)的考試成績，可以用位同學(xué)的考試成績，可以用10個(gè)整型個(gè)整型數(shù)來表示。所以有數(shù)來表示。所以有10個(gè)整型的形式參數(shù)個(gè)整型的形式參數(shù)一組同類數(shù)據(jù)可以用一個(gè)數(shù)組來描述，所以參一組同類數(shù)據(jù)可以用一個(gè)數(shù)組來描述，所以參數(shù)也可以是一個(gè)數(shù)也可以是一個(gè)10個(gè)元素的整型數(shù)組

13、個(gè)元素的整型數(shù)組第二種方法更加簡練第二種方法更加簡練返回值是平均成績返回值是平均成績程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 22int average(int array10) int i, sum = 0; for (i = 0; i 10; +i) sum += arrayi; return sum / 10; 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 23int main() int i, score10; cout 請(qǐng)輸入請(qǐng)輸入10個(gè)成績：個(gè)成績： endl; for ( i = 0; i scorei; cout 平均成績是：平均成績是： average(sco

14、re) endl; return 0; 注意：形式參數(shù)是注意：形式參數(shù)是數(shù)組，實(shí)際參數(shù)也數(shù)組，實(shí)際參數(shù)也是一個(gè)數(shù)組是一個(gè)數(shù)組程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 24v在函數(shù)在函數(shù)average的的return語句前增加一個(gè)對(duì)語句前增加一個(gè)對(duì)array3賦值的語句，如賦值的語句，如array3 = 90。v在在main函數(shù)的函數(shù)的average函數(shù)調(diào)用后，即函數(shù)調(diào)用后，即return語句前增加一個(gè)輸出語句前增加一個(gè)輸出score3的語句的語句v結(jié)果是什么？結(jié)果是什么？v你會(huì)發(fā)現(xiàn)輸出的值你會(huì)發(fā)現(xiàn)輸出的值90而不是而不是80。 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 25

15、vc+語言規(guī)定，數(shù)組名是數(shù)組的起始地址語言規(guī)定，數(shù)組名是數(shù)組的起始地址v參數(shù)傳遞時(shí)，實(shí)際參數(shù)是數(shù)組名，形式參數(shù)也是數(shù)參數(shù)傳遞時(shí)，實(shí)際參數(shù)是數(shù)組名，形式參數(shù)也是數(shù)組名組名v按照值傳遞，當(dāng)用實(shí)際參數(shù)按照值傳遞，當(dāng)用實(shí)際參數(shù)score調(diào)用函數(shù)調(diào)用函數(shù) average時(shí)，是用時(shí)，是用score 初始化形式參數(shù)數(shù)組初始化形式參數(shù)數(shù)組array。如。如 score 的首地址為的首地址為1000，在函數(shù)中形參數(shù)組，在函數(shù)中形參數(shù)組array的的首地址也為首地址也為1000。v形式參數(shù)和實(shí)際參數(shù)是同一數(shù)組！形式參數(shù)和實(shí)際參數(shù)是同一數(shù)組！程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 26v在函數(shù)中并沒有定

16、義新的數(shù)組在函數(shù)中并沒有定義新的數(shù)組v對(duì)形式參數(shù)數(shù)組指定規(guī)模是沒有意義的對(duì)形式參數(shù)數(shù)組指定規(guī)模是沒有意義的v形式參數(shù)數(shù)組不需要指定大小，所以方括號(hào)形式參數(shù)數(shù)組不需要指定大小，所以方括號(hào)中為空中為空v函數(shù)如何知道數(shù)組的規(guī)模？用另一個(gè)整型參函數(shù)如何知道數(shù)組的規(guī)模？用另一個(gè)整型參數(shù)表示數(shù)表示v總結(jié)：數(shù)組傳遞需要兩個(gè)參數(shù)，數(shù)組名和數(shù)總結(jié)：數(shù)組傳遞需要兩個(gè)參數(shù)，數(shù)組名和數(shù)組規(guī)模組規(guī)模程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 27v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版

17、v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 28v對(duì)于某些函數(shù)，程序往往會(huì)用一些固定的值去調(diào)用它對(duì)于某些函數(shù)，程序往往會(huì)用一些固定的值去調(diào)用它.例例如對(duì)于以某種數(shù)制輸出整型數(shù)的函數(shù)如對(duì)于以某種數(shù)制輸出整型數(shù)的函數(shù)print：void print(int value, int base);在大多數(shù)情況下都是以十進(jìn)制輸出，因此在大多數(shù)情況下都是以十進(jìn)制輸出，因此base的值總是的值總是為為10。 vc+在定義或聲明函數(shù)時(shí)可以為函數(shù)的某個(gè)參數(shù)指定默在定義或聲明函數(shù)時(shí)可以為函數(shù)的某個(gè)參數(shù)指定

18、默認(rèn)值。當(dāng)調(diào)用函數(shù)時(shí)沒有為它指定實(shí)際參數(shù)時(shí)，系統(tǒng)自認(rèn)值。當(dāng)調(diào)用函數(shù)時(shí)沒有為它指定實(shí)際參數(shù)時(shí)，系統(tǒng)自動(dòng)將默認(rèn)值賦給形式參數(shù)。例如，可以將動(dòng)將默認(rèn)值賦給形式參數(shù)。例如，可以將print函數(shù)聲明函數(shù)聲明為為 void print(int value, int base=10); 調(diào)用調(diào)用print(20) 等價(jià)于等價(jià)于 print(20, 10)程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 29 c+ c+在說明函數(shù)原型時(shí)，可以為一個(gè)或多個(gè)參在說明函數(shù)原型時(shí)，可以為一個(gè)或多個(gè)參數(shù)指定缺省值。調(diào)用此函數(shù)時(shí)，若缺省某一數(shù)指定缺省值。調(diào)用此函數(shù)時(shí)，若缺省某一參數(shù)，參數(shù)，c+c+自動(dòng)以缺省值作為此參數(shù)

19、的值。如：自動(dòng)以缺省值作為此參數(shù)的值。如： int special(int x=2, float y=1.5)int special(int x=2, float y=1.5) 調(diào)用時(shí)可用：調(diào)用時(shí)可用： special(5,3.2) /x=5; y=3.2special(5,3.2) /x=5; y=3.2 special(6) /x=6; y=1.5 special(6) /x=6; y=1.5 special( ) /x=2; y=1.5 special( ) /x=2; y=1.5程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 30v缺省參數(shù)無論有幾個(gè)，都必須放在參數(shù)序列缺省參數(shù)無論

20、有幾個(gè)，都必須放在參數(shù)序列的最后，的最后， 例如：例如：int savename (char int savename (char * *first, char first, char second = second = “”,char ,char * *third = third = “”, char , char * *fouth = fouth = “”););v在函數(shù)調(diào)用時(shí)，若某個(gè)參數(shù)省略，則其后的在函數(shù)調(diào)用時(shí)，若某個(gè)參數(shù)省略，則其后的參數(shù)皆應(yīng)省略而取其缺省值參數(shù)皆應(yīng)省略而取其缺省值程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 31v對(duì)參數(shù)默認(rèn)值的指定只有在函數(shù)聲明處有意義。對(duì)參

21、數(shù)默認(rèn)值的指定只有在函數(shù)聲明處有意義。因?yàn)楹瘮?shù)的默認(rèn)值是提供給調(diào)用者使用的。因?yàn)楹瘮?shù)的默認(rèn)值是提供給調(diào)用者使用的。v在不同的源文件中，可以對(duì)函數(shù)的參數(shù)指定不同在不同的源文件中，可以對(duì)函數(shù)的參數(shù)指定不同的默認(rèn)值。例如對(duì)于上面的的默認(rèn)值。例如對(duì)于上面的print函數(shù)，如果在某函數(shù)，如果在某一個(gè)功能模塊中輸出的大多是十進(jìn)制數(shù)，那么在一個(gè)功能模塊中輸出的大多是十進(jìn)制數(shù)，那么在此功能對(duì)應(yīng)的源文件中可以指定此功能對(duì)應(yīng)的源文件中可以指定base的默認(rèn)值為的默認(rèn)值為10。如果在另一個(gè)功能最模塊中經(jīng)常要以二進(jìn)制。如果在另一個(gè)功能最模塊中經(jīng)常要以二進(jìn)制輸出，那么在此功能模塊對(duì)應(yīng)的源文件中可以指輸出，那么在此功能模

22、塊對(duì)應(yīng)的源文件中可以指定默認(rèn)值是定默認(rèn)值是2。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 32v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 33v目的是為了提高執(zhí)行效率。目的是為了提高執(zhí)行效率。v對(duì)于任何內(nèi)聯(lián)函數(shù)，編譯器在符號(hào)表里放入函對(duì)于任何內(nèi)聯(lián)函數(shù)，編譯器在符號(hào)表里放入函數(shù)的聲明（包括名字、參數(shù)類型、返回值類

23、數(shù)的聲明（包括名字、參數(shù)類型、返回值類型）。如果編譯器沒有發(fā)現(xiàn)內(nèi)聯(lián)函數(shù)存在錯(cuò)誤，型）。如果編譯器沒有發(fā)現(xiàn)內(nèi)聯(lián)函數(shù)存在錯(cuò)誤，那么該函數(shù)的代碼也被放入符號(hào)表里。在調(diào)用那么該函數(shù)的代碼也被放入符號(hào)表里。在調(diào)用內(nèi)聯(lián)函數(shù)時(shí)，編譯器直接用內(nèi)聯(lián)函數(shù)的代碼替內(nèi)聯(lián)函數(shù)時(shí)，編譯器直接用內(nèi)聯(lián)函數(shù)的代碼替換函數(shù)調(diào)用，于是省去了函數(shù)調(diào)用的開銷。換函數(shù)調(diào)用，于是省去了函數(shù)調(diào)用的開銷。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 34v內(nèi)聯(lián)函數(shù)的定義：在函數(shù)頭部前加保留詞內(nèi)聯(lián)函數(shù)的定義：在函數(shù)頭部前加保留詞inline#includeinline float cube(float s) return s*s*s; i

24、nt main()float side;cin side;cout cube(side) endls;return 0; 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 35v內(nèi)聯(lián)以代碼復(fù)制內(nèi)聯(lián)以代碼復(fù)制(膨脹膨脹)為代價(jià)，省去了函數(shù)調(diào)為代價(jià)，省去了函數(shù)調(diào)用的開銷，提高函數(shù)的執(zhí)行效率。如果相比用的開銷，提高函數(shù)的執(zhí)行效率。如果相比于執(zhí)行函數(shù)體內(nèi)代碼的時(shí)間，函數(shù)調(diào)用的開于執(zhí)行函數(shù)體內(nèi)代碼的時(shí)間，函數(shù)調(diào)用的開銷可以忽略不計(jì)，那么效率的收獲會(huì)很小。銷可以忽略不計(jì)，那么效率的收獲會(huì)很小。v以下情況不宜用內(nèi)聯(lián)以下情況不宜用內(nèi)聯(lián):如果函數(shù)體內(nèi)的代碼比較長，使用內(nèi)聯(lián)將導(dǎo)如果函數(shù)體內(nèi)的代碼比較長，使用內(nèi)聯(lián)

25、將導(dǎo)致內(nèi)存消耗代價(jià)較高。致內(nèi)存消耗代價(jià)較高。如果函數(shù)體內(nèi)出現(xiàn)循環(huán)，那么執(zhí)行函數(shù)體內(nèi)如果函數(shù)體內(nèi)出現(xiàn)循環(huán)，那么執(zhí)行函數(shù)體內(nèi)代碼的時(shí)間要比函數(shù)調(diào)用的開銷大。代碼的時(shí)間要比函數(shù)調(diào)用的開銷大。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 36v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 37v在傳統(tǒng)的在傳統(tǒng)的c語言中，不允

26、許出現(xiàn)同名函數(shù)。當(dāng)要語言中，不允許出現(xiàn)同名函數(shù)。當(dāng)要求寫一組功能類似、參數(shù)類型或參數(shù)個(gè)數(shù)不同求寫一組功能類似、參數(shù)類型或參數(shù)個(gè)數(shù)不同的函數(shù)時(shí)，必須給它們?nèi)〔煌暮瘮?shù)名的函數(shù)時(shí)，必須給它們?nèi)〔煌暮瘮?shù)名 v例如某個(gè)程序要求找出一組數(shù)據(jù)中的最大值，例如某個(gè)程序要求找出一組數(shù)據(jù)中的最大值，這組數(shù)據(jù)最多有這組數(shù)據(jù)最多有5個(gè)數(shù)據(jù)。我們必須寫四個(gè)函數(shù)：個(gè)數(shù)據(jù)。我們必須寫四個(gè)函數(shù)：求兩個(gè)值中的最大值、求三個(gè)值中的最大值、求兩個(gè)值中的最大值、求三個(gè)值中的最大值、求四個(gè)值中的最大值和求五個(gè)值中的最大值。求四個(gè)值中的最大值和求五個(gè)值中的最大值。我們必須為這四個(gè)函數(shù)取四個(gè)不同的函數(shù)名，我們必須為這四個(gè)函數(shù)取四個(gè)不同

27、的函數(shù)名，例如：例如：max2, max3, max4和和max5。 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 38v使參數(shù)個(gè)數(shù)不同、參數(shù)類型不同或兩者兼使參數(shù)個(gè)數(shù)不同、參數(shù)類型不同或兩者兼而有之的兩個(gè)以上的函數(shù)取相同的函數(shù)名而有之的兩個(gè)以上的函數(shù)取相同的函數(shù)名 v如如int max(int a1, int a2);int max(int a1, int a2, int a3);int max(int a1, int a2, int a3, int a4);int max(int a1, int a2, int a3, int a4, int a5); 程序設(shè)計(jì) cs.sjtu 20

28、11.9程序設(shè)計(jì) - 39v由編譯器確定某一次函數(shù)調(diào)用到底是調(diào)用了哪一由編譯器確定某一次函數(shù)調(diào)用到底是調(diào)用了哪一個(gè)具體的函數(shù)。這個(gè)過程稱之為綁定（個(gè)具體的函數(shù)。這個(gè)過程稱之為綁定（binding，又稱為聯(lián)編或捆綁）。又稱為聯(lián)編或捆綁）。v編譯器首先會(huì)為這一組重載函數(shù)中的每個(gè)函數(shù)取編譯器首先會(huì)為這一組重載函數(shù)中的每個(gè)函數(shù)取一個(gè)不同的內(nèi)部名字。當(dāng)發(fā)生函數(shù)調(diào)用時(shí)，編譯一個(gè)不同的內(nèi)部名字。當(dāng)發(fā)生函數(shù)調(diào)用時(shí)，編譯器根據(jù)實(shí)際參數(shù)和形式參數(shù)的匹配情況確定具體器根據(jù)實(shí)際參數(shù)和形式參數(shù)的匹配情況確定具體調(diào)用的是那個(gè)函數(shù)，將這個(gè)函數(shù)的內(nèi)部函數(shù)名取調(diào)用的是那個(gè)函數(shù)，將這個(gè)函數(shù)的內(nèi)部函數(shù)名取代重載的函數(shù)名。代重載的函

29、數(shù)名。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 40v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 41v如果一組重載函數(shù)僅僅是參數(shù)的類型不一樣，程如果一組重載函數(shù)僅僅是參數(shù)的類型不一樣，程序的邏輯完全一樣，那么這一組重載函數(shù)可以寫序的邏輯完全一樣，那么這一組重載函數(shù)可以寫成一個(gè)函數(shù)模板。成一個(gè)函數(shù)模板。 v所謂

30、的函數(shù)模板就是實(shí)現(xiàn)類型的參數(shù)化（泛型所謂的函數(shù)模板就是實(shí)現(xiàn)類型的參數(shù)化（泛型化），即把函數(shù)中某些形式參數(shù)的類型定義成參化），即把函數(shù)中某些形式參數(shù)的類型定義成參數(shù)，稱為模板參數(shù)數(shù)，稱為模板參數(shù) v在函數(shù)調(diào)用時(shí)，編譯器根據(jù)實(shí)際參數(shù)的類型確定在函數(shù)調(diào)用時(shí)，編譯器根據(jù)實(shí)際參數(shù)的類型確定模板參數(shù)的值，生成不同的模板函數(shù)。模板參數(shù)的值，生成不同的模板函數(shù)。 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 42v一一 般的定義形式般的定義形式 template 返回類型返回類型 functionname(形式參數(shù)表形式參數(shù)表) /函數(shù)定義體函數(shù)定義體 v模板形式參數(shù)表可以包含基本數(shù)據(jù)類型，也可以包模板

31、形式參數(shù)表可以包含基本數(shù)據(jù)類型，也可以包含類類型（需加前綴含類類型（需加前綴class） template t max(t a, t b) return ab ? a : b；程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 43vmaxnum = max(3, 7);maxnum = max(3, 7);vmaxchar = max(maxchar = max(z z, , a a););vmaxdouble = max(3.5, 4.6);maxdouble = max(3.5, 4.6);v函數(shù)模板的實(shí)例化：函數(shù)模板的實(shí)例化：根據(jù)實(shí)際參數(shù)確定模板參數(shù)的值根據(jù)實(shí)際參數(shù)確定模板參數(shù)的值將模

32、板參數(shù)的值代入函數(shù)模板，形成一個(gè)真將模板參數(shù)的值代入函數(shù)模板，形成一個(gè)真正的函數(shù)正的函數(shù)程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 44v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 45v一個(gè)標(biāo)識(shí)符能被存一個(gè)標(biāo)識(shí)符能被存取的程序部分，稱取的程序部分，稱為標(biāo)識(shí)符的作用域?yàn)闃?biāo)識(shí)符的作用域v標(biāo)識(shí)符的作用域與標(biāo)識(shí)符的作用

33、域與程序塊有關(guān)。所謂程序塊有關(guān)。所謂的程序塊是帶有聲的程序塊是帶有聲明的復(fù)合語句明的復(fù)合語句v如右框中有兩塊如右框中有兩塊int main(void) int a = 2, b = 3; cout a b; int a = 4; cout a b; cout a b;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 46v在塊中說明的標(biāo)識(shí)符是在塊中說明的標(biāo)識(shí)符是局部局部的，僅能在本塊的，僅能在本塊中和內(nèi)部的塊中存取。中和內(nèi)部的塊中存取。v當(dāng)內(nèi)部塊與外部塊有同名標(biāo)識(shí)符時(shí)，在內(nèi)部當(dāng)內(nèi)部塊與外部塊有同名標(biāo)識(shí)符時(shí)，在內(nèi)部塊中屏蔽外部塊的同名標(biāo)識(shí)符。塊中屏蔽外部塊的同名標(biāo)識(shí)符。v在一個(gè)函數(shù)中，我們不能

34、存取主調(diào)程序的變?cè)谝粋€(gè)函數(shù)中，我們不能存取主調(diào)程序的變量，即使知道該變量的名字。量，即使知道該變量的名字。v函數(shù)參數(shù)對(duì)該函數(shù)也是局部的，可以將它看函數(shù)參數(shù)對(duì)該函數(shù)也是局部的，可以將它看成在塊內(nèi)，即函數(shù)體內(nèi)說明的說明的變量。成在塊內(nèi)，即函數(shù)體內(nèi)說明的說明的變量。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 47v局部變量：在塊內(nèi)定義的變量稱為局部變量，局部變量：在塊內(nèi)定義的變量稱為局部變量，即使是即使是main函數(shù)中定義的變量也是局部的。函數(shù)中定義的變量也是局部的。v全局變量：在所有的函數(shù)外面定義的變量稱為全局變量：在所有的函數(shù)外面定義的變量稱為全局變量全局變量作用范圍：從定義位置到文件結(jié)

35、束。如在作用范圍作用范圍：從定義位置到文件結(jié)束。如在作用范圍外的函數(shù)要使用此變量，用關(guān)鍵詞外的函數(shù)要使用此變量，用關(guān)鍵詞extern在函數(shù)內(nèi)說在函數(shù)內(nèi)說明此全局變量。明此全局變量。作用：方便函數(shù)間的數(shù)據(jù)傳遞作用：方便函數(shù)間的數(shù)據(jù)傳遞v請(qǐng)寫出下列程序的執(zhí)行結(jié)果：請(qǐng)寫出下列程序的執(zhí)行結(jié)果：程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 48int p = 1, q = 5， r=3;int f1() int p = 3, r = 2; q=p+q+r; cout “f1: p,q,r=“ p q r; int f2() p=p+q+r; cout “f2: p,q,r=“ p q r p q

36、r; int f3() int q; r = 2*r; q=r+p; cout “f3: p,q,r=“ p q r; main()f3(); cout “after f3: p,q,r=” p q r p q r; f1(); cout “after f1: p,q,r=“ p q r; f2(); cout “after f2: p,q,r=” p q r p q r; 結(jié)果：結(jié)果： f3: p,q,r=1 7 6 after f3: p,q,r=1 5 6 f1: p,q,r=3 10 2 after f1:p,q,r=1 10 6 f2: p,q,r=17 10 6 after f2:

37、 p,q,r=17 10 6 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 49v全局變量破壞了模塊化，建議盡量少使全局變量破壞了模塊化，建議盡量少使用用v當(dāng)全局變量和局部變量同名時(shí)，在局部當(dāng)全局變量和局部變量同名時(shí)，在局部變量的作用范圍中全局變量被屏蔽。變量的作用范圍中全局變量被屏蔽。v全局變量的使用將在模塊化設(shè)計(jì)中詳細(xì)全局變量的使用將在模塊化設(shè)計(jì)中詳細(xì)介紹介紹程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 50v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變

38、量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 51v在在c+語言中，每個(gè)變量有兩個(gè)屬性：語言中，每個(gè)變量有兩個(gè)屬性：類型：變量所存儲(chǔ)的數(shù)據(jù)類型類型：變量所存儲(chǔ)的數(shù)據(jù)類型存儲(chǔ)類型：變量所存儲(chǔ)的區(qū)域：存儲(chǔ)類型：變量所存儲(chǔ)的區(qū)域：v標(biāo)準(zhǔn)的變量定義：標(biāo)準(zhǔn)的變量定義：存儲(chǔ)類型存儲(chǔ)類型 數(shù)據(jù)類型數(shù)據(jù)類型 變量名；變量名；v存儲(chǔ)類型：存儲(chǔ)類型：自動(dòng)變量：自動(dòng)變量：auto寄存器變量：寄存器變量：register外部變量：外部變量：extern靜態(tài)變量：靜態(tài)變量：static程序設(shè)計(jì) cs.sjtu 20

39、11.9程序設(shè)計(jì) - 52v在函數(shù)內(nèi)或塊內(nèi)定義的變量缺省時(shí)是在函數(shù)內(nèi)或塊內(nèi)定義的變量缺省時(shí)是auto。如。如auto int i；v當(dāng)進(jìn)入塊時(shí)，系統(tǒng)為自動(dòng)變量分配空間。當(dāng)進(jìn)入塊時(shí)，系統(tǒng)為自動(dòng)變量分配空間。當(dāng)退出塊時(shí)，系統(tǒng)釋放分配給自動(dòng)變量當(dāng)退出塊時(shí)，系統(tǒng)釋放分配給自動(dòng)變量的值。因此自動(dòng)變量的值就消失了。當(dāng)?shù)闹?。因此自?dòng)變量的值就消失了。當(dāng)再次進(jìn)入該塊時(shí)，系統(tǒng)重新分配空間。再次進(jìn)入該塊時(shí)，系統(tǒng)重新分配空間。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 53v存儲(chǔ)在寄存器中，代替自動(dòng)變量或形參，存儲(chǔ)在寄存器中，代替自動(dòng)變量或形參，可以提高變量的訪問速度?？梢蕴岣咦兞康脑L問速度。v如無合適的寄

40、存器可用，則編譯器把它如無合適的寄存器可用，則編譯器把它設(shè)為自動(dòng)變量。設(shè)為自動(dòng)變量。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 54v聲明一個(gè)不在本模塊作用范圍內(nèi)的全局變量。如：聲明一個(gè)不在本模塊作用范圍內(nèi)的全局變量。如： extern int num; num為一個(gè)的全局變量。為一個(gè)的全局變量。v用途：用途：在某函數(shù)中引用了一個(gè)聲明在本函數(shù)后的全局變量時(shí)，在某函數(shù)中引用了一個(gè)聲明在本函數(shù)后的全局變量時(shí)，需要在函數(shù)內(nèi)用需要在函數(shù)內(nèi)用extern聲明此全局變量。聲明此全局變量。當(dāng)一個(gè)程序有多個(gè)源文件組成時(shí)，用當(dāng)一個(gè)程序有多個(gè)源文件組成時(shí)，用extern可引用另一可引用另一文件中的全局變量

41、。文件中的全局變量。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 55/file1.cpp#include using namespace std;void f();extern int x; /外部變量的聲明外部變量的聲明int main() f(); cout in main(): x= “ x endl; return 0;/file2.cpp#include using namespace std;int x; /全局變量的定義全局變量的定義void f() cout in f(): x= “ x endl; 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 56v為在整個(gè)程序

42、的運(yùn)行期間都存在的變量為在整個(gè)程序的運(yùn)行期間都存在的變量限定訪問范圍。限定訪問范圍。v兩類靜態(tài)變量：兩類靜態(tài)變量：靜態(tài)的局部變量靜態(tài)的局部變量靜態(tài)的外部變量靜態(tài)的外部變量程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 57v允許局部允許局部變量保存變量保存它的原有它的原有值，以便值，以便在次進(jìn)入在次進(jìn)入塊時(shí)還可塊時(shí)還可以使用此以使用此值。值。eg. int f(int a) int b=0; static int c=3; b=b+1; c=c+1; return(a+b+c); void main() int a=2,i; for (i=0; i3; +i) cout f(a); 運(yùn)行結(jié)

43、果為：運(yùn)行結(jié)果為：7 8 9 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 58v用用static說明的全局變量其他源文件不能說明的全局變量其他源文件不能用用extern引用它引用它v用用extern還可以用在函數(shù)定義或說明中。還可以用在函數(shù)定義或說明中。該函數(shù)只能被用于本源文件中，其他源該函數(shù)只能被用于本源文件中，其他源文件不能調(diào)用此函數(shù)。文件不能調(diào)用此函數(shù)。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 59v未被程序員初始化的靜態(tài)變量都由系統(tǒng)初未被程序員初始化的靜態(tài)變量都由系統(tǒng)初始化為始化為0。v局部靜態(tài)變量的初值是編譯時(shí)賦的。當(dāng)運(yùn)局部靜態(tài)變量的初值是編譯時(shí)賦的。當(dāng)運(yùn)行時(shí)重復(fù)調(diào)

44、用此函數(shù)時(shí)，不重復(fù)賦初值。行時(shí)重復(fù)調(diào)用此函數(shù)時(shí)，不重復(fù)賦初值。v雖然局部靜態(tài)變量在函數(shù)調(diào)用結(jié)束后仍然雖然局部靜態(tài)變量在函數(shù)調(diào)用結(jié)束后仍然存在，但其他函數(shù)不能引用它。存在，但其他函數(shù)不能引用它。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 60void a();void b();void c();void d();main() int x=6; cout “x in main is “ x endl; a(); b(); c(); d(x); x+; a(); b(); c(); d(x); cout “x in main is ” x endl; void a()int x=25; co

45、ut “x in a is ” x endl; void b()static int x=50; cout “x in b is ” x+ endl; void c() extern int x; x*=10; cout “x in c is ” x endl; int x=2; void d(int x) cout “x in d is ” +x endl; 結(jié)果：結(jié)果： x in main is 6 x in a is 25 x in b is 50 x in c is 20 x in d is 7 x in a is 25 x in b is 51 x in c 200 x in d i

46、s 8 x in main is 7 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 61v函數(shù)函數(shù)v自己編寫函數(shù)自己編寫函數(shù)v函數(shù)的使用函數(shù)的使用v數(shù)組作為參數(shù)數(shù)組作為參數(shù)v帶默認(rèn)值的函數(shù)帶默認(rèn)值的函數(shù)v內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)v重載函數(shù)重載函數(shù)v函數(shù)模版函數(shù)模版v變量的作用域變量的作用域v變量的存儲(chǔ)類別變量的存儲(chǔ)類別v遞歸函數(shù)遞歸函數(shù)v基于遞歸的算法基于遞歸的算法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 62v遞歸程序設(shè)計(jì)：將一個(gè)大問題簡化為遞歸程序設(shè)計(jì)：將一個(gè)大問題簡化為同樣形同樣形式式的較小問題。的較小問題。在一個(gè)遞歸求解中，分解的子問題與最初的問題在一個(gè)遞歸求解中，分解的子問題

47、與最初的問題具有一樣的形式具有一樣的形式 作為處理問題的工具，遞歸技術(shù)是一種非常有力作為處理問題的工具，遞歸技術(shù)是一種非常有力的工具。利用遞歸不但可以使得書寫復(fù)雜度降低，的工具。利用遞歸不但可以使得書寫復(fù)雜度降低，而且使程序看上去更加美觀而且使程序看上去更加美觀v遞歸調(diào)用：在一個(gè)函數(shù)中直接或間接地調(diào)用遞歸調(diào)用：在一個(gè)函數(shù)中直接或間接地調(diào)用函數(shù)本身函數(shù)本身程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 63v必須有遞歸終止的條件必須有遞歸終止的條件 v函數(shù)有與遞歸終止條件相關(guān)的參數(shù)函數(shù)有與遞歸終止條件相關(guān)的參數(shù)v在遞歸過程中，決定終止條件的參數(shù)有在遞歸過程中，決定終止條件的參數(shù)有規(guī)略地遞增或

48、遞減規(guī)略地遞增或遞減 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 64v有可對(duì)函數(shù)的入口進(jìn)行測試的基本情況有可對(duì)函數(shù)的入口進(jìn)行測試的基本情況 if (條件條件) return (不需要遞歸的簡單答案不需要遞歸的簡單答案);else return (遞歸調(diào)用同一函數(shù)遞歸調(diào)用同一函數(shù))；基本情況基本情況程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 65n!=1*2*3*4*(n-1)*n(n-1)!遞歸形式：遞歸形式：其他)!1(*01!nnnn遞歸終止條件遞歸終止條件long p(int n) if (n = 0) return 1; else return n * p(n-1);

49、 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 66int raiseinttopower(int n, int k) if (k = 0) return(1); else return( n * raiseinttopower( n, k - 1); 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 67fibonacci函數(shù)函數(shù)00112132435568其他)2() 1(1100)(nfnfnnnfint f(int n)if (n=0) return 0; elseif (n=1) return 1; else return (f(n-1)+f(n-2); 程序設(shè)計(jì) cs.sj

50、tu 2011.9程序設(shè)計(jì) - 68v問題：求解問題：求解n! 可以用循環(huán)的方法，即從可以用循環(huán)的方法，即從1開始，乘開始，乘2，再，再乘乘3-.一直乘到一直乘到n。這種方法容易理解，。這種方法容易理解，也容易實(shí)現(xiàn)也容易實(shí)現(xiàn)由于由于n! = n (n-1)!(n-1)! 數(shù)學(xué)里定義數(shù)學(xué)里定義0！1，從而從而n!可以用下面的遞歸公式表示：可以用下面的遞歸公式表示：) 1()!1() 1 , 0(1!nnnnn程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 69 int p(int n) if(n= = 0) return (1); else return (n * p(n-1);程序設(shè)計(jì) c

51、s.sjtu 2011.9程序設(shè)計(jì) - 70求求p(4) 1)0(*1)1(*2)2(*3)3(*4)4(ppppp遞歸過程回溯程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 71遞歸與迭代的選擇遞歸與迭代的選擇v對(duì)于大多數(shù)常用的遞歸都有簡單、等價(jià)對(duì)于大多數(shù)常用的遞歸都有簡單、等價(jià)的迭代程序。究竟使用哪一種，憑你的的迭代程序。究竟使用哪一種，憑你的經(jīng)驗(yàn)選擇。經(jīng)驗(yàn)選擇。v迭代程序復(fù)雜，但效率高。迭代程序復(fù)雜，但效率高。v遞歸程序邏輯清晰，但往往效率較低。遞歸程序邏輯清晰，但往往效率較低。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 72fibonacci函數(shù)的遞歸實(shí)現(xiàn)函數(shù)的遞歸實(shí)現(xiàn)in

52、t f(int n)if (n=0) return 0; elseif (n=1) return 1; else return (f(n-1)+f(n-2); v實(shí)現(xiàn)效率分析：消費(fèi)的時(shí)間是災(zāi)難性的！實(shí)現(xiàn)效率分析：消費(fèi)的時(shí)間是災(zāi)難性的！程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 73fibonacci函數(shù)的迭代實(shí)現(xiàn)函數(shù)的迭代實(shí)現(xiàn)int f(int n) int i, fn, fn_1 = 0, fn_2 = 1; if (n = 0) return 0; if (n = 1) return 1; for ( i = 2; i=n; +i) fn = fn_1 + fn_2; fn_2 =

53、 fn_1; fn_1 = fn; return fn;消耗的時(shí)間：執(zhí)消耗的時(shí)間：執(zhí)行行n n次加法和次加法和3n3n次次賦值！賦值！程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 74系統(tǒng)考慮系統(tǒng)考慮 對(duì)遞歸函數(shù)的每次調(diào)用都需要內(nèi)存空間。對(duì)遞歸函數(shù)的每次調(diào)用都需要內(nèi)存空間。由于很多調(diào)用的活動(dòng)都是同時(shí)進(jìn)行的，操由于很多調(diào)用的活動(dòng)都是同時(shí)進(jìn)行的，操作系統(tǒng)可能會(huì)耗盡可用的內(nèi)存作系統(tǒng)可能會(huì)耗盡可用的內(nèi)存,避免在處理避免在處理過大的過大的n時(shí)產(chǎn)生溢出問題。時(shí)產(chǎn)生溢出問題。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 75v數(shù)字旋轉(zhuǎn)方陣如右數(shù)字旋轉(zhuǎn)方陣如右圖所示。編程輸出圖所示。編程輸出任意任

54、意n*n的蛇陣。的蛇陣。120 19 18 17 16221 32 31 30 15322 33 36 29 14423 34 35 28 13524 25 26 27 12678910 11程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 76v先填最外圈，然后再填內(nèi)部內(nèi)部的填法同上。先填最外圈，然后再填內(nèi)部內(nèi)部的填法同上。也是先填最外圈，再填內(nèi)部。也是先填最外圈，再填內(nèi)部。v根據(jù)上述思想，可以設(shè)計(jì)一個(gè)遞歸函數(shù)根據(jù)上述思想，可以設(shè)計(jì)一個(gè)遞歸函數(shù)fill。該。該函數(shù)先填外圈，然后遞歸調(diào)用自己填內(nèi)部。函數(shù)先填外圈，然后遞歸調(diào)用自己填內(nèi)部。v函數(shù)原型：函數(shù)原型： void fill(int nu

55、mber, int begin, int size) number：表示要填入的起始數(shù)據(jù)：表示要填入的起始數(shù)據(jù) begin：表示要填的起始位置：表示要填的起始位置 size：蛇陣的規(guī)模：蛇陣的規(guī)模v要生成一個(gè)要生成一個(gè)6*6的蛇陣只要調(diào)用：的蛇陣只要調(diào)用：fill(1,0,6)程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 77int p2020;void fill(int, int,int);int main() int row, col, size; cout size; fill(1,0,size); for (row = 0; row size; +row) cout endl;

56、for (col = 0; col size; +col) cout prowcol t; return 0;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 78v自上而下填最左列自上而下填最左列v自左而右填最下行自左而右填最下行v自下而上填最右列自下而上填最右列v自右而左填最上行自右而左填最上行v遞歸調(diào)用遞歸調(diào)用fill，規(guī)模減，規(guī)模減2，起始位置為原，起始位置為原來的下一行下一列，填入的起始數(shù)字為來的下一行下一列，填入的起始數(shù)字為填入一圈后的第一個(gè)數(shù)字。填入一圈后的第一個(gè)數(shù)字。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 79void fill( int number, int

57、begin, int size) int i, row = begin, col = begin; if (size = 0) return; if (size = 1) pbeginbegin = number; return; prowcol = number; +number; for (i=0; isize-1; +i) +row; prowcol = number; +number; for (i=0; isize-1; +i) +col; prowcol = number; +number; for (i=0; isize-1; +i) -row; prowcol = number

58、; +number; for (i=0; isize-2; +i) -col; prowcol = number; +number; fill( number, begin+1, size-2 );程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 80目標(biāo)：將a上的盤子全部移到b上規(guī)則：每次只能移動(dòng)一個(gè)盤子不允許大盤子放在小盤子上 a b c程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 81vn4（最開始的情況）（最開始的情況） n4（完成情（完成情況）況）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 82v第第1步：從開始的桿到輔助桿（步：從開始的桿到輔助桿（src到到aux）

59、v第第2步：從開始桿到目的桿（步：從開始桿到目的桿（src到到dst）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 83v第第3步：從輔助桿到目的桿（步：從輔助桿到目的桿（aux到到dst）v第第4步：從開始的桿到輔助桿（步：從開始的桿到輔助桿（src到到aux）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 84v第第5步：從目的桿到開始桿（步：從目的桿到開始桿（ dst 到到src）v第第6步：從目的桿到輔助桿（步：從目的桿到輔助桿（dst到到aux）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 85v第第7步：從開始桿到目的桿（步：從開始桿到目的桿（ src 到到dst

60、）v第第8步：從開始桿到目的桿（步：從開始桿到目的桿（src到到dst）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 86v第第9步：從輔助桿到目的桿（步：從輔助桿到目的桿（ aux 到到dst ）v第第10步：從輔助桿到開始的桿（步：從輔助桿到開始的桿（aux到到src ）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 87v第第11步：從目的桿到開始桿（步：從目的桿到開始桿（ dst 到到src）v第第12步：從輔助桿到目的桿（步：從輔助桿到目的桿（ aux 到到dst ）程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 88v第第13步：從開始的桿到輔助桿（步：從開始的桿到輔助桿（src到到