第一章 算法問(wèn)題求解基礎(chǔ)

算法分析與設(shè)計(jì)

主講：徐曉蓉

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院學(xué)習(xí)算法的必要性及目的

算法是計(jì)算機(jī)科學(xué)的基礎(chǔ),更是程序的基石,為了成為訓(xùn)練有素的軟件人才,必須有良好的算法基礎(chǔ)。

哈雷爾在他的<算法學(xué)—計(jì)算的靈魂>一書(shū)中說(shuō):”算法不僅是計(jì)算機(jī)學(xué)科的一個(gè)分支，它更是計(jì)算機(jī)科學(xué)的核心,而且可以毫不夸張地說(shuō),它和絕大多數(shù)科學(xué)、商業(yè)和技術(shù)都是相關(guān)的”

簡(jiǎn)單的說(shuō),學(xué)習(xí)算法,就是為了掌握并靈活運(yùn)用已有的算法策略解決實(shí)際問(wèn)題,并設(shè)計(jì)新的更有效的新算法。教材、參考書(shū)與課時(shí)安排教材

算法設(shè)計(jì)與分析--C++語(yǔ)言描述

陳慧南電子工業(yè)出版社參考書(shū)蘇德富主編,《計(jì)算機(jī)算法設(shè)計(jì)與分析》,電子工業(yè)出版社,2000年6月；王曉東主編,《計(jì)算機(jī)算法設(shè)計(jì)與分析》(第2版),電子工業(yè)出版社，2004年7月；盧開(kāi)澄主編清華大學(xué)出版社出版的《計(jì)算機(jī)指導(dǎo)引論－設(shè)計(jì)與分析》ThomasH.CormenCharlesE.Leiserson《算法導(dǎo)論（第2版）》,高等教育出版社，2002課時(shí)安排授課：48學(xué)時(shí)實(shí)驗(yàn)：

10學(xué)時(shí)(1次/周)課程的教學(xué)任務(wù)和目標(biāo)學(xué)習(xí)并掌握各種基本的算法設(shè)計(jì)策略。學(xué)習(xí)算法分析的基本方法。學(xué)習(xí)用基本的算法設(shè)計(jì)策略解決實(shí)際問(wèn)題的方法.通過(guò)對(duì)常用的、有代表性的算法的學(xué)習(xí)研究，讓學(xué)生理解并掌握算法設(shè)計(jì)的基本技術(shù)。培養(yǎng)學(xué)生分析算法復(fù)雜度的初步能力，鍛煉其邏輯思維能力和想象力，并使之了解算法理論的發(fā)展。使學(xué)生掌握算法設(shè)計(jì)過(guò)程與方法，并學(xué)會(huì)用所學(xué)知識(shí)解決實(shí)際問(wèn)題,培養(yǎng)他們的獨(dú)立科研的能力和理論聯(lián)系實(shí)踐的能力。主要教學(xué)內(nèi)容第一章算法問(wèn)題求解基礎(chǔ)第二章算法分析基礎(chǔ)第五章分治法第六章貪心法第七章動(dòng)態(tài)規(guī)劃法第八章回溯法第九章分枝限界法第十章NP完全問(wèn)題課程的基本要求課前做好充分的預(yù)習(xí)保持課堂安靜，頭腦清醒，思維活躍重視上機(jī)實(shí)踐，有效利用寶貴的上機(jī)時(shí)間,做到上機(jī)前事先對(duì)實(shí)驗(yàn)題目進(jìn)行預(yù)習(xí)、分析并寫(xiě)出代碼.課后認(rèn)真、獨(dú)立、按時(shí)完成并提交作業(yè).本課程平時(shí)分?jǐn)?shù)的組成平時(shí)分=

學(xué)習(xí)態(tài)度+

課堂考勤+

平時(shí)作業(yè)第一章算法問(wèn)題求解基礎(chǔ)算法概述問(wèn)題求解方法算法設(shè)計(jì)與分析遞歸和歸納第一講算法概述及算法設(shè)計(jì)與分析教學(xué)目的：1、理解并掌握算法的概念；2、理解問(wèn)題求解的方法；2、理解用算法求解問(wèn)題的過(guò)程。教學(xué)內(nèi)容：算法的概念，算法與程序的區(qū)別與聯(lián)系、問(wèn)題求解的過(guò)程和方法、用算法求解問(wèn)題的過(guò)程。.教學(xué)重點(diǎn)：算法的概念、算法與程序的區(qū)別與聯(lián)系、用算法求解問(wèn)題的過(guò)程。擬教課時(shí)：2（理論）教學(xué)過(guò)程：

