高級算法設(shè)計與分析第一章

緒論一、課程目標：1、掌握利用程序流程圖進行算法描述；2、掌握算法分析的方法；3、學會常見算法的設(shè)計；4、了解算法優(yōu)化，并能進行簡單的優(yōu)化；二、教學與考核方式：1、時間：2014.9.18—2014.1每周四（3、4）周學時：2總學時：38

方式：課堂講授，隨堂練習2、考核：平時成績100分占30%，期末考試100分，占70%電話mail：zhouzhiguo@第一章算法概述主要內(nèi)容

計算機求解問題算法概述算法描述一、計算機求解問題

問題求解是個大課題，它涉及歸約、推斷、決策、規(guī)劃、常識推理、定理證明和相關(guān)過程的核心概念。人在解決問題時有很大的靈活性，對于同一個問題，不同的人有不同的經(jīng)驗，會采用不同的方法，怎么樣用計算機解決一個現(xiàn)實中的問題呢？雖然也是有很多不同的方法，但基本步驟是相同的。例1.1雞兔同籠問題描述：一個籠子里面關(guān)了雞和兔子（雞、兔均不缺腿多腿）。已經(jīng)知道了籠子里面腳的總數(shù)a，問籠子里面至少有多少只動物，至多有多少只動物。輸入：第1行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據(jù)占1行，包括一個正整數(shù)a(a<32768)。輸出：n行，每行輸出對應(yīng)一個輸入。輸出是兩個正整數(shù)，第一個是最少的動物數(shù)，第二個是最多的動物數(shù)，兩個正整數(shù)用空格分開。如果沒有滿足要求的情況出現(xiàn)，則輸出2個0。1.實例（1）輸出樣例：

1

2

510輸入樣例：

2 4

20題目分析題面信息現(xiàn)實知識隱藏信息（潛在信息）算法設(shè)計編碼實現(xiàn)測試1.實例（2）例1.2

問題描述：按要求輸出一個整數(shù)的每個位上的數(shù)字。輸入：每行只有一個整數(shù)a。輸出：對每個a輸出一行，按照從低位到高位的順序依次輸出a每位上的數(shù)字，數(shù)字之間用逗號隔開。1.實例（3）輸出樣例：

1hasonenumber,is1

12345havefivenumbers,are5,4,3,2,1輸入樣例：

1 12345整數(shù)范圍負數(shù)輸出格式控制1位數(shù)與多位數(shù)英文數(shù)字的處理，如five逗號處理數(shù)據(jù)測試1.實例（4）2.用計算機解決問題的基本步驟（1）問題分析（2）數(shù)學模型建立（3）算法設(shè)計與選擇（4）算法表示（5）算法分析（6）算法實現(xiàn)（7）程序調(diào)試（8）結(jié)果整理，文檔編制（1）問題分析準確、完整地理解和描述問題是解決問題的第一步。為此，必須注意以下一些問題：在原始表達中，所用的術(shù)語是否都明白其準確定義？題目提供了哪些信息？這些信息有什么用？題目要求得到什么結(jié)果？題目中作了哪些假定？是否有潛在的信息？判定求解結(jié)果所需要的中間結(jié)果有哪些？等等。必須認真審查表達問題的有關(guān)描述，深入分析，以加深對問題的了解。（2）數(shù)學模型建立用計算機解決實際問題必須有合適的數(shù)學模型，因為在現(xiàn)實問題面前，計算機是無能為力。對一個實際問題建立數(shù)學模型，可以考慮這樣兩個基本問題：最適合于此問題的數(shù)學模型是什么？是否有已經(jīng)解決了的類似問題可借鑒？如果上述第二個問題的答復(fù)是肯定的,那么通過類似問題的分析、比較和聯(lián)想，可加速問題的解決。（3）算法設(shè)計與選擇算法設(shè)計是指設(shè)計求解某一特定類型問題的一系列步驟，并且這些步驟是可以通過計算機的基本操作來實現(xiàn)的。算法設(shè)計要同時結(jié)合數(shù)據(jù)結(jié)構(gòu)的設(shè)計，簡單說數(shù)據(jù)結(jié)構(gòu)的設(shè)計就是選取存儲方式。算法的設(shè)計與模型的選擇更是密切相關(guān)的，但同一模型仍然可以有不同的算法，而且它們的有效性可能有相當大的差距。（4）算法分析算法分析的目的，首先為了對算法的某些特定輸入，估算該算法所需的內(nèi)存空間和運行時間；其次是為了建立衡量算法優(yōu)劣的標準，用以比較同一類問題的不同算法。通常將時間和空間的增長率作為衡量的標準。（5）算法表示對于復(fù)雜的問題，確定算法后可以通過圖形準確表示算法。算法的表示方式很多如：算法流程圖、盒圖、PAD圖和偽碼（類似于算法設(shè)計語言）等。（6）算法實現(xiàn)根據(jù)選用的算法設(shè)計語言，要解決下列一些問題：有哪些變量，它們是什么類型？需要多少數(shù)組，規(guī)模有多大？用什么結(jié)構(gòu)來組織數(shù)據(jù)？需要哪些子算法？等等。算法的實現(xiàn)方式，對運算速度和所需內(nèi)存容量都有很大影響。（7）程序調(diào)試算法測試的實質(zhì)是對算法應(yīng)完成任務(wù)的實驗證實，同時確定算法的使用范圍。測試方法一般有兩種：白盒測試對算法的各個分支進行測試；黑盒測試檢驗對給定的輸入是否有指定輸出。如何選擇算法測試中的輸入，通常采用的方法是，對輸入數(shù)據(jù)做有代表性的采樣，使之對被測試算法的各個語句、分支和路徑盡可能都被檢查到。對輸入集中的邊界點也要進行測試。經(jīng)測試驗證是否正確的算法，在較大程度上是可以相信它的正確性。（8）結(jié)果整理，文檔編制編制文檔的目的是讓人了解你編寫的算法。首先要把代碼編寫清楚。代碼本身就是文檔。同時還要采用注釋的方式，另外還包括算法的流程圖，自頂向下各研制階段的有關(guān)記錄，算法的正確性證明（或論述），算法測試結(jié)果，對輸入/輸出的要求及格式的詳細描述等。二、算法概述1.算法的定義算法是指在解決問題時，按照某種步驟一定可以得到問題結(jié)果的處理過程。為此需要找到用計算機解決這個問題的方法和步驟，算法就是對解決這個問題的方法和步驟的描述。算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。2.算法的要素算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)三要素組成。（1）操作算術(shù)運算：加、減、乘、除關(guān)系比較：大于、小于、等于、不等于邏輯運算：與、或、非數(shù)據(jù)傳送：輸入、輸出,賦值 （2）控制結(jié)構(gòu)——

