第三講 ?函數(shù)

一 ?函數(shù)聲明與調(diào)用 ?

1 ?函數(shù)調(diào)用

主調(diào)（客戶(hù)）函數(shù)與被調(diào)（服務(wù)器）函數(shù) 函數(shù)調(diào)用時(shí)的參數(shù)與返回值 例一： Swap( a, b ); 例二： n = Add( a, b ); ?

2 ?函數(shù)原型

函數(shù)的實(shí)現(xiàn)與調(diào)用格式說(shuō)明：作為函數(shù)接口 一般出現(xiàn)在頭文件中 格式： 函數(shù)返回值類(lèi)型 函數(shù)名稱(chēng)( 形式參數(shù)列表 ); 例一： int Add( int x, int y ); 例二： void Swap( int x, int y ); 例三： void Compute(); ?

二 ?函數(shù)定義

1 ?函數(shù)實(shí)現(xiàn)

函數(shù)定義，使用編程語(yǔ)言給出函數(shù)的執(zhí)行步驟

2 ?函數(shù)返回值

函數(shù)完成后帶回來(lái)的結(jié)果 主調(diào)函數(shù)可以使用

3 ?謂詞函數(shù)

返回 bool 類(lèi)型值的函數(shù) 表達(dá)某項(xiàng)任務(wù)是否完成或某個(gè)條件是否滿(mǎn)足

4 ?函數(shù)重載 ?

定義同名但參數(shù)不完全相同的函數(shù)

示 例:

?int Max( int x, int y );
?char Max( char x, char y );
?bool Max( bool x, bool y );

三 ?函數(shù)調(diào)用規(guī) ?

1 ?參數(shù)傳遞機(jī)制

• 值傳遞

• 形式參數(shù)在函數(shù)調(diào)用時(shí)才分配存儲(chǔ)空間，并接受實(shí)際參數(shù)的值

• 實(shí)際參數(shù)可以為復(fù)雜的表達(dá)式，在函數(shù)調(diào)用前獲得計(jì)算

• 形式參數(shù)與實(shí)際參數(shù)可同名，也可不同名

• 參數(shù)較多時(shí)，實(shí)際參數(shù)值逐一賦值，它們必須保持?jǐn)?shù)目、類(lèi)型、 順序的一致

• 值的復(fù)制過(guò)程是單向不可逆的，函數(shù)內(nèi)部對(duì)形式參數(shù)值的修改 不會(huì)反映到實(shí)際參數(shù)中去

• 函數(shù)參數(shù)一般為函數(shù)輸入集的一部分，函數(shù)輸出集一般使用返 回值表示，只有使用特殊的手段才可以將函數(shù)參數(shù)作為函數(shù)輸 出集的一部分 ?

• 引用傳遞

2 ?函數(shù)調(diào)用?？蚣??

第四講 ?算法

一 ?算法概念與特征

1 ?算法基本概念

• 算法定義：解決問(wèn)題的方法與步驟

• 設(shè)計(jì)算法的目的：給出解決問(wèn)題的邏輯描述，根據(jù)算法描述進(jìn)行實(shí)際編程

2 ?算法特征

• 有窮性：算法在每種情況下都可以在有限步后終止

• 確定性：算法步驟的順序和內(nèi)容沒(méi)有二義性

• 輸入：算法有零個(gè)或多個(gè)輸入

• 輸出：算法至少具有一個(gè)輸出

• 有效性：所有操作具有明確含義，并能在有限時(shí)間內(nèi)完成 ?

二 ?算法描述

• 偽代碼

• 流程圖（程序框圖）

三 ?算法設(shè)計(jì)與實(shí)現(xiàn)

1 ?算法設(shè)計(jì)與實(shí)現(xiàn)

• 構(gòu)造算法解決問(wèn)題

• 按照自頂向下、逐步求精的方式進(jìn)行

• 使用程序設(shè)計(jì)語(yǔ)言編程實(shí)現(xiàn) ?

四 ?遞歸算法

1 ?遞歸問(wèn)題的引入

• 遞推公式：數(shù)學(xué)上非常常見(jiàn) 例一：階乘函數(shù)： 1! = 1， n! = n × (n-1)! 例二：斐波那契數(shù)列函數(shù)： f(1) = f(2) = 1， f(n) = f(n-1) + f(n-2)

• 遞推函數(shù)一定是分段函數(shù)，具有初始表達(dá)式

• 遞推函數(shù)的計(jì)算邏輯：逐步簡(jiǎn)化問(wèn)題規(guī)模

2 ?遞歸的工作步驟

• 遞推過(guò)程：逐步分解問(wèn)題，使其更簡(jiǎn)單

• 回歸過(guò)程：根據(jù)簡(jiǎn)單情形組裝最后的答案 ?

3 ?循環(huán)與遞歸的比較 ?

• 循環(huán)使用顯式的循環(huán)結(jié)構(gòu)重復(fù)執(zhí)行代碼段，遞歸使用重復(fù)的函數(shù)調(diào)用執(zhí)行代碼段