1.1算法概述算法的概念:是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。算法的特征：輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。

輸出：算法產(chǎn)生至少一個(gè)量作為輸出。

確定性：算法的每個(gè)步驟必須有明確的意義,對(duì)每種可能的情況,算法都要給出確定的操作.能行性:算法的每一條指令必須能夠?qū)崿F(xiàn)，算法執(zhí)行結(jié)果要達(dá)到預(yù)期的目的;有限性：算法必須在執(zhí)行有窮個(gè)指令后終止，并且每條指令都在執(zhí)行有限時(shí)間后結(jié)束。算法的三個(gè)要素：1).數(shù)據(jù):

運(yùn)算序列中作為運(yùn)算對(duì)象和結(jié)果的數(shù)據(jù).2).運(yùn)算:

運(yùn)算序列中的各種運(yùn)算:賦值,算術(shù)和邏輯運(yùn)算3).控制和轉(zhuǎn)移:

運(yùn)算序列中的控制和轉(zhuǎn)移.1.1算法概述算法的分類:從解法上從處理方式上從解的精確程度上算法的描述方法：自然語(yǔ)言描述(但不夠嚴(yán)謹(jǐn))流程圖(早期)和N-S圖（對(duì)于復(fù)雜算法，難于建圖和理解）偽代碼(比自然語(yǔ)言精確，比程序設(shè)計(jì)語(yǔ)言簡(jiǎn)潔)高級(jí)程序設(shè)計(jì)語(yǔ)言(描述精確,但一般細(xì)節(jié)較多)—程序數(shù)值型算法:算法中的基本運(yùn)算為算術(shù)運(yùn)算.非數(shù)值型算法:算法中的基本運(yùn)算為邏輯運(yùn)算.串行算法:串行計(jì)算機(jī)上執(zhí)行的算法.并行算法:并行計(jì)算機(jī)上執(zhí)行的算法.精確算法:能夠得到問(wèn)題的精確解的算法.近似算法:只能得到問(wèn)題的近似解的算法.舉例:從三個(gè)數(shù)a,b,c中取最大數(shù)流程圖描述N-S描述:

a>=b輸入a,b,cmax=a真假max=bmax>=c真假輸出max輸出c開(kāi)始結(jié)束a>=bmax=amax=b輸入a，b，c假真max>=c輸出max輸出c真假輸入a,b,c；If(a>=b)max=a;elsemax=bif(max<=c)max=c;輸出max；自然語(yǔ)言描述:1,輸入a,b,c2,將a和b中最大者賦值給變量max;3,將max與c比較,將兩者中的大者賦值給max;4,輸出max的值.1.1算法概述main(){inta,b,c,max；cin>>a>>b>>c;if(a>=b)max=a;elsemax=bif(max<=c)max=c;cout<<max；}C++語(yǔ)言描述偽代碼描述:舉例:計(jì)算寫(xiě)出其算法

流程圖描述開(kāi)始0->s1->is+i->si+1->Ii<=100？輸出s結(jié)束TN-S描述:0->s1->ii<=100?s+i->si+1->i輸出s的值0s1->iifi<=100s+i->si+1->Iprints自然語(yǔ)言描述:1,0s2,1->I3,s+i->s4,i+1->I5,判斷i<=100是，轉(zhuǎn)3，否則轉(zhuǎn)66,輸出s的值1.1算法概述偽代碼描述:main(){inti,s=0;for(i=1;i<=100;i++)s=s+i;cout<<s;}C++語(yǔ)言描述1.1算法概述程序的概念:

當(dāng)一個(gè)算法用某種程序設(shè)計(jì)語(yǔ)言來(lái)描述時(shí)，得到的就是程序，也就是說(shuō),程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn).程序與算法的區(qū)別：算法必須可以終止;程序則可以不滿足算法的有限性,如操作系統(tǒng)程序，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。C++語(yǔ)言的特點(diǎn)：C++語(yǔ)言,類型豐富,語(yǔ)言精練,具有面向?qū)ο蠛兔嫦蜻^(guò)程的雙重優(yōu)點(diǎn).C++語(yǔ)言既能描述算法所處理的數(shù)據(jù)結(jié)構(gòu),又能描述算法過(guò)程.用C++來(lái)描述算法可使整個(gè)算法結(jié)構(gòu)緊湊、簡(jiǎn)潔明了可讀性強(qiáng).1.2問(wèn)題求解方法1.2.1問(wèn)題和問(wèn)題求解問(wèn)題:當(dāng)前狀況與目標(biāo)不一致時(shí)就會(huì)產(chǎn)生問(wèn)題問(wèn)題求解:

