算法問題求解基礎(chǔ)

1、第1章 算法問題求解基礎(chǔ)1第1章 算法問題求解基礎(chǔ)2平時要求：平時要求： 按時上下課、課堂不吵鬧、手機(jī)調(diào)成非鈴聲狀態(tài)按時上下課、課堂不吵鬧、手機(jī)調(diào)成非鈴聲狀態(tài)考試成績：考試成績：平時表現(xiàn)（考勤、隨堂提問、作業(yè)等）：平時表現(xiàn)（考勤、隨堂提問、作業(yè)等）：20%20%期末考試：期末考試：80%80%第1章 算法問題求解基礎(chǔ)3課程簡介課程簡介課程名稱：課程名稱：算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 Design and Analysis of Algorithms Design and Analysis of Algorithms 先修課程：先修課程： 面向?qū)ο蟪绦蛟O(shè)計(jì)語言面向?qū)ο蟪绦蛟O(shè)計(jì)語言C+C+，數(shù)據(jù)結(jié)

2、構(gòu)，數(shù)據(jù)結(jié)構(gòu)，離散結(jié)構(gòu)離散結(jié)構(gòu)第1章 算法問題求解基礎(chǔ)4第1章 算法問題求解基礎(chǔ)第1部分 算法和算法分析1.1 算法概述 1.2 問題求解方法 1.3 算法設(shè)計(jì)與分析 1.4 遞歸和歸納第1章 算法問題求解基礎(chǔ)51.1.1 什么是算法算法是計(jì)算機(jī)學(xué)科的一個重要分支，它是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是計(jì)算機(jī)程序的基石。算法是計(jì)算機(jī)求解問題的特殊方法。學(xué)習(xí)算法，一方面需要學(xué)習(xí)求解計(jì)算領(lǐng)域中典型問題的各種有效算法，還要學(xué)習(xí)設(shè)計(jì)新算法和分析算法性能的方法。1.1 算法概述算法（algorithm)：一個算法是對特定問題求解步驟的一種描述，它是指令的有限序列。 中國的珠算口訣可視為典型的算法，它將復(fù)雜的計(jì)算描述

3、為一系列的算珠撥動動作。第1章 算法問題求解基礎(chǔ)算法具有下列5個特征：6輸入（input）：算法有零個或多個輸入量；輸出（output）：算法至少產(chǎn)生一個輸出量；確定性（definiteness）：算法的每一條指令都有確切的定義，沒有二義性；能行性（effectiveness）：算法的每一條指令必須足夠基本，它們可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)；有窮性（finiteness）：算法必須總能在執(zhí)行有限步之后終止。第1章 算法問題求解基礎(chǔ)7最早的算法是歐幾里德的“求最大公因子算法”輾轉(zhuǎn)相除法 歐幾里德算法(輾轉(zhuǎn)相除法)計(jì)算兩個整數(shù)m和n（0mn)的最大公約數(shù)，記為gcd(m, n)。其計(jì)

4、算過程是重復(fù)應(yīng)用下列等式，直到n mod m=0.gcd(m,n)=gcd(n mod m,m),對于m0 (1-1) 式中，n mod m表示n除以m之后的余數(shù)。因?yàn)間cd(0,n)=n,n的最后取值也就是m和n最大公約數(shù)。例如，gcd(24,60)=gcd(12,24)=gcd(0,12)=12第1章 算法問題求解基礎(chǔ)8【程序1-1】 歐幾里德遞歸算法void Swap(int&a,int&b) int c=a;a=b;b=c;int RGcd(int m,int n) if(m=0) return n; return RGcd(n%m,m);int Gcd(int m,i

5、nt n) if (mn) Swap(m,n); return RGcd(m,n);第1章 算法問題求解基礎(chǔ)9【程序1-2】 歐幾里德迭代算法int Gcd(int m,int n)if (m=0)return n;if (n=0)return m;if (mn) Swap(m,n);while(m0)int c=n%m;n=m;m=c;return n;第1章 算法問題求解基礎(chǔ)10迭代和遞歸的區(qū)別迭代和遞歸各基于一種控制結(jié)構(gòu)，都涉及到循環(huán)，都可無限進(jìn)行。 迭代是循環(huán)求值，遞歸是調(diào)用本身； 迭代使用循環(huán)結(jié)構(gòu)，遞歸使用選擇結(jié)構(gòu)； 迭代是當(dāng)循環(huán)條件不滿足時終止，遞歸是當(dāng)滿足基本條件時終止； 迭代是

