基于linux的C++學(xué)習(xí)筆記4（算法 示例 優(yōu)化）
算法：解決問題的方法和步驟
設(shè)計算法的目的：給出解決問題的邏輯描述，根據(jù)算法描述進(jìn)行實際編程
算法特征：有窮性、確定性、輸入、輸出、有效性
有窮性——算法在每種情況下都可以在有限步后終止
確定性——算法步驟的順序和內(nèi)容沒有二義性
輸入——算法有零個或多個輸入
輸出——算個發(fā)至少具有一個輸出
有效性——所有操作具有明確的含義，并在有限時間內(nèi)完成
正確性不是算法的特征，算法的正確性數(shù)學(xué)證明
算法示例一：幻方(3*3)
? ? ? ? ? 9? ? ? ?2
?8? ? ? ?1?? ? ? 6?? ? ? ?8
?3? ? ?? 5 ? ? ? 7?? ? ? ?3
?4? ? ? ?9?? ? ? 2? ?
省略了格子
找出規(guī)律，編寫步驟：
步驟一：把1寫在第一行中間一格
步驟二：在該格右上方的那一格寫入下一個自然數(shù)（若該數(shù)超出3*3幻方范圍，將該數(shù)寫在其所在的那一排或列的另一端格子中，即相當(dāng)于認(rèn)為幻方外圍仍然包含了同樣的幻方，而該數(shù)卸載外圍幻方的同樣位置；每寫完三個數(shù)，將第四個樹寫在第三個數(shù)下面格子中）
步驟三：重復(fù)步驟二，直到所有格子均填滿
算法示例二：查英文單詞
步驟一：翻開詞典任意一頁
步驟二：若所查的詞匯按字母排列順序在本頁第一個單詞之前，則往前翻開任意一頁，重復(fù)步驟二；若所查單詞在本頁最后一個單詞之后，則往后翻開任意一頁，重復(fù)步驟二
步驟三：若上述兩個條件都不滿足，則該單詞要么在本頁上，要么詞典中不存在（依次比較本頁單詞，或者查出該單詞，或者得到該單詞查不到的結(jié)論）
算法描述：偽代碼、流程圖
偽代碼——混合自然語言與計算機語言、數(shù)學(xué)語言的算法描述方法
優(yōu)點：方便，容易表達(dá)設(shè)計者思想，清洗描述算法流程，便于修改
缺點：不美觀，復(fù)雜算法不容易理解
順序結(jié)構(gòu)、分支結(jié)構(gòu)（if??else）、循環(huán)結(jié)構(gòu)（for?while）
流程圖（程序框圖）——使用圖形表示算法執(zhí)行邏輯
優(yōu)點：美觀，算法表達(dá)清晰
缺點：繪制復(fù)雜，不易修改，占用過多篇幅
。
算法設(shè)計與實現(xiàn)
構(gòu)造算法解決問題
按照自頂向下、逐步求精的方式進(jìn)行
使用程序設(shè)計語言設(shè)計語言編程實現(xiàn)
典型示例：
素數(shù)判定問題——判定給定的某個自然數(shù)n（大于2是否為素數(shù)）
算法邏輯
????輸入：大于2的正整數(shù)n
????輸出：該數(shù)是否為素數(shù)，若為素數(shù)返回true，否則返回false
????步驟一：設(shè)除數(shù)i為2
????步驟二：判斷除數(shù)i是否已為n，若為真返回true，否則繼續(xù)
????步驟三：判斷n%i是否為0，若為0返回false，否則繼續(xù)
????步驟四：將除數(shù)i遞增，重復(fù)步驟二
第一版
bool?IsPrime(unsigned int n){
????unsigned int i = 2;
????while(i < n){
????????if(n%i == 0)? ? ????????return?false;
????????i++;
????}
????return true;
}
第二版（優(yōu)化用平方根以內(nèi)數(shù)做除數(shù)）
bool IsPrime(unsigned int n){
????unsigned int i = 2;
????while(i <= (unsigned int)sqrt(n)){? ? ? ? ?//sqrt為標(biāo)準(zhǔn)庫中的求平方根函數(shù),返回值為浮點數(shù)
????????if(n%i == 0)? ? return false;
????????i++;
????}
????return true;
}
第三版（優(yōu)化首先判斷是否是偶數(shù)）
bool IsPrime(unsigned int n){
????unsigned int i?= 3;
????if(n%2 == 0)? ? ? ?return false;? ? ? ? ? ? ? //是偶數(shù)也就是合數(shù)
????while(i <= (unsigned int)sqrt(n)){? ? ? ? ?//sqrt為標(biāo)準(zhǔn)庫中的求平方根函數(shù),返回值為浮點數(shù)
????????if(n%i == 0)? ? return false;
????????i++;
????}
????return true;
}
第四版（優(yōu)化防止平方根計算浮點數(shù)帶來的誤差導(dǎo)致錯誤，如：121的平方根被計算成10.999999強轉(zhuǎn)unsigned?int為10）
bool IsPrime(unsigned int n){
????unsigned int i?= 3;
????if(n%2 == 0)? ? ? ?return false;? ? ? ? ? ? ? //是偶數(shù)也就是合數(shù)
????while(i <=?(unsigned int)sqrt(n) + 1){? ? ? ? ?//sqrt為標(biāo)準(zhǔn)庫中的求平方根函數(shù),返回值為浮點數(shù)
????????if(n%i == 0)? ? return false;
????????i++;
????}
????return true;
}
第五版（優(yōu)化防止求平方根操作在while循環(huán)中重復(fù)執(zhí)行）
bool IsPrime(unsigned int n){
????unsigned int i?= 3, t = (unsigned int)sqrt(n)?+?1;
????if(n%2 == 0)? ? ? ?return false;??? ? ? ? ? ? //是偶數(shù)也就是合數(shù)
????while(i?<= t){? ? ? ? ?//sqrt為標(biāo)準(zhǔn)庫中的求平方根函數(shù),返回值為浮點數(shù)
????????if(n%i == 0)? ? return false;
????????i += 2;
????}
????return true;
}
算法選擇的權(quán)衡指標(biāo)
正確性：算法是否完全正確
效率：在某些場合，對程序效率的追求具有重要意義
可理解性：算法是否容易理解，也是必須要考慮的
算法評估：衡量算法的好壞，主要是效率
最大公約數(shù)問題——求兩個整數(shù)x與y的最大公約數(shù)
第一版（窮舉法）
unsigned int gcd(unsigned int x, unsigned int y){
????unsigned int t;
????t = x<y?x:y;
????while(x%t != 0 || y%t != 0)? ? ?t--;
????return t;
}
第二版（歐式算法）
輸入：正整數(shù)x、y
輸出：最大公約數(shù)
步驟一：x整除以y，記余數(shù)為r
步驟二：若r為0，則最大公約數(shù)即為y，算法結(jié)束
步驟三：否則將y作為新x，將r作為新y，重復(fù)上述操作
unsigned int gcd(unsigned int x, unsigned int y){
????unsigned int t;
????while(true)
????{
????????r = x%y;
????????if(r == 0)? ? ? ? ? return y;
????????x = y;
????????y = r;?
????}
}
遞歸算法
遞推公式：數(shù)學(xué)上很常見，階乘函數(shù)（1！=1，n！=n*（n-1）?。㈧巢瞧鯏?shù)列（f（1）=f（2）=1，f(n)=f(n-1)+f(n-2)）
遞推函數(shù)一定是分段函數(shù)，具有初始表達(dá)式
遞推函數(shù)的計算邏輯：逐步簡化問題規(guī)模
遞歸的工作步驟
????遞推過程：逐步分解問題，使其更簡單
????回歸過程：根據(jù)簡單情形組裝最后的答案
階乘函數(shù)
使用循環(huán)實現(xiàn)
unsigned int GetFactorial(unsigned int n){
????unsigned int result? = 1, i = 0;
????while(++i <= n)? ? ?result *= i;
????return result;
}
使用遞歸實現(xiàn)
unsigned int GetFactorial(unsigned int n){
????unsigned int?result;
????if(1 ==?n)? ? ?result =?1;
????else? ? ? ? ? ? ?result = n*GetFactorial(n-1);
????return result;
}
斐波那契數(shù)列函數(shù)
使用循環(huán)實現(xiàn)
unsigned?int GetFibonacci(unsigned int n){
????unsigned int i, f1, f2, f3;
????if(2 == n || 1 == n)? ? ? ?return 1;
????f2 = 1;f1 = 1;
????for(i = 3; i <= n; i++){
????????f3 = f2 + f1; f1 = f2; f2 = f3;
????}
????return f3;
}
使用遞歸實現(xiàn)
unsigned?int GetFibonacci(unsigned int n){
????if(2 == n || 1 == n)? ? ? ?return 1;
? ??else? ? ? ? ? ? ? ? ? ? ? ? ? ? ?return GetFibonacci(n-1) +?GetFibonacci(n-2);
}
循環(huán)和遞歸的比較：
????循環(huán)使用顯式的循環(huán)結(jié)構(gòu)重復(fù)執(zhí)行代碼段，遞歸使用重復(fù)的函數(shù)調(diào)用執(zhí)行代碼段
????循環(huán)在滿足其終止條件時終止執(zhí)行，而遞歸則在問題簡化到最簡單情形時終止執(zhí)行
????循環(huán)的重復(fù)是在當(dāng)前迭代執(zhí)行結(jié)束時進(jìn)行，遞歸的重復(fù)則是在遇到對同名函數(shù)的調(diào)用時進(jìn)行
????循環(huán)和遞歸都可能隱藏程序錯誤，循環(huán)的條件測試可能永遠(yuǎn)為真，遞歸可能永遠(yuǎn)退化不到最簡單情形
????理論上任何遞歸程序都能使用循環(huán)迭代的辦法解決（遞歸函數(shù)的代碼短小精悍，掌握遞歸的思考方法，遞歸程序更容易理解）
漢諾塔問題——假設(shè)有三個分別命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小不同、依小到大分別編號為1，2，3......，n的圓盤，要求將塔座X上的n歌圓盤移動到塔座Z上并按相同順序疊放，圓盤移動時必須遵循的規(guī)則：
????每次只能移動一個圓盤；
????圓盤可以插在X、Y、Z中的任意一個塔座上；
????任何時刻都不能將較大的圓盤壓在較小的圓盤上；
問題分析：
????是否存在簡單情形，問題很容易解決
????是否將原始問題分解成性質(zhì)相同但規(guī)模較小的子問題，且新問題的解答對原始問題有關(guān)鍵意義
解決方案（數(shù)學(xué)歸納法）
????只有一個圓盤是最簡單的情形
????對于n-1，考慮n-1個圓盤，若將n-1個圓盤移動到某個塔座上，則可移動第n個圓盤
????策略：先將n-1個圓盤移動到塔座Y上，然后將第n個圓盤移動到Z上，最后將n-1個圓盤從Y上移動到Z上
偽代碼
void MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to)
{
????if(1 == n)????將一個圓盤從form移動到to
????else{
????????將n-1個圓盤從from以to為中轉(zhuǎn)移動到tmp
????????將圓盤n從from移動到to
????????將n-1個圓盤從tmp以from為中轉(zhuǎn)移動到to
????}
}
程序代碼
#include<iostream>
using namespace std;
/*?枚舉類型HANOI，?分別表示三個圓柱代號?*/
unsigned int GetInteger();
void MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to);
char ConverHanoiToChar(HANOI x);
void MovePlate(unsigned int n, HANOI from, HANOI to);
int main(){
????unsigned int n;
????n =?GetInteger();
????MoveHanoi(n, X, Y, Z);
????return 0;
}
unsigned int?GetInteger(){//獲取輸入值
????unsigned int t;
????cout << "Input number of plates:";
????cin >> t;
????return t;
}
void?MoveHanoi(unsigned int n, HANOI from, HANOI tmp, HANOI to){
????if(1 == n)????MovePlate(n, from , to);
????else{
????????MoveHanoi(n-1, from, to, tmp);
????????MovePlate(n, from, to);
????????MoveHanoi(n-1, tmp, from, to);
????}
}
char ConverHanoiToChar(HANOI?x){//將枚舉文字轉(zhuǎn)換成字符
????switch(x){
????????case X:return 'X';
? ? ????case Y:return 'Y';
? ? ????case Z:return 'Z';
? ? ? ? default:return '\0';
????}
}
void?MovePlate(unsigned int n, HANOI from,?HANOI to){
????char fc, tc;
????fc = CovertHanoiToChar(from);
? ??tc = CovertHanoiToChar(to);
????cout << n << ":" << fc << "-->" << tc <<endl;
}
遞歸信任
遞歸實現(xiàn)是否檢查了最簡單的情形
????在嘗試將問題分解成子問題前，首先檢查問題是否已足夠簡單
????在大多數(shù)情況下，遞歸函數(shù)以if開頭
????如果不是這樣，仔細(xì)檢查源代碼
是否解決了最簡單情形
????大量遞歸錯誤是由沒有正確解決最簡單情形導(dǎo)致的
????最簡單情形不能調(diào)用遞歸
遞歸分解是否使問題更簡單
????只有分解出子問題更簡單，遞歸才能正確工作，否則將形成無限遞歸，算法無法終止
問題簡化過程是否能夠確實回歸最簡單情形，還是遺漏了某些情況
????如漢諾塔問題需要調(diào)用兩次遞歸過程，程序中如果遺漏了任意一個都會導(dǎo)致錯誤
子問題是否與原始問題完全一致
????如果遞歸過程改變了問題實質(zhì)，則整個過程肯定會得到錯誤結(jié)果
使用遞歸信任時，子問題的解是否正確組裝為原始問題的解
????將子問題的解正確組裝以形成原始問題的解也是必不可少的步驟
容錯：允許錯誤的發(fā)生
錯誤的處理
????很少見的特殊情況或普通錯誤：忽略該錯誤不對程序運行結(jié)果產(chǎn)生影響
????用戶輸入錯誤：通知用戶錯誤性質(zhì)，提醒用戶更正輸入
????致命錯誤：通知用戶錯誤的性質(zhì)，停止執(zhí)行
典型容錯手段
????數(shù)據(jù)有效性檢查
????程序流程的提前終止
數(shù)據(jù)有效性檢查示例：
void GetUserInput(){
????獲取用戶輸入的數(shù)據(jù)
????while(用戶輸入的數(shù)據(jù)無效){
????????通知用戶輸入數(shù)據(jù)有誤，提醒用戶重新輸入數(shù)據(jù)
????????重新獲取用戶輸入數(shù)據(jù)
????}
}
素數(shù)判定函數(shù)第六版（添加參數(shù)檢查及異常處理）
const int failed_in_testing_primality = 1;
bool IsPrime(unsigned int n){
????unsigned int i = 3, t = (unsigned int)sqrt(n)+1;
????if(1 =>?n){//越界處理，提示錯誤信息并返回錯誤碼
????????cout << "IsPrime:Failed in testing the primality of" << n << endl;
????????exit(failed_in_testing_primality);
????}
? ? if(n?== 2)????return true;//2為素數(shù)
????if(n%2 == 0)????return false;
????while( i <= t){
????????if(n%i == 0)? return false;
????????i += 2;
????}
????return true;
}
算法復(fù)雜度
引入算法復(fù)雜度的目的——度量算法的效率和性能
大O表達(dá)式
????算法效率與性能的近似表示（定性描述）
????算法執(zhí)行時間與問題規(guī)模的關(guān)系
表示原則
????忽略所有對變化趨勢影響較小的項，例如多項式忽略高階項之外的所有項
????忽略所有與問題規(guī)模無關(guān)的常數(shù)，例如多項式的系數(shù)
O(1)：常數(shù)級，表示算法執(zhí)行時間與問題規(guī)模無關(guān)
O(log(n))：對數(shù)級，表示算法執(zhí)行時間與問題規(guī)模的對數(shù)成正比
O(sprt(n))：平方根級，表示算法執(zhí)行時間與問題規(guī)模的平方根成正比
O(n)：線性級，表示算法執(zhí)行時間與問題規(guī)模成正比
O(n*log(n))：n*log(n)級，表示算法執(zhí)行時間與問題規(guī)模的n*log(n)成正比
O(n2)：平方級，表示算法執(zhí)行時間與問題規(guī)模的平方成正比
......
算法復(fù)雜度估計
for(i =?0; i < n; i++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //O(n)
????;
for(i?=?0; i < n; i++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //O(n2)
???for(j?=?0; j?< n; j++)
?????????;
for(i?=?0; i < n; i++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //O(n2)
???for(j?=?i;?j?<?n;?j++)
?????????;