• 循環(huán)在滿(mǎn)足其終止條件時(shí)終止執(zhí)行，而遞歸則在問(wèn)題簡(jiǎn)化到最簡(jiǎn)單情形時(shí)終止執(zhí)行

• 循環(huán)的重復(fù)是在當(dāng)前迭代執(zhí)行結(jié)束時(shí)進(jìn)行，遞歸的重復(fù)則是在遇到對(duì)同名函數(shù)的調(diào)用時(shí)進(jìn)行

五 ?容 錯(cuò)

1 ?定義

• 允許錯(cuò)誤的發(fā)生

2 ?錯(cuò)誤的處理

• 很少見(jiàn)的特殊情況或普通錯(cuò)誤：忽略該錯(cuò)誤不對(duì)程序運(yùn)行結(jié)果產(chǎn)生影響

• 用戶(hù)輸入錯(cuò)誤：通知用戶(hù)錯(cuò)誤性質(zhì)，提醒用戶(hù)更正輸入

• 致命錯(cuò)誤：通知用戶(hù)錯(cuò)誤的性質(zhì)，停止執(zhí)行

3 ?典型容錯(cuò)手段

• 數(shù)據(jù)有效性檢查

• 程序流程的提前終止 ?

六 ?算法復(fù)雜度 ?

1 ?引入算法復(fù)雜度的目的

• 度量算法的效率與性能

2 ?大 O 表達(dá)式

• 算法效率與性能的近似表示（定性描述）

• 算法執(zhí)行時(shí)間與問(wèn)題規(guī)模的關(guān)系

3 ?表示原則

• 忽略所有對(duì)變化趨勢(shì)影響較小的項(xiàng)，例如多項(xiàng)式忽略高階項(xiàng)之外的所有項(xiàng)

• 忽略所有與問(wèn)題規(guī)模無(wú)關(guān)的常數(shù)，例如多項(xiàng)式的系數(shù) ?

4 ?標(biāo)準(zhǔn)算法復(fù)雜度類(lèi)型 ?

• O(1)：常數(shù)級(jí)，表示算法執(zhí)行時(shí)間與問(wèn)題規(guī)模無(wú)關(guān)

• O(log(n))：對(duì)數(shù)級(jí)，表示算法執(zhí)行時(shí)間與問(wèn)題規(guī)模的對(duì)數(shù)成正比

• O(sqrt(n))：平方根級(jí)，表示算法執(zhí)行時(shí)間與問(wèn)題規(guī)模的平方根成正比

• O(n)：線(xiàn)性級(jí)，表示算法執(zhí)行時(shí)間與問(wèn)題規(guī)模成正比

• O(n*log(n))： nlog(n) 級(jí)，表示算法執(zhí)行時(shí)間與問(wèn)題規(guī)模的nlog(n) 成正比

• O(n2)：平方級(jí)，表示算法執(zhí)行時(shí)間與問(wèn)題規(guī)模的平方成正比

七 ?練習(xí)

?#include<iostream>
?#include<cmath>
?
?using namespace std;
?bool IsPrime( unsigned int n );
?
?int main()
?{
? ? ?int n,i;
? ? ?cout << "Please enter a number n(n > 1):";
? ? ?cin >> n;
? ? ?cout << n << " = ";
? ? ?for(i = 2;i <= n;i++)
? ? ?{
? ? ? ? ?while(n % i == 0)
? ? ? ? ?{
? ? ? ? ? ? ?if(IsPrime( i ))
? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ?cout << ?i;
? ? ? ? ? ? ? ? ?n /=i;
? ? ? ? ? ? ? ? ?if(n != 1)
? ? ? ? ? ? ? ? ?cout << "*";
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ?}
? ? ?cout << endl;
? ? ?return 0;
?}
?
?bool IsPrime( unsigned int n )
?{
? ? ?unsigned int i = 2, t = (unsigned int)sqrt(n) + 1;
? ? ?if(n == 2)
? ? ?return true;
? ? ?if( n % 2 == 0 )
? ? ?return false;
? ? ?while( i <= t )
? ? ?{
? ? ? ? ?if( n % i == 0 )
? ? ? ? ?return false;
? ? ? ? ?i += 2;
? ? ?} ?
? ? ?return true;
?}?#include<iostream>
?#include<cmath>
?
?using namespace std;
?
?int main()
?{
? ? ?int n,i;
? ? ?cout << "Please enter a number n(n > 1):";
? ? ?cin >> n;
? ? ?cout << n << " = ";
? ? ?for(i = 2;i <= n;i++)
? ? ?{
? ? ? ? ?while(n % i == 0)
? ? ? ? ?{
? ? ? ? ? ? ?
? ? ? ? ? ? ?cout << ?i;
? ? ? ? ? ? ?n /=i;
? ? ? ? ? ? ?if(n != 1)
? ? ? ? ? ? ?cout << "*";
? ? ? ? ?}
? ? ?}
? ? ?cout << endl;
? ? ?return 0;
?}
?//不用判斷因數(shù)是否為素?cái)?shù)也可以