尋找一種方法來(lái)實(shí)現(xiàn)目標(biāo).問(wèn)題求解過(guò)程:

是人們通過(guò)使用問(wèn)題領(lǐng)域知識(shí)來(lái)理解和定義問(wèn)題，并憑借自身的經(jīng)驗(yàn)和知識(shí)去選擇和使用適當(dāng)?shù)膯?wèn)題求解策略、技術(shù)和工具,將一個(gè)問(wèn)題描述轉(zhuǎn)換成問(wèn)題解的過(guò)程。1.2.2問(wèn)題求解過(guò)程問(wèn)題求解的四步法簡(jiǎn)述如下:理解問(wèn)題設(shè)計(jì)方案實(shí)現(xiàn)方案回顧復(fù)查1.2問(wèn)題求解方法1.2.3系統(tǒng)生命周期

計(jì)算機(jī)求解問(wèn)題的過(guò)程就是一個(gè)計(jì)算機(jī)軟件的開(kāi)發(fā)過(guò)程，被稱為軟件生命周期或系統(tǒng)生命周期。軟件生命周期可劃分為如下5個(gè)階段:分析設(shè)計(jì)編碼測(cè)試維護(hù)開(kāi)發(fā)期運(yùn)行期1.3算法設(shè)計(jì)與分析1.3.1算法問(wèn)題求解過(guò)程證明正確性分析算法設(shè)計(jì)程序理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法1.3.2如何設(shè)計(jì)算法學(xué)習(xí)一些基本的算法設(shè)計(jì)策略.分析問(wèn)題的特性,當(dāng)該問(wèn)題的特性符合于某種算法設(shè)計(jì)策略處理的問(wèn)題特性時(shí),就可使用該算法設(shè)計(jì)策略設(shè)計(jì)算法,求解問(wèn)題.1.3算法設(shè)計(jì)與分析1.3.3如何確認(rèn)算法（正確性）算法的正確性的定義:在給定有效輸入后,算法經(jīng)過(guò)有限時(shí)間的計(jì)算并產(chǎn)生正確的答案,就稱算法是正確的。正確性證明的目的:確認(rèn)一個(gè)算法能正確無(wú)誤的工作.正確性證明的內(nèi)容:方法的正確性證明——算法思路的正確性.證明一系列與算法的工作對(duì)象有關(guān)的引理、定理以及公式。程序的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。程序正確性證明的方法：大型程序—將其分解為小的相互獨(dú)立的互不相交的模塊,分別驗(yàn)證。小模塊程序—可以使用以下方法驗(yàn)證:數(shù)學(xué)歸納法,軟件形式方法等。1.3算法設(shè)計(jì)與分析1.3.3如何確認(rèn)算法（正確性）程序排錯(cuò)的方法程序測(cè)試定義:指對(duì)程序模塊或程序總體，輸入事先準(zhǔn)備好的樣本數(shù)據(jù)，檢查該程序的輸出，來(lái)發(fā)現(xiàn)程序存在的錯(cuò)誤及判定程序是否滿足其設(shè)計(jì)要求的一項(xiàng)積極活動(dòng)目的:發(fā)現(xiàn)錯(cuò)誤調(diào)試定義:診斷和糾正錯(cuò)誤的過(guò)程1.3.4如何分析算法算法分析主要是指對(duì)算法的執(zhí)行時(shí)間和所需空間的估算.小結(jié)

本次課我們主要講解了有關(guān)算法的一些概念,算法求解問(wèn)題的過(guò)程,主要理解掌握算法的概念,算法與程序之間的區(qū)別。第二講遞歸和歸納教學(xué)目的：1、理解遞歸的概念；2、理解并掌握遞歸的求解問(wèn)題的思想；教學(xué)內(nèi)容：遞歸的概念，遞歸定義中的兩個(gè)要素,遞歸算法舉例，遞歸算法正確性的歸納證明.教學(xué)重點(diǎn)：遞歸的思想。教學(xué)難點(diǎn)：遞歸的思想。擬教課時(shí)：2（理論）教學(xué)過(guò)程：1.4遞歸和歸納什么是歸納？通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。什么是遞歸？它是一個(gè)數(shù)學(xué)概念，也是一種程序設(shè)計(jì)的方法它是一種直接或間接調(diào)用自身的技術(shù)，如老和尚給小和尚講故事。1.4.1遞歸定義：直接或間接引用自身的技術(shù)本質(zhì)：是一種循環(huán)結(jié)構(gòu),如老和尚給小和尚講故事.它通常是把“較復(fù)雜”的計(jì)算逐次歸結(jié)為“較簡(jiǎn)單”的計(jì)算,直至歸結(jié)到“最簡(jiǎn)單”的計(jì)算,并最終得到計(jì)算結(jié)果為止.如n!的遞歸計(jì)算。1.4遞歸和歸納遞歸求解問(wèn)題的過(guò)程:類似于使用一本大詞典查詢一個(gè)單詞的情形.如遞歸定義：是一種直接或間接引用自身的定義方法。

