Chapter 3 – Functions 函式 目標 能夠明白如何利用一些函式、用模組化的方式建立程式 能夠建立新的函式

Presentation on theme: "Chapter 3 – Functions 函式 目標 能夠明白如何利用一些函式、用模組化的方式建立程式 能夠建立新的函式"— Presentation transcript:

1 Chapter 3 – Functions 函式 目標 能夠明白如何利用一些函式、用模組化的方式建立程式 能夠建立新的函式
了解在函式之間傳遞訊息的機制 介紹隨機產生亂數的模擬技術 了解如何將識別字的適用範圍限定在程式的特定區域 了解如何撰寫、使用函式去呼叫自己的方法(遞迴涵式)

2 Chapter 3 - Functions Outline 大綱 3.1 簡介 3.2 C++ 程式中的元件 3.3 數學程式庫的函式
3.1 簡介 3.2 C++ 程式中的元件 3.3 數學程式庫的函式 3.4 函式 3.5 函式的定義 3.6 函式的原型 3.7 標頭檔 3.8 亂數的產生 3.9 範例：一個機率的遊戲和介紹 enum 的用法 3.10 儲存類別 3.11 定義範圍的原則 3.12 遞迴的觀念 3.13 遞迴觀念的範例：Fibonacci 數列 3.14 遞迴與迭代 3.15 沒有參數列的函式

3 Chapter 3 - Functions Outline 大綱 3.16 行內函式
3.16 行內函式 3.17 參照及參照參數 3.18 預設的引數 單元範圍解析運算子 3.20 函式的重載 函式樣板 3.22 (選讀性的範例研究)物件的探索：辨識類別的屬性

4 3.1 Introduction Divide and conquer
一般有用的程式都比我們前面看過的範例長，研發和維護大程式最好的方法就是利用較小的元件來建構。 每個元件都比原來的大程式容易管理 平常計劃、管理最好也用這種方法。

5 C++ 的程式由下列元件構成 函式可以被其他涵式呼叫 3.2 C++ 程式中的元件 C++ 標準程式庫裡的函式(類別)
程式設計者自己設計的函式(類別) 標準程式庫裡面提供了豐富的函式 儘量熟悉、利用標準程式庫裡面的函式，可增快速度、增加可攜性。 函式可以被其他涵式呼叫 用函式呼叫的方式讓某個函式執行指定的工作。呼叫函式必須寫出函式名稱、並提供需要的引數(argument) 就像老闆對員工一樣： 老闆(呼叫別人的函式)要求員工(被呼叫的函式)執行某件工作、作完後要向老闆報告(傳回)結果

6 3.2 C++ 程式中的元件 函式定義 老闆 員工2 員工3 員工1 員工4 員工5 只需要寫一次，可以在許多地方被呼叫很多次。
函式裡面的敘述式對別的函式是隱藏的 就像老闆對員工一樣： 老闆不知道員工如何作好所交代的工作，只要知道該件工作被完成了。 老闆 員工2 員工3 員工1 員工4 員工5

7 呼叫 sqrt (平方根) 函式. 前面的敘述式會印出 30
3.3 數學程式庫的函式 數學程式庫的函式 可以讓程式設計者執行某些常見的數學計算 要使用數學程式庫的函式時，必須引入標頭檔 <cmath> 函式呼叫的方法： functionName (argument) 範例： cout << sqrt( ); 呼叫 sqrt (平方根) 函式. 前面的敘述式會印出 30 sqrt 函式需要一個 double 的引數(argument)其傳回值的型態也是 double，所以數學程式庫的函式傳回值型態都是 double。

8 3.3 數學程式庫的函式 函式的引數可以是 常見的程式設計錯誤 3.1
3.3 數學程式庫的函式 函式的引數可以是 常數 sqrt( ); 變數 sqrt( x ); 運算式 sqrt( sqrt( x ) ) ; sqrt( 3 – 6*x ); 常見的程式設計錯誤 3.1 忘了先引入數學標頭檔就直接使用數學程式庫中的函式，這是一種語法錯誤。若要在程式中使用標準程式庫中的函式，必須引入標準程式庫的標頭檔。

9 3.3 數學程式庫的函式 ceil(x) ceil(9.2) 是 10.0 cos(x) cos(0.0) 是 1.0 exp(x)
3.3 數學程式庫的函式 ceil(x) ceil(9.2) 是 10.0 cos(x) cos(0.0) 是 1.0 exp(x) exp(1.0) 是 fabs(x) fabs(-8.76) 是 8.76 floor(x) floor(9.2) 是 9.0 fmod(x,y) fmod(13.657, 2.333)是1.992 log(x) log( ) 是 1.0 log10(x) log10(10.0) 是 1.0 pow(x,y) pow(2,7) 是 128 sin(x) sin(0.0) 是 0 sqrt(x) sqrt(900.0) 是 30.0 tan(x) tan(0.0) 是 0 x除 y 的餘數，商數是整數

10 區域變數(Local variables)
3.4 函式 函式 讓程式設計者用模組化的方式撰寫程式 區域變數(Local variables) 只能在所定義的函式中使用(知道)的變數 在函式定義中宣告的變數都是區域變數 參數(Parameters) 在參數列裡面定義的變數 也是區域變數 此函式被呼叫時，呼叫者提供資料進來時使用的變數 將程式寫成函式化的好處： 容易管理 增加軟體的重複使用性(software reusability) 避免程式碼的重複

11 3.4 函式 軟體工程的觀點 3.3-3.5 一個程式中包含許多 函式，main 應該寫成呼叫一群函式的敘述，以便執行程式中的許多工作。
3.4 函式 軟體工程的觀點 一個程式中包含許多 函式，main 應該寫成呼叫一群函式的敘述，以便執行程式中的許多工作。 每個函式必須限制只執行單獨一項經過嚴密定義的工作，而且函式的名稱要有效的表達出該項工作的內容。這樣可以提昇軟體的重複使用性。 當無法找到某函式適當、簡單的名稱時，可能表示你的函式執行太多不同的工作。最好將這樣的函式再分成幾個比較型的函式。

