計算機軟件基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)之算法.ppt

第二章 算法,2.1 算法的兩要素 2.2 算法的特征 2.3 算法的表示 2.4 常用算法 2.5 算法的設(shè)計要求 2.6 算法的復(fù)雜度分析,解決問題一般步驟,實際問題-模型-算法-程序-結(jié)果 解決問題的核心 - 算法以及算法的處理對象 - 數(shù)據(jù)的結(jié)構(gòu),程序與算法,何謂算法： 解題過程的準確、完整的描述稱作解該問題的算法 何謂程序：就是用計算機語言表述的算法 流程圖就是圖形化了的算法 程序算法數(shù)據(jù)結(jié)構(gòu),2.1 算法的兩要素,算法由對數(shù)據(jù)對象的運算和操作與算法的控制結(jié)構(gòu)兩要素組成 1.算法中對數(shù)據(jù)的運算和操作 (1) 邏輯運算： “與”、“或”、“非”； (2) 算術(shù)運算： 加、減、乘、除； (3) 數(shù)據(jù)比較： 大于、小于、等于、不等于； (4) 數(shù)據(jù)傳送： 輸入、輸出、賦值。,2. 控制結(jié)構(gòu),算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次序。用流程圖 可以形象地表示出算法的控制結(jié)構(gòu) 任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三種控制結(jié)構(gòu)組合而成,2. 2 算法的基本特征,算法是由一套計算規(guī)則組成的一個過程 1.確定性 算法中每一個指令須有明確的含義，不能有二義性 2.可行性 算法中描述的操作都可實現(xiàn),執(zhí)行結(jié)果能達到預(yù)期目標 3.輸 出 每種算法必須有確定的結(jié)果，產(chǎn)生一個或多個輸出 4.輸 入 每個算法必須有0個（自動生成初始數(shù)）或多個輸入 5.有窮性 解答必須在有限步內(nèi)得到,不能出現(xiàn)“死循環(huán)” 我們可以得出如下的結(jié)論：算法是一個過程，這個過程由一套明確的規(guī)則組成，這些規(guī)則指定了一個操作的順序，以便用有限的步驟提供特定類型問題的解答。,2. 3 算法的表示,算法設(shè)計一般是由粗到細的過程，一般可以使用下面幾種類型的工具描述算法: 1.自然語言 自然語言描述算法通俗易懂，但它有著難以克服的缺陷： (1) 易產(chǎn)生歧義性 (2) 語句繁瑣冗長，很難清楚地表達算法的邏輯流程 (3) 當(dāng)今的計算機尚不能處理用自然語言表示的算法 2.專用工具 常用的有流程圖、問題分析(PAD)和NS盒圖、偽代碼等。 3.算法描述語言 為了便于轉(zhuǎn)換成某種編程語言，一般采用準程序設(shè)計語言作算法描述語言。例如，類C語言繼續(xù),流程圖 是采用不同的幾何圖形來描述算法的邏輯結(jié)構(gòu)，每個幾何圖形表示不同性質(zhì)的操作,常用流程圖符號：,返回,1.枚舉法（窮舉法）（常用） 基本思想是： 先依據(jù)題目的部分條件確定答案的大致范圍 在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完 若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解 例：百元買百雞： 公雞5元、母雞3元、小雞1元,2. 4 常用算法,2.迭代法,使一個復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復(fù)執(zhí)行過程。 基本思想：通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。 基本方法： 首先確定一個合適的迭代公式，選取一個初始近似值以及解的誤差 然后用循環(huán)處理實現(xiàn)迭代過程，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于或等于預(yù)先給定的誤差 并認為最后一次迭代得到的近似值為問題的解。 例：數(shù)值計算方法,3.遞歸法,基本思想：將復(fù)雜問題逐層分解，最后歸結(jié)為一些簡單的問題。 如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的 例：輸出自然數(shù)1到n。 #include “stdio.h” Wrt1(int n) if (n!=0) wrt1(n-1);printf(“%dn”,n)； return:; ,遞歸過程必須有一個遞歸終止條件， 當(dāng)n=0時定義為1，是階乘遞歸定義的遞歸出口,遞歸則是從函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值,4.遞推法,基本思想：從已知的初始條件出發(fā)，逐次推出所要求的中間結(jié)果和最后結(jié)果。（本質(zhì)上屬歸納法） 所謂遞推法，它的數(shù)學(xué)公式也是遞歸的。只是在實現(xiàn)計算時與遞歸相反。從給定邊界出發(fā)逐步迭代到達指定計算參數(shù)。 例：求階乘 f(n)n! n(n-1)! nf(n-1) 要計算10!，可以從遞推初始條件f(0)=1出發(fā)，應(yīng)用遞推公式f(n)=nf(n-1)逐步求出f(1)、f(2)、f(9)、最后求出f(10)的值 遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，科技計算中最常見,5.分治法,解一個復(fù)雜的問題時，盡可能地把這個問題分解為較小部分，找出各個的解，然后再把各部分的解組合成整個問題的解，這就是所謂的分治法 分治法的基本步驟 1.分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題； 2.解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題； 3.合并：將各個子問題的解合并為原問題的解。 常用于：人工智能、查找、檢索 例：將無序的N個元素按遞增次序排序（P79）,6.回溯法 基本思想： 通過對問題的分析，找出一個解決問題的線索； 然后沿著這個線索逐步試探。 若成功，就得到問題的解 若失敗，就逐步回退，換別的路線再進行試探 例：求解騎士周游（P80）、老鼠走迷宮等,迷宮求解 入口,出口,回溯法的算法：,Proc Backtracking(succ : Boolean) 確定起始狀態(tài)值走第一步 確定下一步還有幾種可能 選一可能走下一步，記住可能和本步特征 做完新一步應(yīng)做的事 While 目標未達到 do 確定下一步有幾種可能 While 沒有可能and 還有上一步 do 回退上一步 查有無下一可能 Enddo If 上一步?jīng)]有了Then return (SUCC=FALSE) EndIf 選一可能走一步，記住可能和本步特征 做完新一步應(yīng)做的事 Enddo return (SUCC=TRUE) End Backtracking,2.5 算法的設(shè)計要求,（1）正確性（Correctness） 算法應(yīng)滿足具體問題的需求。 （2）可讀性（Readability） 算法的第一目的是為了閱讀和交流 有助于對算法的理解、調(diào)試和修改。 （3）健壯性（Robustness） 算法應(yīng)具有容錯處理。 當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。 （4）高效率與低存儲量 實際問題的求解往往是求得時間和空間的統(tǒng)一、折中。,for (i=1; i=n; +i) for (j=1; j= n; +j) cij= 0; 算法時間復(fù)雜度表示為f(n) = O(n2),2.6 算法的復(fù)雜度分析,時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量 （算法中基本操作重復(fù)執(zhí)行的次數(shù)） 用“O（數(shù)量級）”來表示，稱為“階”。 常見的時間復(fù)雜度有： O（1） O（logn） O（n ） O(n2) 常數(shù)階 對數(shù)階 線性階 平方階,不同算法的時間復(fù)雜度可有不同,for (i=1; i=n; +i) for (j=1; j= n; +j) cij= 0;,空間復(fù)雜度：指執(zhí)行算法程序所需要的內(nèi)存空間、初始數(shù)據(jù)、執(zhí)行時所需額外空間 度量同時間復(fù)雜度,小結(jié),算法是由一套計算規(guī)則組成的一個過程 算法與程序的