6、用計(jì)數(shù)器控制循環(huán)，不停地修改計(jì)數(shù)器的值，直到不滿足條件為止； 遞歸是逐漸逼近基本條件而終止，不斷的對問題進(jìn)行簡化直到可以直接計(jì)算基本問題為止。第1章 算法問題求解基礎(chǔ)11最大公約數(shù)問題還有其他算法。程序1-3的連續(xù)整數(shù)檢測法的依據(jù)直接來自最大公約數(shù)的定義：m和n的最大公約數(shù)是能夠同時整除它們的最大正整數(shù)?！境绦?-3】 Gcd的連續(xù)整數(shù)檢測算法int Gcd(int m,int n)if (m=0)return n; if (n=0)return m;int t=mn?n:m;while (m%t | n%t) t-;return t; 第1章 算法問題求解基礎(chǔ)121.1.2 為什么學(xué)習(xí)算法

7、算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才。對于計(jì)算機(jī)專業(yè)的學(xué)生來說，學(xué)習(xí)算法的理由是非常充分的。因?yàn)槟惚仨氈纴碜圆煌?jì)算領(lǐng)域的重要算法，你也必須學(xué)會設(shè)計(jì)新的算法、確認(rèn)其正確性并分析其效率。隨著計(jì)算機(jī)應(yīng)用的日益普及，各個應(yīng)用領(lǐng)域的研究和技術(shù)人員都在使用計(jì)算機(jī)求解他們各自專業(yè)領(lǐng)域的問題，他們需要設(shè)計(jì)算法，編寫程序，開發(fā)應(yīng)用軟件，所以學(xué)習(xí)算法對于越來越多的人來說變得十分必要。第1章 算法問題求解基礎(chǔ)Donald E. Knuth13l 計(jì)算機(jī)科學(xué)大師、“算法分析之父”唐德納（1938年1月10日-）現(xiàn)與其妻Jill生活于斯坦福校園內(nèi)。l 1974年美

8、國計(jì)算機(jī)協(xié)會圖靈獎 (ACM Turing Award)l 1979年美國前總統(tǒng)卡特授予的科學(xué)金獎(Medal of Science)l 1996年11月由于發(fā)明先進(jìn)技術(shù)榮獲極受尊重的京都獎(Kyoto Prize)。第1章 算法問題求解基礎(chǔ)141.2.1 問題和問題求解1.2 問題求解方法問題求解（problem solving）是尋找一種方法來實(shí)現(xiàn)目標(biāo)。問題求解過程（problem solving process）是人們通過使用問題領(lǐng)域知識來理解和定義問題，并憑借自身的經(jīng)驗(yàn)和知識去選擇和使用適當(dāng)?shù)膯栴}求解策略、技術(shù)和工具，將一個問題描述轉(zhuǎn)換成問題解的過程。計(jì)算機(jī)求解問題的關(guān)鍵之一是尋找一種

9、問題求解策略（problem solving strategy），得到求解問題的算法，從而得到問題的解。第1章 算法問題求解基礎(chǔ)151.2.2 問題求解過程問題求解的四步法簡述如下： 理解問題（understand the problem） 設(shè)計(jì)方案（devise a plan） 實(shí)現(xiàn)方案（carry out the plan） 回顧復(fù)查（look back）第1章 算法問題求解基礎(chǔ)161.2.3 系統(tǒng)生命周期劃分為: 分析（analysis） 設(shè)計(jì)（design） 編碼（coding or programming） 測試（testing） 維護(hù)（maintenance）等5個階段。前4個階段