12 3.5 函式定義 我們建立的函式作的事情包括： 函式定義的格式： 範例： 拿到傳進函式的資料 Take in data
3.5 函式定義 我們建立的函式作的事情包括： 拿到傳進函式的資料 Take in data 執行運算 Perform operations 傳回結果 Return the result 函式定義的格式： return-value-type function-name( parameter-list ) { declarations and statements } 範例： int square( int y) { return y * y; }

13 1. Function prototype 2. Loop Function definition Program Output
1 // Fig. 3.3: fig03_03.cpp 2 // Creating and using a programmer-defined function 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 int square( int ); // function prototype 函式原型 9 10 int main() 11 { 12 for ( int x = 1; x <= 10; x++ ) cout << square( x ) << " "; 14 15 cout << endl; 16 return 0; 17 } 18 19 // Function definition 函式定義 20 int square( int y ) 21 { 22 return y * y; 23 } 1. Function prototype 2. Loop Function definition Program Output 注意這裡如何宣告參數與傳回值型態

14 Function definition Program Output
// Fig. 3.4: fig03_04.cpp // Finding the maximum of three floating-point numbers. #include <iostream> …… double maximum( double, double, double ); // function prototype 10 11 int main() 12 { double number1; double number2; double number3; 16 cout << "Enter three floating-point numbers: "; cin >> number1 >> number2 >> number3; 19 // number1, number2 and number3 are arguments to // the maximum function call cout << "Maximum is: " << maximum( number1, number2, number3 ) << endl; return 0; 27 } Function definition Program Output fig03_04.cpp (1 of 2) Function maximum takes 3 arguments (all double) and returns a double.

15 1. Function prototype (3 parameters) 2. Input values 2.1 Call function
29 // function maximum definition; 30 // x, y and z are parameters 31 double maximum( double x, double y, double z ) 32 { double max = x; // assume x is largest 34 if ( y > max ) // if y is larger, max = y; // assign y to max 37 if ( z > max ) // if z is larger, max = z; // assign z to max return max; 43 } Comma separated list for multiple parameters. 1. Function prototype (3 parameters) 2. Input values 2.1 Call function Enter three floating-point numbers: Maximum is: 99.32 Enter three floating-point numbers: Maximum is: 3.333 Enter three floating-point numbers: Maximum is: 88.99

16 常見的程式設計錯誤 若函式需要傳回值，但是定義中忘記傳回值，也是語法錯誤。 傳回值型態宣告為 void 又傳回一個值，也是語法錯誤。 相同型態的參數不可一起宣告，如 float x, y，必須宣告為 float x, float y，宣告為 float x, y 編譯器會產生錯誤訊息，每個參數的型態都必須宣告。 函式定義右小括號後面多加了分號，會產生語法錯誤。 函式定義中將函式參數宣告為變數，會產生語法錯誤。 將函數定義寫在另一個函數裡面，會產生語法錯誤。 若函數原型、函式標頭與函式呼叫，三者對於使用引數和參數的個數、型別與順序不完全相同，以及傳回值型態有不相合的情形時，都屬於語法錯誤。

17 良好的程式設計習慣 避免將傳入函數的引數與相對應的參數取成相同的名字，以免混淆。 在函式定義前後加上空白行，可增加程式的可讀性。 選擇有意義的函式名稱與參數名稱可增強程式的可讀性。 軟體工程的觀點 函式的長度最好不要超過一個視窗。無論函式多長，都應該只作一件工作；短的函式可增進軟體的重複使用性。 程式應該寫成簡短函式的集合，這會使程式更容易撰寫、除錯、維護以及修改。 一個函式若需要很多參數，可能表示此函式執行太多工作，應考慮將此函式分成幾個小函式；函式的標頭應保持在一行以內。

18 函式原型 Function prototype
3.6 函式原型 函式原型 Function prototype 函式名稱 參數型態 傳進函數的 傳回值型態 函式傳回呼叫它之值的型態(預設型態是 int) void 代表此函式不傳回任何值 只有在函式定義出現在此函式呼叫的後面時才需要寫 範例： double maximum(double, double, double); 傳入三個 double 的參數 傳回一個 double 的結果

19 Promotion rules 型別提昇原則
Coercion of arguments 對引數的強制規定 將引數傳入函式時，會將引數轉換成函式原型中所定義的型態。例 sqrt(4)  sqrt(4.0)  2.0。 Mixed-type expressions 當不同型態的資料出現在同一個運算式時，compiler 會將資料自動轉換成相同的資料型態，而且是轉換成較「高等」的資料型能。 要將資料轉換成較「低等」的型態可能會造成資料錯誤的情形，所以 compiler 不會自動作，只能用 assignment 或是用 cast operator.

20 型別提昇原則 long double Double Float unsigned long int long int
unsigned int int unsigned short int short int unsigned char char bool

21 軟體工程觀點 C++ 裡函式原型是必須的。使用 #include 前置處理器指令，從適當程式庫的標頭檔取得標準程式庫中的函式原型。您和您的群組成員所使用到的函式，也可以使用 #include 取得包含有這些函式原型的標頭檔。 常見的程式設計錯誤 忘記以分號作為函式原型的結尾，這是語法錯誤。 若函式呼叫的格式與函式原型不符，即是語法錯誤。 若函式原型和函式定義不相符，亦為語法錯誤。

22 19章 preprocessor 有較詳細介紹。
3.7 標頭檔 Header Files 標頭檔 Header files 包含程庫中函式的函式原型。 例如：<cstdlib> ,<cmath>,<iostream>,<iomanip>… 用此方式載入 #include <filename> 範例： #include <cmath> 程式設計者也可以自訂標頭檔 檔名型式必須是： filename.h 載入方式如右　　#include "filename.h“ 19章 preprocessor 有較詳細介紹。

23 3.7 標頭檔 Header Files cmath: math.h cstdio: stdio.h cstdlib: stdlib.h cstring: string.h ctime: time.h iostream: iostream.h iomanip: iomanip.h

24 3.8 亂數的產生 rand 函式 srand 函式 載入 <cstdlib>
3.8 亂數的產生 rand 函式 i = rand(); 載入 <cstdlib> 產生一個 0 到 RAND_MAX(通常是32767) 的虛擬亂數 虛擬亂數是事先設定好的一系列 虛擬亂數是一系列事先設定好的「亂數」 程式每次執行時會產生相同系列的亂數 srand 函式 產生一個亂數的種子位置 srand( seed ); srand( time( 0 ) ); //must include <ctime> time( 0 ) 以秒數表示目前系統的時間 因為程式的執行時間每次不同，所以每次執行時 rand 可產生不同的亂數

