第一章 算法問題求解基礎

算法分析與設計

主講：徐曉蓉

計算機科學與技術學院學習算法的必要性及目的

算法是計算機科學的基礎,更是程序的基石,為了成為訓練有素的軟件人才,必須有良好的算法基礎。

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

簡單的說,學習算法,就是為了掌握并靈活運用已有的算法策略解決實際問題,并設計新的更有效的新算法。教材、參考書與課時安排教材

算法設計與分析--C++語言描述

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

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

學習態(tài)度+

課堂考勤+

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

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

輸出：算法產生至少一個量作為輸出。

確定性：算法的每個步驟必須有明確的意義,對每種可能的情況,算法都要給出確定的操作.能行性:算法的每一條指令必須能夠實現(xiàn)，算法執(zhí)行結果要達到預期的目的;有限性：算法必須在執(zhí)行有窮個指令后終止，并且每條指令都在執(zhí)行有限時間后結束。算法的三個要素：1).數據:

運算序列中作為運算對象和結果的數據.2).運算:

運算序列中的各種運算:賦值,算術和邏輯運算3).控制和轉移:

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

a>=b輸入a,b,cmax=a真假max=bmax>=c真假輸出max輸出c開始結束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；自然語言描述: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++語言描述偽代碼描述:舉例:計算寫出其算法

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

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

尋找一種方法來實現(xiàn)目標.問題求解過程:

是人們通過使用問題領域知識來理解和定義問題，并憑借自身的經驗和知識去選擇和使用適當的問題求解策略、技術和工具,將一個問題描述轉換成問題解的過程。1.2.2問題求解過程問題求解的四步法簡述如下:理解問題設計方案實現(xiàn)方案回顧復查1.2問題求解方法1.2.3系統(tǒng)生命周期

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

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

基礎情況(邊界條件):列舉新事物的若干簡單對象兩個基本要素：

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

重點掌握遞歸算法的設計方法.例1-2逆序輸出正整數的各位數

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

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

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

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

{if(n==1)move(x,1,z);/*將編號為1的圓盤從X移動Z*/elseif(n>1){hanoi(n-1,x,z,y);/*將X上編號為1至n-1的圓盤移到Y,Z作輔助塔*/move(x,n,z);/*將編號為n的圓盤從X移到Z*/

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

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

n*(n-1)!