各操作之間的執(zhí)行次序順序結(jié)構(gòu)：各操作依次執(zhí)行選擇結(jié)構(gòu)：由條件是否成立來選擇執(zhí)行循環(huán)結(jié)構(gòu)：有些操作要重復(fù)執(zhí)行，直到功能滿足某個條件時結(jié)束。又稱重復(fù)或迭代結(jié)構(gòu)。注明：模塊間的調(diào)用也是一種控制結(jié)構(gòu)，特別地模塊自身的直接或間接調(diào)用—遞歸結(jié)構(gòu)，是一種功能很強的控制結(jié)構(gòu)。（3）數(shù)據(jù)結(jié)構(gòu)算法操作的對象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)的存儲方式及處理方式就是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。它與算法設(shè)計是緊密相關(guān)的。常見的數(shù)據(jù)結(jié)構(gòu)有：線性表（數(shù)組）、堆棧、隊列、串、文件、樹、圖、集合等3.算法的基本性質(zhì)目的性算法有明確的目的，完成相應(yīng)的功能分步性算法為完成其復(fù)雜的功能，由一系列 計算機可執(zhí)行的步驟組成有序性算法的步驟是有序的，不可隨意改變算法步驟的執(zhí)行順序有限性算法是有限的指令序列，所包含步驟也是有限的操作性算法是對某些對象進行操作，使其改變4.算法的基本特征（1）有窮性一個算法在執(zhí)行有窮步之后必須結(jié)束。也就是說一個算法它所包含的計算步驟是有限的而且每個步驟都能在有限時間內(nèi)完成。（2）確定性對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。（3）可行性算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)。（4）算法有零個或多個的輸入有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。（5）算法有一個或多個的輸出它是一組與輸入有確定關(guān)系的量值，是算法進行信息加工后得到的結(jié)果。5.算法設(shè)計應(yīng)注意的問題（1）正確性一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果；典型、苛刻的幾組輸入數(shù)據(jù)也能夠得出滿足要求的結(jié)果。（2）可讀性算法應(yīng)該易于人的理解；晦澀難讀的算法易于隱藏較多錯誤而難以調(diào)試。（3）健壯性算法的異常情況。處理出錯的方法是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。

（4）高效率與低存儲量需求效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。6.算法設(shè)計的基本方法（1）結(jié)構(gòu)化方法——“自頂向下,逐步求精”

“自頂向下”是將復(fù)雜、大的問題劃分為小問題。