25 3.8 亂數的產生 調整比例(Scaling) 調整亂數到某一特定的範圍(例如：0-1、1-6、1-56、…) 餘數運算子 ( % ) 範例
3.8 亂數的產生 調整比例(Scaling) 調整亂數到某一特定的範圍(例如：0-1、1-6、1-56、…) 餘數運算子 ( % ) 將亂數由 0 到 RAND_MAX 之間調整到 a 到 a + b – 1 之間。 範例 i = rand() % 6 + 1; 可產生 1 到 6 之間的亂數 n = a + rand() % b; 產生 a~a+b-1 之間的亂數。

26 1. Define loop Output random number Program Output
#include <iostream> …… #include <iomanip> 10 using std::setw; 12 #include <cstdlib> // contains function prototype for rand 14 int main() 15 { // loop 20 times for ( int counter = 1; counter <= 20; counter++ ) { // pick random number from 1 to 6 and output it cout << setw( 10 ) << ( 1 + rand() % 6 ); 21 // if counter divisible by 5, begin new line of output if ( counter % 5 == 0 ) cout << endl; } // end for structure return 0; 30 } 1. Define loop Output random number Program Output fig03_07.cpp (1 of 2) Output of rand() scaled and shifted to be a number between 1 and 6. Executing the program again gives the same "random" dice rolls.

27 3.8 亂數的產生 Next Program to show distribution of rand()
3.8 亂數的產生 Next Program to show distribution of rand() Simulate 6000 rolls of a die Print number of 1’s, 2’s, 3’s, etc. rolled Should be roughly 1000 of each

28 // Fig. 3.8: fig03_08.cpp // Roll a six-sided die 6000 times. #include <iostream> …… #include <iomanip> 9 10 using std::setw; 11 12 #include <cstdlib> // contains function prototype for rand 13 14 int main() 15 { int frequency1 = 0; int frequency2 = 0; int frequency3 = 0; int frequency4 = 0; int frequency5 = 0; int frequency6 = 0; int face; // represents one roll of the die 23 1. Initialize seed 2. Input value for seed 2.1 Use srand to change random sequence 2.2 Define Loop 3. Generate and output random numbers

29 25 for ( int roll = 1; roll <= 6000; roll++ ) {
face = 1 + rand() % 6; // random number from 1 to 6 // determine face value and increment appropriate counter switch ( face ) { case 1: // rolled 1 frequency1; break; case 2: // rolled 2 frequency2; break; case 3: // rolled 3 frequency3; break; case 4: // rolled 4 frequency4; break; case 5: // rolled 5 frequency5; break; case 6: // rolled 6 frequency6; break; 1. Initialize seed 2. Input value for seed 2.1 Use srand to change random sequence 2.2 Define Loop 3. Generate and output random numbers

30 55 default: // invalid value
cout << "Program should never get here!"; } } cout << "Face" << setw( 13 ) << "Frequency" << "\n 1" << setw( 13 ) << frequency1 << "\n 2" << setw( 13 ) << frequency2 << "\n 3" << setw( 13 ) << frequency3 << "\n 4" << setw( 13 ) << frequency4 << "\n 5" << setw( 13 ) << frequency5 << "\n 6" << setw( 13 ) << frequency6 << endl; return 0; 73 } Default case included even though it should never be reached. This is a matter of good coding style 1. Initialize seed 2. Input value for seed 2.1 Use srand to change random sequence 2.2 Define Loop 3. Generate and output random numbers Face Frequency

31 2.1 Use srand to change random sequence
1 // Fig. 3.9: fig03_09.cpp 2 // Randomizing die-rolling program 3 #include <iostream> 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 #include <iomanip> 10 11 using std::setw; 12 13 #include <cstdlib> 14 15 int main() 16 { 17 unsigned seed; 18 19 cout << "Enter seed: "; 20 cin >> seed; 21 srand( seed ); 22 23 for ( int i = 1; i <= 10; i++ ) { cout << setw( 10 ) << 1 + rand() % 6; 25 if ( i % 5 == 0 ) cout << endl; 28 } 29 30 return 0; 31 } 1. Initialize seed 2. Input value for seed 2.1 Use srand to change random sequence 2.2 Define Loop 3. Generate and output random numbers

32 Enter seed: 67 Enter seed: 432

33 3.9 範例：一個機率的遊戲和介紹 enum 的用法
列示 Enumeration – 用識別字代表的整數集合 enum typeName {constant1, constant2…}; 每個識別字都是常數，從 0(預設) 開始、每次增加 1 每個常數名稱必須惟一。 Example: enum Status {CONTINUE, WON, LOST}; 建立一個列示型態為 typeName 的示列變數 將非列示常數的值存進列示變數中會造成語法錯誤。 Status enumVar; // create variable enumVar = WON; // set equal to WON enumVar = 1; // ERROR

34 3.9 範例：一個機率的遊戲和介紹 enum 的用法
列示常數的值可以設定，例如： enum Months { JAN = 1, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV, DEC}; 由 1 開始，每次增加 1 for(j = JAN; j <= DEC;j++)//j 是 int Craps 模擬器的規則 擲兩個骰子 第一次：7 或 11 玩家贏 第一次：2, 3 或 12 玩家輸 第一次：4, 5, 6, 8, 9, 10 這個值就成為玩家的「點數」 繼續擲骰子，先擲出玩家的「點數」就贏，但若先擲出 7 點就輸。

35 1.1 Initialize variables and enum
1 // Fig. 3.10: fig03_10.cpp 2 // Craps 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 #include <cstdlib> 9 10 #include <ctime> 11 12 using std::time; // 這一行應該要刪掉 13 14 int rollDice( void ); // function prototype 15 16 int main() 17 { 18 enum Status { CONTINUE, WON, LOST }; 19 int sum, myPoint; 20 Status gameStatus; 21 22 srand( time( 0 ) ); 23 sum = rollDice(); // first roll of the dice 24 25 switch ( sum ) { case 7: case 11: // win on first roll gameStatus = WON; break; case 2: case 3: case 12: // lose on first roll gameStatus = LOST; break; 1. rollDice prototype 1.1 Initialize variables and enum 1.2 Seed srand 2. Define switch statement for win/loss/continue Notice how the enum is defined