10、屬于開發(fā)期，最后一個階段處于運(yùn)行期。 一個計(jì)算機(jī)程序的開發(fā)過程就是使用計(jì)算機(jī)求解問題的過程。軟件工程將軟件開發(fā)和維護(hù)過程分成若干階段，稱為系統(tǒng)生命周期或軟件生命周期第1章 算法問題求解基礎(chǔ)算法設(shè)計(jì)的整個過程，可以包含 問題需求的說明 數(shù)學(xué)模型的建立 算法的詳細(xì)設(shè)計(jì) 算法的正確性驗(yàn)證 算法的實(shí)現(xiàn) 算法分析 程序測試 文檔資料的編制在此我們只關(guān)心算法的設(shè)計(jì)和分析。17第1章 算法問題求解基礎(chǔ)181.3.1 算法問題求解過程算法一般分為兩類：精確算法和啟發(fā)式算法。精確算法（exact algorithm）總能保證求得問題的解。啟發(fā)式算法（heuristic algorithm）通過使用某種規(guī)則、簡化

11、或智能猜測來減少問題求解時間。 1.3 算法設(shè)計(jì)與分析第1章 算法問題求解基礎(chǔ)191.3.2 如何設(shè)計(jì)算法 使用計(jì)算機(jī)的問題求解策略主要指算法設(shè)計(jì)策略（algorithm design strategy）。算法設(shè)計(jì)技術(shù)（也稱“策略”）是使用算法解題的一般性方法，可用于解決不同計(jì)算領(lǐng)域的多種問題。 一般來說，算法的設(shè)計(jì)是一項(xiàng)創(chuàng)造性活動，但學(xué)習(xí)一些基本的算法設(shè)計(jì)策略是非常有用的。算法設(shè)計(jì)方法主要有：遞歸法、分治法、貪心算法、動態(tài)規(guī)劃法、回溯法、分支限界法等，我們將在后面的章節(jié)中陸續(xù)介紹。第1章 算法問題求解基礎(chǔ)201.3.3 如何表示算法 算法的基本結(jié)構(gòu) 用自然語言表示 用流程圖表示 用N-S流程

12、圖表示 用偽代碼表示 用計(jì)算機(jī)語言表示第1章 算法問題求解基礎(chǔ)211.3.4 如何確認(rèn)算法確認(rèn)一個算法是否正確的活動稱為算法確認(rèn)。使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明。程序測試（program testing）是指對程序模塊或程序總體，輸入事先準(zhǔn)備好的樣本數(shù)據(jù)（稱為測試用例，test case），檢查該程序的輸出，來發(fā)現(xiàn)程序存在的錯誤及判定程序是否滿足其設(shè)計(jì)要求的一項(xiàng)積極活動。第1章 算法問題求解基礎(chǔ)221.3.5 如何分析算法算法分析（algorithm analysis）活動是指對算法的執(zhí)行時間和所需空間的估算。在算法寫成程序后，便可使用樣本數(shù)據(jù)，實(shí)際測量一個程序所消耗的時間和空間，

13、這稱為程序的性能測量（performance measurement）。第1章 算法問題求解基礎(chǔ)23算法的正確性。算法的時間復(fù)雜度：一個算法在計(jì)算機(jī)上運(yùn)行所花費(fèi)的時間。算法的空間復(fù)雜度：在存儲器上所占用的存儲空間（主要考慮在算法運(yùn)行過程中臨時占用的存儲空間的大?。Ｋ惴ǖ囊鬃x性。 1.3.6 算法評價第1章 算法問題求解基礎(chǔ)241.4.1 遞歸1.遞歸定義遞歸（recursive）定義是一種直接或間接引用自身的定義方法。一個合法的遞歸定義包括兩部分：基礎(chǔ)情況和遞歸部分。1.4 遞歸和歸納第1章 算法問題求解基礎(chǔ)25例1-1 斐波那契數(shù)列根據(jù)這一定義，可以得到一個無窮數(shù)列0,1,1,2,3,5,