“逐步求精”是將現(xiàn)實世界的問題經(jīng)抽象轉(zhuǎn)化為邏輯空間或求解空間的問題。結(jié)構(gòu)算法設(shè)計技術(shù)的優(yōu)越性：①符合人類解決復(fù)雜問題的普遍規(guī)律。②用先全局后局部、先整體后細節(jié)、先抽象后具體的逐步求精過程開發(fā)出的算法有清晰的層次結(jié)構(gòu)。（2)面向?qū)ο蠓椒?/p>

對象=數(shù)據(jù)+對數(shù)據(jù)操作的代碼實體該方法的過程包括以下步驟：①在給定的抽象層次上識別類和對象②識別這些對象和類的語義③識別類和對象之間的關(guān)系④實現(xiàn)類和對象它的特征主要包括:

抽象化將各種獨立的操作分解成為可以用命名區(qū)分的單元。

封裝性不同的操作具有不同的作用范圍。

多態(tài)性對于不同數(shù)據(jù)類型的相似操作使用相同的名。

繼承性類可以被繼承。（3）課程采用結(jié)構(gòu)化設(shè)計方法自頂向下模塊化分解過程

①把一個較大的算法劃分為若干子算法②每一個模塊可繼續(xù)劃分為更小的子模塊③直到用三種控制結(jié)構(gòu)和具體操作表示算法注：運用這種編程方法，考慮問題必須先進行整體分析。模塊劃分的基本要求

①模塊的功能盡可能地單一化、明確化

②模塊間的聯(lián)系及相互影響盡可能地小

③模塊的規(guī)模應(yīng)當足夠小，以便于調(diào)試

原則是簡單性、獨立性和完整性（低耦合、高內(nèi)聚）模塊間的接口問題傳遞方式一般有以下幾種：①按名共享：全局變量②子模塊返回調(diào)用模塊信息：子模塊名③調(diào)用模塊傳遞給子模塊信息：值參數(shù)傳遞④調(diào)用模塊與子模塊互相傳遞信息：變量參數(shù)傳遞(C語言沒有此種傳遞方,Pascal、C++語言提供此類參數(shù))⑤按地址共享變量：地址參數(shù)傳遞（參數(shù)為指針變量名、數(shù)組名，變量地址）算法設(shè)計的基本方法抽象

抽象包括算法的抽象和數(shù)據(jù)抽象。算法抽象是指算法的尋求(或開發(fā))采用逐步求精、逐層分解的方法。數(shù)據(jù)抽象也指在算法抽象的過程中逐步完善數(shù)據(jù)結(jié)構(gòu)和引入新的數(shù)據(jù)及確定關(guān)于數(shù)據(jù)的操作。

枚舉“枚舉”一些真實數(shù)據(jù)歸納“歸納”出算法的細節(jié)7.從算法到實現(xiàn)從算法到實現(xiàn)應(yīng)注意的事項：數(shù)據(jù)類型的選擇計算過程 整除、優(yōu)先級結(jié)果的輸出格式

對齊、空行、空格、特定的分隔符等算法實現(xiàn)后的測試、調(diào)試（回歸測試）三、算法描述

算法是對解題過程的精確描述。算法=控制結(jié)構(gòu)+原操作表示算法的語言主要有：自然語言、流程圖、偽代碼、計算機算法設(shè)計語言等。1.自然語言自然語言是人們?nèi)粘Ｋ玫恼Z言。其缺點是：

①由于自然語言的歧義性容易導(dǎo)致算法執(zhí)行的不確定性。

②自然語言的語句一般太長從而導(dǎo)致了用自然語言描述的算法太長。

③當一個算法中循環(huán)和分支較多時就很難清晰地表示出來。

④自然語言表示的算法不便翻譯成計算機算法設(shè)計語言理解的語言。2．流程圖流程圖可以表示任何算法的邏輯結(jié)構(gòu)。

1)基本組件算法入口加工輸入條件控制流連接點和出口處理輸出2）三種基本控制結(jié)構(gòu)

①順序結(jié)構(gòu)：②選擇結(jié)構(gòu)IFTHENELSE型分支DOCASE型多分支③循環(huán)結(jié)構(gòu)DO─DOWHILE型循環(huán)DOUNTIL循環(huán)結(jié)構(gòu)3)算法流程圖的主要缺點

①

不是逐步求精的好工具，它誘使算法員過早地考慮算法的控制流程，而不去考慮算法的全局結(jié)構(gòu)。②隨意性太強，結(jié)構(gòu)化不明顯。③不易表示數(shù)據(jù)結(jié)構(gòu)。④流程圖的層次感不明顯3．盒圖（NS流程圖）

（1）盒圖具有以下優(yōu)點：

①層次感強、嵌套明確

②支持自頂向下、逐步求精。