36 2.1 Define loop to continue playing 2.2 Print win/loss
default: // remember point gameStatus = CONTINUE; myPoint = sum; cout << "Point is " << myPoint << endl; break; // optional 40 } 41 42 while ( gameStatus == CONTINUE ) { // keep rolling sum = rollDice(); 44 if ( sum == myPoint ) // win by making point gameStatus = WON; else if ( sum == 7 ) // lose by rolling 7 gameStatus = LOST; 50 } 51 52 if ( gameStatus == WON ) cout << "Player wins" << endl; 54 else cout << "Player loses" << endl; 56 57 return 0; 58 } 59 2.1 Define loop to continue playing 2.2 Print win/loss

37 3. Define rollDice function Program Output
60 int rollDice( void ) 61 { 62 int die1, die2, workSum; 63 64 die1 = 1 + rand() % 6; 65 die2 = 1 + rand() % 6; 66 workSum = die1 + die2; 67 cout << "Player rolled " << die1 << " + " << die2 << " = " << workSum << endl; 69 70 return workSum; 71 } 3. Define rollDice function Program Output Player rolled = 11 Player wins Player rolled = 10 Point is 10 Player rolled = 6 Player rolled = 6 Player rolled = 10 Player rolled = 4 Point is 4 Player rolled = 5 Player rolled = 9 Player rolled = 9 Player rolled = 3 Player rolled = 7 Player loses

38 良好的程式設計習慣 3.5~3.7 使用者自己定義的型態名稱最好用大寫當開頭。 Enumeration constants 的名稱最好都用大寫，這樣比較容易一眼就看出它們不是一般的變數。 用 enumeration 來代替整數常數，程式比較清楚。

39 儲存類別指定字: auto, register, extern, static, mutable(21章才討論)
3.10 儲存類別 Storage Classes 儲存類別指定字: auto, register, extern, static, mutable(21章才討論) 儲存類別：影響識別字存在記憶體的時期 範圍scope：哪些敘述可以使用該識別字 連結linkage：識別字在哪裡宣告(多個 source files) 兩種儲存類別:automatic(自動) 與 static(靜態) 自動儲存類別(Automatic storage) 在同個區段(block)中建立與消滅 auto 區域變數(local variable)的預設指定字。範例： auto float x, y; register 嘗試將變數放在高速的暫存器中 區域變數或參數才能如此宣告

40 靜態儲存類別(Static storage)
3.10 儲存類別 Storage Classes 靜態儲存類別(Static storage) 此種變數在程式一開始執行就存在 static 函式中的區域變數可作此定義 在函式結束時仍保持其值 此種變數仍只有該函式能使用 extern 全域變數和函式名稱預設值 任何函式都可使用此種變數

41 3.10 儲存類別 Storage Classes 增進效能的小技巧 3.2-3.4
自動儲存類別是一種節省記憶體的辦法(不需再使用的變數就不佔記憶體位置) 用暫存器來存變數的執行速度比較快。 現在的編譯器可以自動判斷該將哪些變數放在暫存器中。 軟體工程的觀點 自動儲存符合最小開放權限原則(the principle of least privilege) Global variable 在使用上比較容易出錯，儘量避免。 只在某個涵數裡面用到的變數，儘量宣告成區域變數。 常見錯誤 3.18 將多個儲存類別指定字用在一個識別字上是語法錯誤。

42 3.11 識別字範圍原則 Identifier Scope Rules
檔案範圍File scope 定義在函式外面，從宣告處到檔案結束，任何函式都可使用 例如：全域變數、函式定義、函式原型 函式範圍 Function scope 只在同一個函式內可以參照使用 只有標記(start:, case:, etc.) 是函式範圍 區段範圍 Block scope 宣告在區段中的變數，範圍：宣告處開始，到區段結束 (})。 函式中的變數與函式的參數(parameters) 外層區段相同名稱的變數在內層會被「隱藏」起來。 函式原型範圍 Function prototype scope 在函式原型中參數列中使用的識別字 此名稱在函式原型中可以不用，在任何其他地方可重複使用

