【正文】 最為常用？ ? 算法與算法策略有何區(qū)別？ ? 哪些基本的算法策略在各種算法解決方案中被普遍采用 ? 12 基本算法 ? 蠻力法 ? 分段函數(shù) ? 遞推法 ? 模運算 ? 字符和字符串運算 ? 遞歸 ? 組合計算 ? 迭代法 13 蠻力法 ? 計算機問題求解的第一號方法被稱為蠻力法 (Brute Force) ，也稱窮舉法 ? 采用蠻力算法解題的基本思路： ? 確定窮舉對象、窮舉范圍和判定條件； ? 一一窮舉可能的解，驗證是否是問題的解 ? 在蠻力算法中，窮舉 對象的選擇 也是非常重要的，它直接影響著算法的時間復雜度，選擇適當?shù)母F舉對象可以獲得更高的效率 14 百錢買百雞問題 ? 某個人有一百塊錢，打算買一百只雞。 4. 算法程序?qū)τ诰倪x擇的，甚至刁難的測試數(shù)據(jù)都有滿足要求的輸出結(jié)果。 2. 算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果 ?；舅惴ê筒呗? 西安交大 《可視化計算》 學習目標 ? 程序與算法有哪些異同 ? ? 算法有哪些基本特性？ ? 算法的效率如何度量？ ? 如何為算法設計做準備？ 2 算法定義 ? 算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。 ? 通俗來說，就是通過計算來解決問題的過程，在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法 ? 不同的是：前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法 ? 所以， 程序是使用計算機實現(xiàn)的算法 ；而 算法則不一定需要有計算機 才能實現(xiàn) 3 算法的特性 ? 算法具有五個基本特性： ? 輸入 （ 具有 零個 或多個輸入 ） ? 輸出 （ 一或多 個輸出） ? 有窮性 （ 自動結(jié)束 而不會出現(xiàn)無限循環(huán) ） ? 確定性 （ 每一步驟的含義， 不會 出現(xiàn)二義性 ） ? 可行性 （ 能夠通過執(zhí)行 有限次數(shù) 完成 ） 4 算法設計的要求 ? 正確性 ? 可讀性 ? 健壯性 ? 時間效率高 ? 存儲量需求低 5 正確性 的層次 1. 算法程序沒有語法錯誤 。 3. 算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果 。 6 可讀性 ? 為了便于閱讀、理解和交流 ， 可讀性 要素： ? 增加算法文件名、子圖、子程序、算法樣本數(shù)據(jù)文件名的可讀性； ? 在算法語句中增加注 釋 語句，說明重要變量、決策語句的用途； ? 將算法有關的文檔整理在一個目錄中 7 健壯性 ? 能對輸入數(shù)據(jù)不合法的情況做合適的處理 ? 比如輸入的時間或者距離不應該是負數(shù) ? 算法的健壯性表現(xiàn)在當輸入數(shù)據(jù)不合法時，算法也能做出相關處理，而不是產(chǎn)生異?；驘o法解釋的結(jié)果 8 時間效率高和存儲量需求低 ? 對于同一個問題，如果有多個算法能夠達到同樣的問題解決標準，執(zhí)行時間最短的算法效率最高 ? 存儲量需求指的是算法在執(zhí)行過程中需要的最大存儲空間，主要指算法程序運行時所占用的內(nèi)存或外部硬盤存儲空間 ，越少越好 9 算法效率的度量 ? 一個用高級程序語言編寫的程序在計算機上運行時所消耗的時間取決于下列因素 ： 1. 編譯產(chǎn)生的代碼質(zhì)量 ； 2. 算法采用的策略、方法 ； 3. 問題的輸入規(guī)模 ； 4. 機器執(zhí)行指令的速度。到市場上一看，公雞五塊錢一只，母雞三塊錢一只，小雞一塊錢三只。 19 階梯電價流程圖 20 分段函數(shù)求解中的 問題 ? 最常見 的 錯 誤 的是將函數(shù)的數(shù)學表達式直接搬到算法中，例如：“ 0=x=100” ； ? 函數(shù)定義中，沒有定義 x0，也就是輸入為負數(shù) 的時候，如何處理。 ? 算法中加入了輸入數(shù)據(jù)的正確性控制，也就是不可以輸入 0和負數(shù) 26 模運算 ? 在算法應用中，有一類計算與模運算（求除法之余數(shù)）有關 ， 例如 ： ? 一個星期的模為 7天 ? 一天的模是 24小時或 1440分鐘 ? 一年的模是 12個月（也可以是 365或 366天） ? 而模運算在數(shù)字比較和諸多計算案例中有應用 27 求 100~1000范圍內(nèi)的平方回數(shù) ? 所謂平方回數(shù)，是指某個數(shù)，既是一個回文數(shù)，又是一個平方數(shù)， ? 例如： 121是回文數(shù)，又是 11的平方 28 模運算 求解分析 ? 一個 100以上的平方數(shù)，必須從平方根大于等于 10的數(shù)字開始計算，而 1000可以作為搜索循環(huán)的控制變量 ? 但是，如何求出回文數(shù)？ ? 由于是在三位數(shù)中求回文數(shù)，也就是要求個位與百位上相等 ? 這個時候，模（在 RAPTOR中模運算符： mod）運算就可以派上用場 29 求平方回數(shù)流程圖 ? 請思考一下，這個算法還使用了其他什么算法思想？ 30 字符和字符串運算 ? 字符和字符串運算在算法中的用途有： ? 在輸入輸出界面中的應用，如在輸出過程中將計算結(jié)果與量綱結(jié)合在一起； ? 在信息安全中的應用，如信息的加密與解密； ? 對用戶對特定應用的輸入的字符串，進行模式正確性的判斷（如電子郵件地址需包含“ ”符號）等 31 替換加密 ? 試用以下 替 換碼表，實現(xiàn)通信過程的加密 ? 明碼表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ? 密碼表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M 32 替換加密 ? Ａ []保存 明文 ? Key[]保存 密碼表 ? B[]保存 密文 ? 解密算法，自行設計 33 遞歸 ? 在數(shù)學和計算機科學中，遞歸是指由一種（或多種）簡單的 基線條件 (Base case)定義的一類對象或方法，并規(guī)定其他所有情況都能被還原為其 基線條件 ? 具體表現(xiàn)為： 一個函數(shù)在其定義或說明中有直接或間接調(diào)用自身 ： ? 把一個大型復雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解 ? 遞歸策略只需少量的程序就可描述出解題過程 34 遞歸過程 ? 一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段 ? 當邊界條件不滿足時，遞歸前進； ? 當邊界條件滿足時，遞歸返回 ? 一般遞歸過程需要通過函數(shù)或 子程序 傳遞參數(shù) ? 而 RAPTOR中要實現(xiàn)子程序的參數(shù)調(diào)用，必須使用其所謂的“中級模式（ Intermediate mode）” 35 遞歸算法常用于解決三類問題 (1)數(shù)據(jù)的定義是按遞歸定義的 (2)問題解法按遞歸算法實現(xiàn) (3)數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的 ? 典型的遞歸算法 (帶參數(shù)傳遞實現(xiàn) )的運行效率較低 ? 在遞歸調(diào)用的過程當中系統(tǒng)為每一層的返回點、局部變量等開辟了棧來存儲 ? 遞歸次數(shù)過多容易造成棧溢出等 問題 36 遞歸算法 ? 理論上而言，所有遞歸算法都可以用非遞歸算法來實現(xiàn) ? 遞歸的應用： ? 遞歸是很好的求解問題的方法 ，可以很好的描述一個算法的原理 ? 但是在算法實現(xiàn)中，必須避免“ 天真的遞歸 ” 37 漢諾塔 ? 有 A、 B、 C三根柱子。 fib(1)=1。 ? 這種使用遞歸的方式，被稱為“ 天真的遞歸（Naive recursion） ”。尋找表示所有素數(shù)的 素數(shù)通項公式 ，或者叫素數(shù)普遍公式，是古典數(shù)論最主要的問題之一 ? 加法、減法和乘法這三種運算，在整數(shù)范圍內(nèi)可以毫無阻礙地進行 ? 整數(shù)之間的除法 在整數(shù)范圍內(nèi)并不一定能夠無阻礙地進行 ? 大數(shù)密碼體系 ，至今仍然關系著國家的安全 45 測素子程序 ? 測素子程序是解決數(shù)論問題的核心，所以在數(shù)論應用算法中，幾乎都要用到。這些是關于 排列 、 組合 和整數(shù)分拆問題的求解，屬于組合數(shù)學研究的范疇 ? 例如，求解從 n個元素中取出 m個元素的不同組合，用 C(n,m)表示。 ? 使用二維數(shù)組 a[]，保存數(shù)字三角形的所有數(shù)據(jù) ? 二維數(shù)組的大小為 N*N，當然，其中有一半的元素為空值 0。 ? 使用回溯算法，決策樹的建樹過程為： 深度有限，左側(cè)優(yōu)先 ，左側(cè)分支不取東西， 右側(cè)取當前物件 01背包問題求解 （ 3， 5， 0） （ 2， 3， 8） （ 2， 5， 0） （ 1， 2， 7） （ 1， 5， 0） （ 1， 3， 8） i：紅色， 表示物品的編號 aw：綠色，當前可用空間 V：藍色，當前物品價值 （ 1， 0， 15） （ ， 3， 8） （ ， 5， 0） （ ， 0， 9） （ ， 2， 7） （ ， 3， 16） （ ， 2， 17） 77 k元組的概念 ? 元組 (tuple)是一種有窮序列， k個元素的序列稱為 k元組。 ? 自己用棧模擬系統(tǒng)的運行棧，通過分析只保存必須保存的信息，從而用非遞歸算法替代遞歸算法 ? 利用棧保存參數(shù)，由于棧的后進先出特性吻合遞歸算法的執(zhí)行過程，因而可以用非遞歸算法替代遞歸算法 92 使用非遞歸方法實現(xiàn)漢諾塔算法 93 算法說明 ? 將三個柱子分別命名為 na1， na2， na3，初始狀態(tài)，所有的盤子都在 na1上，三個柱子按逆時針方向排列成一個圓環(huán) ? 其中存在一個規(guī)律，當對于規(guī)模為 n的漢諾塔問題時： ? 1．奇數(shù)編號盤子總是移動移動到它后的第 2個柱子上； ? 2．偶數(shù)編號的盤子總是移動移動到它的后第 1個柱子上 94 基本算法策略的討論 ? 最優(yōu)化和非最優(yōu)化 ： ? 什么不去追求最優(yōu)化的解？ ? 因為 存在一個解空間的規(guī)模問題，如果在規(guī)定時間里，可以找到所有的解，那么選出其中的最優(yōu)解； ? 但是，如果不可能（有許多 O(2n） 以上時間復雜度的問題 )，那么，只好退而求其次，用次優(yōu)解來解決問題 ? 而貪心策略就是求次優(yōu)解的常用思 95 基本算法策略的討論 ? 時間換空間（或空間換時間） ? 大部分遞歸算法編寫簡單，但運行的時間會隨著問題規(guī)模的增長而急劇增長 ? 而分治方法，一般要花費較多的時間將問題劃分成為較小規(guī)模，增加了程序的復雜性；遞歸程序的非傳參實現(xiàn)，也是如此 ? 但較為復雜的算法，卻換來幾何級數(shù)的運行時間節(jié)省 96 基本算法策略的討論 ? 回溯策略 所解的一些問題往往是不能用數(shù)學公式去直接求解的 ? 它需要通過一個過程，此過程要經(jīng)過若干個步驟才能完成，每一個步驟又分為若干種可能； ? 同時，為了完成任務，還必須遵守一些規(guī)則和約束 ； ? 對于這樣一類問題，一般采用搜索的方法來解決，回溯法就是搜索算法中的一種控制策略，它能夠解決許多搜索中問題 97 基本算法策略的討論 ? 使用遞歸算法的思路分析問題，但用非遞歸算法解決問題。s problem