③容易轉(zhuǎn)換成高級語言源算法AB成立不成立PABwhileP1AuntilP1A順序結(jié)構(gòu)選擇結(jié)構(gòu)當型循環(huán)結(jié)構(gòu)直到型循環(huán)（2）三種基本控制結(jié)構(gòu)（3）主要缺點：不易擴充和修改，不易描述大型復(fù)雜算法。4．PAD圖

問題分析圖(ProblemAnalysisDiagram,簡稱PAD)表示的算法是一個二維樹形結(jié)構(gòu)圖，層次感強、嵌套明確且有明確的控制流程。三種基本控制結(jié)構(gòu)①順序結(jié)構(gòu)②

選擇結(jié)構(gòu)

如果條件P成立，執(zhí)行S1當條件P的值為P1,執(zhí)行語句體S1

條件不成立，執(zhí)行S2為P2時執(zhí)行語句體A2，……

③循環(huán)結(jié)構(gòu)如果條件P成立，重復(fù)執(zhí)行S如果條件P不成立，重復(fù)執(zhí)行SPAD圖的主要優(yōu)點：①設(shè)計出來的算法必是結(jié)構(gòu)化的。

②

PAD圖描繪的算法結(jié)構(gòu)清晰。③用PAD圖表現(xiàn)的算法邏輯，易讀、易懂、記。④容易用軟件工具自動將PAD圖轉(zhuǎn)換成高級語言源算法。⑤既可用于表示算法邏輯，也可用于描繪數(shù)據(jù)結(jié)構(gòu)。⑥支持自頂向下、逐步求精。缺點：由于是圖形符號書寫、錄入不方便。例：圖3.6問題分析圖實例5．偽代碼偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法的工具。它不用圖形符號，因此書寫方便格式緊湊，易于理解，便于用計算機算法設(shè)計語言實現(xiàn)。6．算法設(shè)計語言的缺點

①算法的基本邏輯流程難于遵循與自然語言一樣，算法設(shè)計語言也是基于串行的，當算法的邏輯流程較為復(fù)雜時這個問題就變得更加嚴重②特定算法設(shè)計語言編寫的算法限制了與他人的交流，不利于問題的解決

③要花費大量的時間去熟悉和掌握某種特定的算法設(shè)計語言

④要求描述計算步驟的細節(jié)而忽視算法的本質(zhì)

⑤需要考慮語法細節(jié)，而擾亂算法設(shè)計的思路

⑥考慮到算法設(shè)計語言的不斷更新，不適于描述算法。

算法設(shè)計都不用算法設(shè)計語言直接描述。一個簡單問題的求解過程問題求解的步驟可以簡化為三步：具體（問題的現(xiàn)實領(lǐng)域）

（1）問題分析建立模型

抽象（邏輯結(jié)構(gòu)、模型建立、功能確認）（2）算法設(shè)計

具體（計算機世界）（3）算法分析

抽象（性能及算法文檔）。

數(shù)學建模是在對問題的認真分析加上必要的數(shù)學知識來確定問題的解決方法。對一般的問題，我們把這一步稱為“問題分析”，是確認問題和問題的基本運算的。運算只描述處理功能，第二步“算法設(shè)計”是對處理功能的求精，即找出問題的處理步驟。第三步“算法分析”是對數(shù)學模型的建立、數(shù)據(jù)結(jié)構(gòu)的選擇及算法設(shè)計工作的評價、總結(jié)。例1.3求二個正整數(shù)的最大公約數(shù)。問題分析：此題只需有小學知識，就可有以下建立以下的數(shù)學模型。數(shù)學模型：a，b>0的整數(shù)，求c，c能整除a，b，且a/c與b/c互質(zhì)。算法設(shè)計：這個方法首先基于人能“宏觀”地“看出”所求兩數(shù)的公約數(shù)才能繼續(xù)的。計算機雖沒有“宏觀”能力來“看出”公約數(shù)，但通過“枚舉嘗試”（逐個嘗試）就可以“試出”a,b有哪些是公約數(shù)，并將這些公約數(shù)“累乘”，就能得到最大公約數(shù)。具體算法設(shè)計：

1）用for循環(huán)枚舉可能的因數(shù)，并用變量累乘求出的因數(shù)。

2）注意到2因數(shù)在“4，8”兩個數(shù)據(jù)中出現(xiàn)兩次，所以，測試某因數(shù)是否所給數(shù)據(jù)的因數(shù)時，應(yīng)該用循環(huán)語句而不是條件語句。算法描述如下：zdgys(){inta,b,c,i;inputa,b;c=1；//變量c是為累乘因數(shù)而設(shè)置的；

for(i=2;i<=aandi<=b;i++)//“枚舉”可能的公約數(shù)

w