14、8,13,21,34,55，稱為斐波那契數(shù)列。1102110 nFFF, FFnnn第1章 算法問題求解基礎(chǔ)262.遞歸算法當(dāng)一個算法采用遞歸方式定義時便成為遞歸算法。一個遞歸算法是指直接或間接調(diào)用自身的算法?！境绦?-4】 求Fn long Fib( long n) if(n=1) return n;else return Fib(n-2)+Fib(n-1); 第1章 算法問題求解基礎(chǔ)27 可以用遞歸樹（recursive tree）來描述程序1-4的函數(shù)Fib執(zhí)行時的調(diào)用關(guān)系。 圖圖1-2 1-2 計(jì)算計(jì)算FibFib（4 4）的遞歸樹）的遞歸樹第1章 算法問題求解基礎(chǔ)遞歸方法的主要優(yōu)點(diǎn)：

15、結(jié)構(gòu)清晰、可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法證明算法的正確性，因此為設(shè)計(jì)算法、調(diào)試程序帶來了很大的方便。遞歸算法的缺點(diǎn)：由于不斷地函數(shù)調(diào)用，需要保存中間結(jié)果以及進(jìn)行參數(shù)的傳遞，遞歸方法算法的運(yùn)行效率較低，無論耗費(fèi)的計(jì)算時間還是占用的存儲空間都比非遞歸算法要多。28第1章 算法問題求解基礎(chǔ)291.4.2 遞歸算法示例例1-2 逆序輸出正整數(shù)的各位數(shù) 【程序1-5】 void PrintDigit(unsigned int n) cout=10) PrintDigit(n/10); /以逆序輸出前k-1位數(shù) 第1章 算法問題求解基礎(chǔ)例1-3 漢諾塔問題（tower of Hanoi）假定有三個塔座：X

16、，Y，Z，在塔座X上有n個直徑大小各不相同，按圓盤大小從小到大編號為1，2，n的圓盤。現(xiàn)要求將X塔座上n個圓盤移到塔座Y上，并仍按同樣順序疊排。 圓盤移動時必須遵循下列規(guī)則：（1）每次只能移動一個圓盤；（2）圓盤可以加到塔座X，Y，Z中任意一個上；（3）任何時刻都不能將一個較大的圓盤放在較小的圓盤之上。30第1章 算法問題求解基礎(chǔ)31第1章 算法問題求解基礎(chǔ)漢諾塔的遞歸思想假設(shè)有 n 個圓盤，三根相鄰的柱子標(biāo)號為 A，B，C，并且 A 柱上圓盤由小到大依次編號為1，2，n?，F(xiàn)要把按金字塔狀疊放著 n 個不同大小的圓盤，一個一個移動到柱子 C 上。當(dāng)只有一個盤子時，即 n=1，則只需經(jīng)過一次移動

17、將盤子從 A 柱到 C 柱；當(dāng) n1 時可以把最上面 n-1個圓盤看作是一個整體。這樣 n 個圓盤就分成了兩部分：上面 n-1 個圓盤和最下面的 1 個圓盤。32第1章 算法問題求解基礎(chǔ)示例：三個盤子的過程33ABC初始狀態(tài)第1章 算法問題求解基礎(chǔ)34第1步: A-CABC第1章 算法問題求解基礎(chǔ)35第2步: A-BABC第1章 算法問題求解基礎(chǔ)36第3步: C-BABC第1章 算法問題求解基礎(chǔ)37第4步: A-CABC第1章 算法問題求解基礎(chǔ)38第5步: B-AABC第1章 算法問題求解基礎(chǔ)39第6步: B-CABC第1章 算法問題求解基礎(chǔ)40第7步: A-CABC第1章 算法問題求解基礎(chǔ)41【程序1-6】 漢諾塔問題enum tower A=X, B=Y, C=Z;void Move(int n,tower x,tower y) /將第n個圓盤從塔座x移到塔座y的頂部cout The disk n is moved from char(x) to top of tower char(y) endl; void Hanoi(int n, tower x, tower y, tower z)/將x上部的n個圓盤移到y(tǒng)上，順序不