43 12 int x = 1; //global variable, file scope
14 int main(){ int x = 5; //local variable, block scope { int x = 7; //local variable cout << x << endl; } 41 } 44 void useLocal( void ){ int x = 25; //local variable cout << x << endl; x; cout << x << endl; 54 } 59 void useStaticLocal( void ) 60 { static int x = 50; //static local variable cout << x << endl; x; cout << x << endl; 70 } 73 void useGlobal( void ) 74 { cout << x << endl; x *= 10; cout << x << endl; 81 }

44 1.1 Initialize global variable
1 // Fig. 3.12: fig03_12.cpp 2 // A scoping example 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 void a( void ); // function prototype 9 void b( void ); // function prototype 10 void c( void ); // function prototype 11 12 int x = 1; // global variable 13 14 int main() 15 { 16 int x = 5; // local variable to main 17 18 cout << "local x in outer scope of main is " << x << endl; 19 20 { // start new scope int x = 7; 22 cout << "local x in inner scope of main is " << x << endl; 24 } // end new scope 25 26 cout << "local x in outer scope of main is " << x << endl; 27 28 a(); // a has automatic local x 29 b(); // b has static local x 30 c(); // c uses global x 31 a(); // a reinitializes automatic local x 32 b(); // static local x retains its previous value 33 c(); // global x also retains its value 34 1. Function prototypes 1.1 Initialize global variable 1.2 Initialize local variable 1.3 Initialize local variable in block 2. Call functions 3. Output results x is different inside and outside the block. local x in outer scope of main is 5 local x in inner scope of main is 7

45 Local static variables are not destroyed when the function ends.
35 cout << "local x in main is " << x << endl; 36 37 return 0; 38 } 39 40 void a( void ) 41 { 42 int x = 25; // initialized each time a is called 43 44 cout << endl << "local x in a is " << x << " after entering a" << endl; x; 47 cout << "local x in a is " << x << " before exiting a" << endl; 49 } 50 51 void b( void ) 52 { static int x = 50; // Static initialization only // first time b is called. cout << endl << "local static x is " << x << " on entering b" << endl; x; cout << "local static x is " << x << " on exiting b" << endl; 60 } 61 62 void c( void ) 63 { 64 cout << endl << "global x is " << x << " on entering c" << endl; 66 x *= 10; 67 cout << "global x is " << x << " on exiting c" << endl; 68 } Local automatic variables are created and destroyed each time a is called. 3.1 Define Functions local x in a is 25 after entering a local x in a is 26 before exiting a Local static variables are not destroyed when the function ends. local static x is 50 on entering b local static x is 51 on exiting b Global variables are always accessible. Function c references the global x. global x is 1 on entering c global x is 10 on exiting c

46 Program Output local x in outer scope of main is 5
local x in inner scope of main is 7 local x in a is 25 after entering a local x in a is 26 before exiting a local static x is 50 on entering b local static x is 51 on exiting b global x is 1 on entering c global x is 10 on exiting c local static x is 51 on entering b local static x is 52 on exiting b global x is 10 on entering c global x is 100 on exiting c local x in main is 5 Program Output

47 3.11 識別字範圍原則 Identifier Scope Rules
常見的程式設計錯誤 3.19 已在外層區段中使用的識別字，若不小心在內層區段中又誤用了相同名稱作為識別字，但是程式設計者的原意是在程式執行內層區段時，希望外層區段的識別字仍然有效，這就形成邏輯錯誤。 良好的程式設計習慣 3.8 避免在內層範圍所使用的變數名稱掩蓋住外層範圍中相同名稱的識別字，這只要避免在程式中使用相同名稱的識別字即可作到。

48 遞迴函式 Recursive functions
3.12 遞迴 Recursion 遞迴函式 Recursive functions 可以呼叫自己的函式 只解決基本的情形(base case) 若不是 base case, 函式就將問題分解成比較小的問題、愈分愈小， 程式會愈來愈接近 base case。 通常呼叫自己的部份都放在 return statement 裡面 最後用較小問題的答案組合出較大問題的答案 呼叫自己的部份會有重複執行的效果、base case 是停止執行的部份。

49 3.12 遞迴 Recursion 範例：factorial 階乘 遞迴關係 ( n! = n * ( n – 1 )! )
n! = n * ( n – 1 ) * ( n – 2 ) * … * 1 遞迴關係 ( n! = n * ( n – 1 )! ) 5! = 5 * 4! 4! = 4 * 3!… 基本情形 base case (1! = 0! = 1) 5! 5*4! 120 4*3! 24 3*2! 6 2*1! 2 1

50 //Fig. 3.14: fig03_14.cpp //Recursive factorial function #include <iostream> using std::cout; using std::endl; #include <iomanip> using std::setw; unsigned long factorial (unsigned long); int main() { for (int i = 0; i <= 10;i++) cout << setw(2) << i << “! = “ << factorial(i) << endl; return 0; } //Recursive definition of function factorial unsigned long factorial(unsigned long number) { if(number <= 1) return 1; else return number * factorial (number – 1); 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 10! =

51 3.12 遞迴 Recursion unsigned long, unsigned long int 無號數 常見程式設計錯誤 忘記從遞迴函式中傳回值(在有需要的情形)，大部份的編譯器都會產生警告訊息。 若忽略了基本處理狀況(base case)，或者遞迴步驟不正確，則遞迴動作最後並不會收斂到基本狀況，這就會造成「無窮」遞迴，最後導至記憶體耗盡而當機。這有點類似迭代(iterative)的無窮迴圈情形。當輸入非預期的數值時，也會造成無窮遞迴的情形。

52 3.13 使用遞迴觀念的範例：Fibonacci 數列
每個數都是前兩個數字的和 遞迴公式的例子： fib(n) = fib(n-1) + fib(n-2) 用 C++ 所寫的 fibonacci 函式 long fibonacci( long n ) { if ( n == 0 || n == 1 ) // base case return n; else return fibonacci( n - 1 ) + fibonacci( n – 2 ); } 成長比例約 1.618…， 會收斂到golden ratio

53 3.13 使用遞迴觀念的範例：Fibonacci 數列
Fibonnaci 函式的呼叫圖 f(4) return f(3) + f(2) 3 return f(2) + f(1) 2 return f(1) + f(0) 1 return f(1) + f(0) return 1 return 1 return 0 1 return 1 return 0

54 2.1 Call function fibonacci
1 // Fig. 3.15: fig03_15.cpp 2 // Recursive fibonacci function 3 #include <iostream> 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 unsigned long fibonacci( unsigned long ); 10 11 int main() 12 { unsigned long result, number; 14 cout << "Enter an integer: "; cin >> number; result = fibonacci( number ); cout << "Fibonacci(" << number << ") = " << result << endl; return 0; 20 } 21 22 // Recursive definition of function fibonacci 23 unsigned long fibonacci( unsigned long n ) 24 { 25 if ( n == 0 || n == 1 ) // base case return n; 27 else // recursive case return fibonacci( n - 1 ) + fibonacci( n - 2 ); 29 } 1. Function prototype 1.1 Initialize variables 2. Input an integer 2.1 Call function fibonacci 2.2 Output results. 3. Define fibonacci recursively Only the base cases return values. All other cases call the fibonacci function again.

55 2n,這種 exponential time 的程式 執行速度會比較慢，也比較浪 費記憶體。
Enter an integer: 0 Fibonacci(0) = 0 這個程式會呼叫自己的次數是 2n,這種 exponential time 的程式 執行速度會比較慢，也比較浪 費記憶體。 Enter an integer: 1 Fibonacci(1) = 1 Program Output Enter an integer: 2 Fibonacci(2) = 1 Enter an integer: 3 Fibonacci(3) = 2 Enter an integer: 4 Fibonacci(4) = 3 Enter an integer: 5 Fibonacci(5) = 5 Enter an integer: 10 Fibonacci(10) = 55 要如何設計速度比較快的程式， 這是「演算法」(algorithms) 討論 的問題。 Enter an integer: 6 Fibonacci(6) = 8 Enter an integer: 20 Fibonacci(20) = 6765 Enter an integer: 30 Fibonacci(30) = Enter an integer: 35 Fibonacci(35) = Ex 3.41 用非遞迴的方式寫出計算 Fibonacci number 的程式。

56 3.13 使用遞迴觀念的範例：Fibonacci 數列
C++ 沒有定義 operands 的執行順序，我們通常習慣的順序是左邊先作，但實際上也可能是右邊先作，compiler 可自由決定。Visual C++ 是左邊先作 運算元的執行順序通常不會影響運算結果，但如果涵數有 side-effect 的話，不同的執行順序結果就可能不同。 C++ 中只有四種 operators 有規定運算元的執行順序，分別是：&& || , ?: 前三者都是左邊先作，最後一個是三元運算，第一個運算元先作，再用其結果決定要作哪一個運算元。 如果您程式的執行結果會因為運算元的執行順序而有不同的結果的話，那您的程式可能在不同的系統上會產生不同的結果，會造成 portability 性質比較差。

57 兩者都可以達到重複執行的效果，哪一種作法比較好呢？ 重複執行的原理
3.14 遞迴與迭代(iteration) 兩者都可以達到重複執行的效果，哪一種作法比較好呢？ 重複執行的原理 迭代：使用迴圈(loop) 遞迴：重複地遞迴函式呼叫 終止執行的方式 迭代：迴圈條件不成立 遞迴：遇到基本狀況(base case) 兩者都可能發生無窮迴圈的情形 在執行效率(iteration)與好的軟體工程(recursion)間取得平衡

58 軟體工程的觀點 任何用遞迴方式解決的問題都可以用非遞迴方式解決。某些問題選擇用遞迴方式解決的原因是：用遞迴可以較自然地表示問題與答案，這樣也會較容易了解和除錯。 另外，若無法很明顯地找出迭代的解法時，也可能選擇使用遞迴的方式。 將程式儘量函式化，用工整且階層化的方式可促進軟體工程的提昇，只是必須付出執行效率上的代價。 增進效能的小技巧 3.6-7 在注重執行效率的情形下，避免使用遞迴，遞迴呼叫要花更多時間與記憶體。 高度函式化的程式執行速度比較慢，需要較大的記憶體，但比較容易編寫、測試、除錯、維護與改進。 常見程式設計錯誤 3.22 不小心使非遞迴函式呼叫自己，無論直接或間接都是邏輯錯誤。

59 此書中遞迴的例子 第3章：階乘函式、Fibonacci 函式、最大公因數、兩個整數和、兩整數相乘、某整數的指數次方、Tower of Hanoi, 將輸入數字倒著輸出、視覺化遞迴 第4章：陣列元素加總、列印陣列、反向列印陣列、反向列印字串、檢查字串是否為迴文、陣列中的最小值、選擇排序法、八皇后、線性搜尋、二元搜尋 第5章：快速排序法、迷宮訪問、反向輸出鍵盤輸入之字串 第17章：插入鏈結串列、刪除鏈結串列、搜尋鏈結串列、反向印出鏈結串列、插入二元樹、二元樹的前序(中序、後序)走訪

60 3.15 含有空置參數列的函式 要宣告函式是空白參數的方式有二 將函式後面的括號中寫上 void 或留空白
3.15 含有空置參數列的函式 要宣告函式是空白參數的方式有二 將函式後面的括號中寫上 void 或留空白 void print(); 或 void print( void ); 上面的函式 print 沒有引數、也沒有傳回值

61 1. Function prototypes (take no arguments)
1 // Fig. 3.18: fig03_18.cpp 2 // Functions that take no arguments 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 void function1(); 9 void function2( void ); 10 11 int main() 12 { 13 function1(); 14 function2(); 15 16 return 0; 17 } 18 19 void function1() 20 { 21 cout << "function1 takes no arguments" << endl; 22 } 23 24 void function2( void ) 25 { 26 cout << "function2 also takes no arguments" << endl; 27 } 1. Function prototypes (take no arguments) 2. Call the functions Function definitions Program Output Notice the two ways of declaring no arguments. function1 takes no arguments function2 also takes no arguments

62 可攜性的小技巧 3.3 C++ 的空白參數列所代表的意義和在 C 裡是不相同的。在 C 裡，空白參數列代表取消所有引數的檢查(就是呼叫該函式時，可以傳遞任何的引數)，而在 C++ 裡，卻代表該函式不需要任何引數。因此，用到這個特性的 C 程式若以 C++ 來編譯將產生語法錯誤。 常見的程式設計錯誤 3.23 除非程式中的每個函式都提供了函式原型，或者每個函式在被叫用前都已經加以定義，否則 C++ 不會進行編譯工作。

63 3.16 行內函式 inline function inline functions 行內函式 Example: 可降函式呼叫的時間損耗
告訴編譯器，在呼叫行內函式的地方、產生一個函式的程式碼來取代函式呼叫 編譯器可以忽略 inline 應該用在小的、常常被呼叫、內容很少修改的函式 Example: inline double cube( const double s ) { return s * s * s; }

64 //Fig. 3.19: fig03_19.cpp //Using an inline function to calculate the volume of a cube #include <iostream> using std::cout; using std::endl; using std::cin; inline double cube (const double s) {return s * s * s;} int main() { cout << “Enter the side length of your cube: “; double side; cin >> side; cout << “Volume of cube with side “ << side << “ is “ << cube(side) << endl; return 0; } Enter the side length of your cube: 3.5 Volume of cube with side 3.5 is

65 軟體工程的觀點 對行內函式所做的任何修改，會造成所有呼叫此函式的程式需要重新編譯，對程式的發展、維護影響很大。 很多程式設計者並不關心是否將參數宣告成 const, 就算被呼叫的函式不應該修改所傳入的引數。關鍵字 const 只保護傳進函式中的參數、而不保護原來的引數。 好的程式設計習慣 3.9 修飾字 inline 應只用於程式碼很小、常使用、不常修改的函式。 增進效能的小技巧 3.8 使用行內(inline) 函式可減少程式執行時間，但會增加程式碼的大小。

66 3.17 參照及參照參數 References and Reference Parameters
Call by value 傳值呼叫 將資料複製到函式裡面去 改變參數不會改變原始的引數 可避免不必要的副作用(side effects) Call by reference 傳參考值呼叫 被呼叫的函式可以直接取存外面的引數 改數參數內容會影響到原始的引數 Reference parameter 參照參數是引數的別名 & 用來表示參照 void change( int &variable ) { variable += 3; } 將 3 加到外面的引數裡面去 int y = &x. 改變 y 將同時改變 x ，兩者存取相同位置

67 4 #include <iostream>
int squareByValue( int ); // function prototype 10 void squareByReference( int & ); // function prototype main() { int x = 2; int z = 4; 16 cout << "x = " << x << " before squareByValue\n"; cout << "Value returned by squareByValue: " << squareByValue( x ) << endl; cout << "x = " << x << " after squareByValue\n" << endl; 23 cout << "z = " << z << " before squareByReference" << endl; squareByReference( z ); cout << "z = " << z << " after squareByReference" << endl; return 0; 29 } 33 int squareByValue( int number ) 34 { return number *= number; // caller's argument not modified 37 } 38 42 void squareByReference( int &numberRef ) 43 { numberRef *= numberRef; // caller's argument modified 46 } Notice the & operator, indicating pass-by-reference. 2 x 2 number 16 z 4 z numberRef 4 number

68 3.1 Function Definition of squareByReference Program Output
x = 2 before squareByValue Value returned by squareByValue: 4 x = 2 after squareByValue z = 4 before squareByReference z = 16 after squareByReference 3.1 Function Definition of squareByReference Program Output

69 增進效能的小技巧 傳值呼叫的缺點之一，就是若要傳送大量的資料，光是複製那些資料就會耗費可觀的執行時間。 傳參考呼叫可避免複製大量資料的額外時間消耗，使程式執行更有效率。 軟體工程的觀點 3.18 傳參考呼叫會降低程式的安全性，因為被呼叫的函式可能會破壞呼叫者的資料。 常見的程式設計錯誤 3.24 因為參照型態的參數使用時只要寫變數名稱，程式設計者可能會誤以為這時傳值呼叫的參數。若不小心改變此參數內容，可能會產生不可預期的結果。

70 3.17 參照及參照參數 References and Reference Parameters
當要傳很大量資料的時候，可以用 call-by-reference 的方式，再將參數用 const 來限制。這樣不僅時間比較快，而且可以達到安全的效果。 在傳參照參數時，可用 int& cref 代替 int &cref。 Reference 也可以成為其他變數的 alias，例如： int count = 1; int &cref = count; //cref 成為 count 的別名、同一位置 ++cref; //將 count 值增加1。 Reference 變數在宣告時一定要作 initialize。 cref 1 counter

71 沒有作 initialize 的話，syntax error
//Fig. 3.21: fig03_21.cpp //References must be initialized #include <iostream> using std::cout; using std::endl; int main() { int x = 3, &y = x; //y 是 x 的 alias，指同一個位置。 cout << “x = “ << x << endl << “y = “ << y << endl; y = 7; return 0; } 沒有作 initialize 的話，syntax error y 3 x x = 3 y = 3 x = 7 y = 7

72 常見的程式設計錯誤 參照變數宣告時沒有設定初值的話，就是語法錯誤。 嘗試將一個已宣告的參照變數重新指定成另一個變數的別名，這是邏輯錯誤。因為這會造成將其他變數的值指定到已經宣告成為別名的參照位址。 將被呼叫的函式中一個自動變數的指標或參照變數 return 回去是邏輯錯誤，某些 compiler 會產生警告訊息。

73 3.18 預設的引數 Default Arguments
預設引數的功用：若函式的參數被省略時，就使用預設值 可以是常數、全域變數、或函式呼叫 呼叫函式時，若沒有提供足夠的參數個數，最右邊的就用預設值 在函式原型中設定預設值 int defaultFunction( int x = 1,int y = 2, int z = 3 );

74 變數名稱可以省略 使用三個 default 參數 使用兩個 default 參數 使用一個 default 參數
1 // Fig. 3.23: fig03_23.cpp 2 // Using default arguments 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 int boxVolume( int length = 1, int width = 1, int height = 1 ); 9 10 int main() 11 { 12 cout << "The default box volume is: " << boxVolume() << "\n\nThe volume of a box with length 10,\n" << "width 1 and height 1 is: " << boxVolume( 10 ) << "\n\nThe volume of a box with length 10,\n" << "width 5 and height 1 is: " << boxVolume( 10, 5 ) << "\n\nThe volume of a box with length 10,\n" << "width 5 and height 2 is: " << boxVolume( 10, 5, 2 ) << endl; 20 21 return 0; 22 } 23 24 // Calculate the volume of a box 25 int boxVolume( int length, int width, int height ) 26 { 27 return length * width * height; 28 } 變數名稱可以省略 1. Function prototype 2. Print default volume 2.1 Print volume with one parameter 2.2 Print with 2 parameters 2.3 Print with all parameters. 3. Function definition 使用三個 default 參數 使用兩個 default 參數 使用一個 default 參數 沒有使用 default 參數

75 指定並嘗試使用一個不在最右邊(尾端)引數的預設值，而此引數右方的所有引數並未同時使用預設值，這是語法錯誤。 良好的程式設計習慣 3.10
The default box volume is: 1 The volume of a box with length 10, width 1 and height 1 is: 10 width 5 and height 1 is: 50 width 5 and height 2 is: 100 Program Output Notice how the rightmost values are defaulted. 常見的程式設計錯誤 3.28 指定並嘗試使用一個不在最右邊(尾端)引數的預設值，而此引數右方的所有引數並未同時使用預設值，這是語法錯誤。 良好的程式設計習慣 3.10 使用預設引數可簡化函式呼叫的的撰寫。不過有些程式設計者則認為將所有的引數都寫出來可使程式更清楚。

76 3.19 一元範圍解析運算子 Unary Scope Resolution Operator
一元範圍解析運算子 (::) 功用：可存取相同名稱的全域變數 如果變數名稱都不同時，並不需要用到 寫法 ::variable 而不是 variable 不能用這個方法存取外層、非 global 的變數 其實大家寫程式時，最好儘量避免用相同名稱的變數代表不同的意義，所以沒有需要的話，最好不要有相同名稱的變數，出現在彼此包含的 block 中。

77 1. Define variables 2. Print variables Program Output
1 // Fig. 3.24: fig03_24.cpp 2 // Using the unary scope resolution operator 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 #include <iomanip> 9 10 using std::setprecision; 11 12 const double PI = ; 13 14 int main() 15 { 16 const float PI = static_cast< float >( ::PI ); 17 18 cout << setprecision( 20 ) << " Local float value of PI = " << PI << "\nGlobal double value of PI = " << ::PI << endl; 21 22 return 0; 23 } 1. Define variables 2. Print variables Program Output Notice the use of :: Local float value of PI = Global double value of PI =

78 3.20 函式重載 Function Overloading
可以定義相同名稱、不同參數的函式 應該執行相似的工作(例如：分別對 int 與 float 作相同的處理). 用相同的涵式名稱、不同的參數來作類似的事情，可以增加可讀性。例如定義 multiplication 可作一維、二維、三維、……矩陣相乘，可以不需要記太多的涵數名稱。 int square( int x) {return x * x;} float square(float x) { return x * x; } 程式用函式的簽名(signature)來判斷該呼叫哪個函式 signature 由函式名稱與參數型態來決定 可以有相同的傳回值型態

79 1. Define overloaded function 2. Call function Program Output
1 // Fig. 3.25: fig03_25.cpp 2 // Using overloaded functions 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 int square( int x ) { return x * x; } 9 10 double square( double y ) { return y * y; } 11 12 int main() 13 { 14 cout << "The square of integer 7 is " << square( 7 ) << "\nThe square of double 7.5 is " << square( 7.5 ) << endl; 17 18 return 0; 19 } Functions have same name but different parameters 1. Define overloaded function 2. Call function Program Output The square of integer 7 is 49 The square of double 7.5 is 56.25

80 3.20 函式重載 Function Overloading
常見的程式設計錯誤 建立兩個參數列相同、傳回值型態不同的重載函式，這是語法錯誤。 可以省略參數的函式若與其他函式成為重載函式時，會造成語法錯誤。例如：一個函式沒有參數、另一個相同名稱的函式有一個有預設值的參數，當呼叫這兩個函式相同的名稱且沒有提供參數時，就會造成語法錯誤。

81 3.21 函式樣板 Function Templates
想要對不同型態的資料作相同的運算時，可以用 template 的方式，可以作得比 overloaded function 還要好。 可以定義一個 template 的函式，用任何資料型態呼叫時，就會產生該種資料型態的程式碼出來。也就是寫一個 template 的函式，就可以處理所有的資料型態。 所以 template 定義就像一個 code generator 一樣。 第十二章會講到更多涵數的 template 與 class 的 template。

82 3.21 函式樣板 Function Templates
關鍵字 class 或 typename 要放在每個型態參數前 template < class T > // or template< typename T > T square( T value1 ) { return value1 * value1; } T 當函式呼叫時，T 會被參數的型態取代 int x; int y = square(x); 若參數型態為 int, 則所有的 T 都變成 int 同樣可用 float, double, long... 來取代

83 //Fig. 3.27: fig03_27.cpp //Using a function template #include <iostream> using std::cout; using std::cin; using std::endl; template <class T> T maximum (T value1, T value2, T value3) { T max = value1; if (value2 > max) max = value2; if (value3 > max) max = value3; return max; }

84 int main() { int int1, int2, int3; cout << “Input three integer values: “; cin >> int1 >> int2 >> int3; cout << “The maximum integer value is: “ << maximum (int1, int2, int3); double double1, double2, double3; cout << “\nInput three double values: “; cin >> double1 >> double2 >> double3; cout << “The maximum double value is: “ << maximum (double1, double2, double3); char char1, char2, char3; cout << “\nInput three characters: “; cin >> char1 >> char2 >> char3; cout << “The maximum character value is: “ << maximum (char1, char2, char3); << endl; return 0; } 建立一份整數參數的 maximum 涵數 建立一份double 參數的 maximum 涵數 建立一份 character 參數的 maximum 涵數 Input three integer values: 1 2 3 The maximum integer value is: 3 Input three double values: The maximum double value is: 3.3 Input three characters: A C B The maximum character value is: C

85 3.22 Thinking About Objects: Identifying a Class’s Attributes
第二章的最後一節介紹過一個模擬電梯的例子，在第二章中，我們介紹這個例子中所用到的物件（類別）。 在這一節中，我們繼續討論這個例子，而這裡我們將討論這些類別的屬性。第四章會討論操作(operation)，第五章討論物件間的互動、又稱 collaboration。 真實世界物件的屬性，人：身高、體重，汽車：里程表、速度表讀取方式、油量，個人電腦：廠牌、螢幕型態、RAM 大小、hard disk 大小等。 我們平常都是用屬性來描述類別，所以要找出類別的 屬性時，首先就看這些類別有哪些描述詞。 例如電梯的屬性包括：容量、目前停在哪一樓、往上或往下、要花五秒鐘到另一層、是否在移動。

86 3.22 Thinking About Objects: Identifying a Class’s Attributes
屬性名稱 型別 初值 Elevator currentFloor:int = 1 direction:enum = up capacity:int = 1 arrivalTime:int moving:bool = false Clock time:int = 0 Door open:bool = false Floor capacity:int = 1 occupied:bool = false Bell <none yet> Scheduler floor1ArrivalTime:int floor2ArrivalTime:int Light on:bool = false FloorButton pressed:bool = false Building <none yet> ElevatorButton pressed:bool = false Person ID:int Fig Class diagram showing attributes

87 3.22 Thinking About Objects: Identifying a Class’s Attributes
狀態描述圖 Statechart diagrams 物件有狀態，statechart diagram 是描述一個物件如何在這些狀態間轉換。通常都是發生某個 event 之後作轉換。 Not pressed Pressed button press button reset Fig.3.30 Statechart diagram for classes FloorButton and ElevatorButton. Moving Waiting Servicing Floor Exit/close door [No further request] button press[current floor] button press[other floor] arrivalTime = currentTime + 5 when[currentTime == arrivalTime] button press[need to move] Fig Statechart diagram for class Elevator.

88 3.22 Thinking About Objects: Identifying a Class’s Attributes
Close door Move to other floor Stop moving Reset elevator button Ring bell Open door [button pressed] [current floor button pressed] not pressed] [current floor button [in motion] [currentTime < arrivalTime] [currentTime = Fig 3.32 Activity diagram modeling elevator’s logic for responding to button presses. Activity diagrams 描述某個物件的活動。

89

90

91

92

93

94

95

96

97

98

99

100