基礎(chǔ)情況(邊界條件):列舉新事物的若干簡(jiǎn)單對(duì)象兩個(gè)基本要素：

遞歸部分:給出簡(jiǎn)單對(duì)象定義新對(duì)象的條件和方法例:階乘函數(shù)、斐波那契數(shù)列注意：只有具備這兩個(gè)要素，才能在有限次計(jì)算后得到結(jié)果，否則，將會(huì)無(wú)限循環(huán)1.4遞歸和歸納longFib(intn){if(n<=1)return1;elsereturnFib(n-2)+Fib(n-1);}遞歸調(diào)用：在函數(shù)體內(nèi)調(diào)用自己的做法稱為遞歸調(diào)用遞歸函數(shù)定義:包含遞歸調(diào)用的函數(shù).種類:直接遞歸、間接遞歸遞歸算法（函數(shù)）定義:直接或間接調(diào)用自身的算法，稱為遞歸算法。Fib()函數(shù)的執(zhí)行過(guò)程：Fib(4)Fib(3)Fib(2)Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)遞歸樹(shù)：用以描述某一遞歸函數(shù)在執(zhí)行過(guò)程中的調(diào)用關(guān)系的樹(shù),稱為關(guān)系樹(shù).1.4遞歸和歸納1.4.2遞歸算法示例

重點(diǎn)掌握遞歸算法的設(shè)計(jì)方法.例1-2逆序輸出正整數(shù)的各位數(shù)

設(shè)有正整數(shù)n=12345,要求以各位數(shù)的逆序形式輸出,即輸出54321。設(shè)k位正整數(shù)為d1d2…dk,為了以逆序形式輸出各位數(shù)dkdk-1…d2d1,可以分成兩步:(1)首先輸出末位數(shù)dk;(2)如果k>1(即n>=10),則再輸出由前k-1位組成的正整數(shù)d1d2…dk-1的逆序形式.voidPrintDigit(unsignedintn){cout<<n%10;if(n>=10)PrintDigit(n/10);}1.4遞歸和歸納例1-3漢諾塔問(wèn)題

假定有三個(gè)塔座:X,Y,Z,在塔座X上有n個(gè)直徑大小各不相同的圓盤(pán)，現(xiàn)要求依據(jù)如下原則，將此n個(gè)圓盤(pán)從X移到Z塔座:(1)每次只能移動(dòng)一個(gè)盤(pán)子;(2)盤(pán)子可以放在任意一個(gè)塔座上;(3)任意時(shí)刻任意塔座都不能允許有大壓小的情況.

移動(dòng)過(guò)程可描述如下:(1)以塔座Z為中介，將前n-1個(gè)圓盤(pán)從X->Y;(2)將第n個(gè)圓盤(pán)移到塔座Z;(3)以塔座X為中介，將前n-1個(gè)圓盤(pán)從Y->Z.voidmove(charx,intn,chary){cout<<“Thedisk”<<n<<“ismovedfrom”<<x<<“totopoftower”<<y<<endl;}voidhanoi(intn,charx,chary,charz)

/*將塔座X上按直徑由小到大且至上而下編號(hào)為1至n的n個(gè)圓盤(pán)按規(guī)則搬到塔座Z上，Y可用作輔助塔座*/

{if(n==1)move(x,1,z);/*將編號(hào)為1的圓盤(pán)從X移動(dòng)Z*/elseif(n>1){hanoi(n-1,x,z,y);/*將X上編號(hào)為1至n-1的圓盤(pán)移到Y(jié),Z作輔助塔*/move(x,n,z);/*將編號(hào)為n的圓盤(pán)從X移到Z*/

hanoi(n-1,y,x,z);/*將Y上編號(hào)為1至n-1的圓盤(pán)移動(dòng)到Z，X作輔助塔*/}}1.4遞歸和歸納

1n=0例1-4、階乘問(wèn)題F(n)=n!=

n*(n-1)!