《智能科學(xué)技術(shù)導(dǎo)論-周昌樂-第03講 算法設(shè)計》由會員分享，可在線閱讀，更多相關(guān)《智能科學(xué)技術(shù)導(dǎo)論-周昌樂-第03講 算法設(shè)計（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第03講算法設(shè)計 導(dǎo)語 算法是智能計算領(lǐng)域最核心的概念之一。當(dāng)你擁有 了一臺機器，希望機器系統(tǒng)能夠為你服務(wù)，解決你需要 解決的某個智能計算任務(wù)，那你首先要給出完成這項任 務(wù)的算法步驟。比如，你希望具備猜?lián)淇伺祁伾@樣一 個魔術(shù)游戲的能力，那么你就需要為機器編制完成這樣 任務(wù)的算法。如果說對于計算機科學(xué)技術(shù)的學(xué)生而言， 玩的就是算法，那么對于智能科學(xué)技術(shù)的學(xué)生而言，玩 的就是智能算法！ 正是通過使用算法，可以將智慧編進機器系統(tǒng)中， 從而來構(gòu)建能夠表現(xiàn)智能行為的機器。因此，你編制的 算法越有智慧，那么所構(gòu)建的機器也就越能夠具有更智 慧的行為表現(xiàn)。從某中意義上講，機器智能的限度就是 能否找到算

2、法的限度。那些能夠找到算法的智能任務(wù)范 圍，也就是智能機器的能力范圍。 智能科學(xué)技術(shù)研究的目的，就是要找出盡可能多的 智能算法，使我們的機器擁有盡可能多的智慧能力。由 此可見，算法在智能科學(xué)與技術(shù)領(lǐng)域中的重要地位，掌 握算法設(shè)計的原理，也就成為學(xué)習(xí)這一專業(yè)的最基本技 能。 第3.1節(jié)算法概述 一般而言，所謂算法就是給出解決一個（智能）計 算問題具體步驟的集合。我們在前面'機器系統(tǒng)〃一講中 已經(jīng)遇到過一些簡單的指令執(zhí)行算法。比如中央處理機 常規(guī)處理''算法〃就是，只要未發(fā)出停機指令就執(zhí)行以下 步驟： （1）獲得指令；（2）指令解碼；（3）執(zhí)行指令。 “煮雞蛋吃”算法如下：（1）從冰箱里

3、取一枚雞 蛋；（2）將雞蛋放進煮鍋；（3）鍋里加水直到蓋滿雞 蛋；（4）持續(xù)給鍋加溫直到沸騰為止；（5）停止加溫 取出雞蛋；（6）將雞蛋放入涼水浸泡1分鐘；（7）敲 破雞蛋殼，去除全部蛋殼；（8）將去殼后的雞蛋一口 一口吃掉。 “遛小狗”算法：（1）給小狗套上狗繩，（2） 出門上路；（3）如果遇到樹小狗在逗留，則等待小狗 尿尿；（4）繼續(xù)前進，如果遛狗時間沒有達到規(guī)定的 時間，則繼續(xù)遛狗轉(zhuǎn)（3），否則返回。 “擺蓍成卦”算法：探蓍，古代問卜的一種方式， 用手抽點蓍草莖的數(shù)目，以決定吉兇禍福。其法為，大 衍之?dāng)?shù)五十，其用四十有九，分而為二以象兩，掛一以 象三，探之以四以象四時，歸奇于劫以象閏

4、，五歲再閏， 故再營而后卦。是故四營而成易（爻），十有八變而成 卦。八卦而小成，引而伸之，觸類而長探，天下之能事 畢矣。 如果強調(diào)精確性，那么實際卦象生成算法如下（重 精品文檔 復(fù)如下三變步驟之六遍，共計十八變）： （1） 大衍之?dāng)?shù)50，其用49： 50根蓍草，去其1而不用， 令可用之?dāng)?shù)s=49，余數(shù)之和t=0，循環(huán)如下操作三變： （2） 分二（分而為二以象兩）：余49根隨意分為左右 兩堆（天意） （3） 掛一（掛一以象三）：從右堆中取出1根 （4） 探四（探之以四以象四時）：對左右兩堆均以四 根一組數(shù)之，令其為新的可用之?dāng)?shù)s （5） 歸奇（歸奇于執(zhí)以象閏）：t=t+兩堆得出的余

5、數(shù) 之和 （6） （故四營而成易）：不到三變轉(zhuǎn)（2） （7） 根據(jù)y= （49-t）/4來決定一個爻畫：y=7 （少陽）、 8 （少陰）、9 （老陽）、6 （老陰） 通過上述幾個算法例子，我們不難了解算法的一些 特點。但作為機器系統(tǒng)能夠嚴格精確執(zhí)行的操作步驟集 合，我們必須對算法下一個嚴格的定義：算法是一組明 確的、可以直接執(zhí)行之步驟的有限有序集合。 （1） 有序性：算法中所有步驟均規(guī)定有執(zhí)行順序的； （2） 有限性：算法中的步驟是有限的； （3） 明確性：集合中的每條指令均是明確的、可以直 接執(zhí)行的步驟。 有時候，我們還會要求每一個算法不但構(gòu)成步驟是 有限的，而且還要求這些步

6、驟的動態(tài)執(zhí)行也是在有限時 間中能夠結(jié)束的，即所謂（4）終止性。不過，對于特 殊算法，有時候我們卻需要永不終止，如操作系統(tǒng)。關(guān) 于這個話題，更多地涉及到計算理論的內(nèi)容，并跟算法 效率的討論有關(guān)。我們不做展開了。 對于算法而言，還有一個重要的方面就是一定區(qū)分 算法內(nèi)涵與算法描述之間的區(qū)別。算法的內(nèi)涵是指一個 算法所固有的功能本質(zhì)，完成某一任務(wù)的具體步驟及其 內(nèi)在聯(lián)系。而算法的描述則是具體給出的一種表示方式。 一個算法可以有不同的描述文本，這些描述文本完成的 任務(wù)完全一致，因此代表著一個相同的抽象本質(zhì)。 就好像一本書與一個故事的區(qū)別，一個故事可以寫 成不同版本的書，而這不同版本的書卻講述的是同一

7、個 故事。算法的抽象本質(zhì)，是任務(wù)固有的復(fù)雜本性所決定 的，而算法的表示只是完成這一任務(wù)之算法的一種具體 描述。如果我們考慮到算法的執(zhí)行問題，還需要區(qū)分程 序、算法與進程三者的關(guān)系。程序是算法的描述，進程 是執(zhí)行程序的活動，而執(zhí)行一個程序就是執(zhí)行這個程序 所表達的算法，因此進程是算法執(zhí)行活動。 最后，對于算法，還要考慮算法的效率與正確性問 題。效率是指執(zhí)行一個算法所要花費的時空代價。時間 代價是指算法執(zhí)行中花消的時間，而空間代價是指算法 執(zhí)行中花消的內(nèi)存。當(dāng)然，一般我們僅僅從理論上來討 論算法的效率，并不考慮具體的機器系統(tǒng)，加上空間代 （活動1） 精品文檔 價可以轉(zhuǎn)化為時間代價。因此

8、，在考慮算法的效率時， 主要查看對于給定的輸入數(shù)據(jù)規(guī)模，一個算法需要動態(tài) 執(zhí)行多少個計算步驟，稱為算法的計算復(fù)雜性。 算法的計算復(fù)雜性是由算法所解決的問題本身的 復(fù)雜本性所決定的，這是算法問題的計算復(fù)雜性。不過， 同樣的問題可以有不同的算法來解決，這些不同算法的 計算復(fù)雜性才是反映算法效率的關(guān)鍵。我們希望，對于 給定的問題，都能夠找到最低計算復(fù)雜性的那個算法， 剛好反映了問題本身的計算復(fù)雜性。 衡量算法計算復(fù)雜性一般用輸入數(shù)據(jù)的規(guī)模來比 照，也即算法計算復(fù)雜性是其輸入數(shù)據(jù)規(guī)模的函數(shù)，通 常記為： O （f （n）） 其中n為算法輸入數(shù)據(jù)的規(guī)模，f（）為算法的計算 復(fù)雜性函數(shù)，O（）為復(fù)

9、雜性當(dāng)量。從理論上講，可以 將算法按照計算復(fù)雜性函數(shù)類別來進行分類，比如函數(shù) 為對數(shù)函數(shù)的就稱為對數(shù)復(fù)雜性，多項式的就稱多項式 復(fù)雜性（又分為k次多項式）、指數(shù)的稱為指數(shù)復(fù)雜性。 至于算法的正確性，則是要確保算法確實解決了給 定的問題。目前，證明算法正確性的方法主要有兩種途 徑：一是軟件測試途徑，就是具體地運行算法的程序， 采用各種選擇測試數(shù)據(jù)的方法來系統(tǒng)地測試軟件，分析 算法的結(jié)果是否符合規(guī)定的（中間環(huán)節(jié)或最終結(jié)果）輸 出要求；另一種是程序正確性證明方法，主要是從理論 上分析證明算法的正確性。 當(dāng)然我們希望所構(gòu)造的算法都是正確的，即確實剛 好解決了所要解決的問題，不多也不少。但實際上，當(dāng)

10、 需要解決的問題足夠復(fù)雜時，很難保證構(gòu)造的算法是正 確的，往往或存在許多漏洞（bug），常常會給各種智 能系統(tǒng)帶來災(zāi)難性的后果，比如航天飛機的發(fā)射失敗， 往往就是因為軟件算法上的一點點小問題導(dǎo)致的。因此， 算法設(shè)計也是大事，不可不慎！ 第3.2節(jié)算法構(gòu)造 構(gòu)造算法的前提，首先是要給出某種算法表示的方 式。盡管算法功能是超越具體的表達形式的，但功能總 是要通過一定的形式來呈現(xiàn)的。日常生活中我們一般采 用自然語言來發(fā)表我們的思想，也常常采用某圖式來表 達事物及其關(guān)系。但對于算法而言，由于明確性的要求， 因此往往需要某中精確的形式語言來作為算法表達的 語言，這種可以精確描述算法的形式語言就成為原

11、語。 定義原語一般包括兩個方面的考慮，語法和語義。 語法規(guī)定原語中符號組合的規(guī)則，語義則說明原語中符 號及其組塊的含義。為了既兼顧機器算法執(zhí)行的精確可 行性，又兼顧人們算法描述的直觀方便性，并且具有某 種通用性，因而可以忽略實現(xiàn)某種程序設(shè)計語言的細節(jié)， 一般采用一種稱為偽碼的符號系統(tǒng)來作為描述算法的 精品文檔 原語。 所謂偽碼（psudocode）是一種重在表達算法思想 的非正式符號系統(tǒng)，常常用在算法的開發(fā)進程之中。與 一般高級程序設(shè)計語言相比較，偽碼的主要特點是，既 具有直觀方便性的優(yōu)點，又忽略了嚴格語法的規(guī)范性。 由于算法思想主要是通過各種遞歸語義結(jié)構(gòu)來描述的， 因此與所有描述算法的

12、語言符號系統(tǒng)一樣，偽碼必須要 能夠給出各種遞歸語義結(jié)構(gòu)的表達方法。有時為了直觀 表達算法的思想，也常采用一種稱為流程圖的圖式來對 偽碼描述的算法作補充說明。］— '起/止點輸入/輸出一處理 準(zhǔn)備預(yù)定義處理 ——0 C ? 判斷 控制流 外接 內(nèi)接 流程圖的基本符號 上圖給出了流程圖的基本符號，下面我們針對主要 的遞歸語義結(jié)構(gòu)，結(jié)合流程圖表示，來給出一種算法原 語具體規(guī)范。 （1）賦值語義結(jié)構(gòu)：如果用name表示變量名稱，用 expression表示與name有關(guān)的數(shù)值表達，那么我們稱： name—expression 為一個賦值語義結(jié)構(gòu)，其含義表示“ 把expression 的

13、值賦給name”。比如： x—3+4y 就表示將3+4y表達式計算結(jié)果的值賦給x。一旦這一計 算結(jié)束后，變量x的值，就變成“3+4y” 了，但注意變 量y的值保持不變。 i 賦值語句流程圖 name—expression （2）條件語義結(jié)構(gòu)：根據(jù)某個條件式的是否成立，來 決定采取進一步的計算活動。表示這樣算法步驟的語義 結(jié)構(gòu)，就稱為條件語義結(jié)構(gòu)。一般采用如下的描述形式: if （條件）then （活動1） else （活動2） 或者 if （條件）then （活動） 其中if、then、else這些關(guān)鍵詞稱為保留詞（不允許算 法設(shè)計者用做命名變量名稱的詞，稱為保留詞），用

14、于 界定一個條件語義結(jié)構(gòu)不同部分（內(nèi)部）和作用范圍（外 部）。 在上述條件語義結(jié)構(gòu)中，第一個式子的含義表示“如 果（條件）成立，就執(zhí)行 否則執(zhí)行（活動2） ”， 第二個式子的含義 表示"如果（條件）成立， 就執(zhí)行（活動）”。比如， 精品文檔 if (xW6) then (y—x+2) else (y—x+6) 就是一個條件語義結(jié)構(gòu)。 條件語句流程圖 (3) 循環(huán)語義結(jié)構(gòu)：用來表示只要某個條件式保持為 真就繼續(xù)規(guī)定的計算活動，表示這樣的算法步驟的語義 結(jié)構(gòu)，就稱為循環(huán)語義結(jié)構(gòu)。一般采用如下的描述形式： while (條件)do (活動) 其中while和do也是保留詞。循環(huán)語義結(jié)

15、構(gòu)的含義是 “檢查(條件)是否滿足，如果其為真就執(zhí)行(活動)， 并返回再次檢查(條件)。只有當(dāng)某次檢查(條件)不 滿足時，才結(jié)束算法步驟?！?W 木 比如*初始值假定 2

16、使 得這樣的偽碼表示更加具有可讀性，一般規(guī)定語句之間 用分號隔開，如果一個語句內(nèi)部嵌有另一個語句，則采 用縮進格式。 比如語句 if (xW6) then (y—x+2) else (if (xW6) then ( y—x+2) else (y—x+6)) 寫成縮進格式就是 if (xW6) then (y—x+2) else (if (xW6) then (y—x+2) else (y—x+6) ) 進一步，對于重復(fù)出現(xiàn)的偽碼段或者相對獨立的一 段代碼，可以用固定名稱加以命名定義，稱為過程，然 后在需要出現(xiàn)的地方直接用該名稱替代這段偽瑪。一般 過程的定義方式為 proc

17、edure name (參量) 偽瑪段 引用之處直接用語句"procedure name”來替代所定義 的 這段“偽瑪段”。 過程語句流程圖L , name (參量) 精品文檔 比如下面就定義了一個稱為greetings的過程： procedure greetings (y) x—y； while (xW6) do (print ("hello”)； x—x+1) 此時，在其他需要完成這一過程功能的地方，只需 要直接調(diào)用這一過程名即可，比如 if (xW10) then (procedure greetings (3)) 有時候，為了使得偽碼可讀性更高，在嵌套的語句 中

18、，每一層語句的結(jié)束，都用明顯的標(biāo)識來醒目地加以 標(biāo)記，比如end while、end if等，使得偽碼的嵌套 層次更加一目了然。當(dāng)然，這種做法并非是強制性的， 依賴于個人偏好。作為中國人，有時也可以用漢語保留 詞來替換英語保留詞，以及只要不影響算法思想的表達， 可以采用你自己認為的習(xí)慣方式來規(guī)定你的偽碼表達 習(xí)慣，前提是要讓別人能夠理解可讀。 有了表示算法的偽碼原語，現(xiàn)在我們可以來介紹如 何編寫解決具體問題的算法了，即所謂的算法構(gòu)造。針 對某個具體需要解決的問題，算法構(gòu)造可以分為兩個階 段：發(fā)現(xiàn)解決該問題的算法，以及用偽碼將發(fā)現(xiàn)的算法 表達出來。如果你已經(jīng)熟練掌握了偽碼的使用，那么很 顯然，

19、構(gòu)造算法的重點在于發(fā)現(xiàn)算法。其實，發(fā)現(xiàn)算法 就是一個理解解決問題的過程。 從算法發(fā)現(xiàn)的角度看，可以將解決問題的一般原理 對應(yīng)到如下這樣四個階段上： 階段1理解問題 階段2尋找一個可能解決問題的算法過程(思路) 階段3闡明算法并且用程序?qū)⑵浔磉_出來 階段4從準(zhǔn)確度以及作為解決其他問題的一個工 具的潛力這兩個方面來評估這個程序。 舉個例子來說?；鸩窆饔螒?，由17跟火柴棍構(gòu)成的 一幅2X3個小方格的圖案，請你去掉其中的5跟火柴， 使得剩余的火柴棍剛好形成相互獨立的、兩兩之間沒有 公共邊的3個小方格。 火柴棍游戲 具體解決問題的思路有許多，比如正向思維、逆向 思維(均舉撲克牌游戲)、混

20、合思維以及靈機一動(三 0+1=1 a.重復(fù)地進行相加運算 1+2=3 b.本次的和作為下一次 3+=6 相加運算的被加數(shù) a.令s表示被加數(shù)（初始值為 0 ），令I(lǐng)表示加數(shù)（初始 值為1 ） 根火柴問題）等等。但對于算法發(fā)現(xiàn)而言，主要的難點 不在于去解決一個問題的特定實例，而是要找出一種適 合一個問題所有實例的一般算法。比如要給出加法運算 的一般算法，而不是僅僅解決1+1這一個加法運算的特 定實例。這時，你就會發(fā)現(xiàn)，對于給定問題，發(fā)現(xiàn)其解 決算法并非是一個容易的問題。甚至對于許多問題，根 本就不存在可以加以解決的算法，比如整數(shù)方程解的問 題。 舉例 1：計算 1

21、+2+...+100（n） 6+4=10 c?加數(shù)有規(guī)律地變化著 10+5=1 5... 4851+99=4950 4950+100=5050 b.進行100次加法后結(jié)束，或 者當(dāng)加數(shù)大于100時結(jié)束 c.S中存放計算結(jié)果 舉例 1：計算 1+2+...+100 下面的算法中S表示被加數(shù)，也表示累加和，I表示 加數(shù) 步驟 1： S - 0; I - 1 步驟2：若I小于等于100，則轉(zhuǎn)向步驟3；否則，轉(zhuǎn) 向步驟6； \ 步驟3： S - S + I; 步驟4： I - I + 1; 步驟5：轉(zhuǎn)向步驟2； \ 步驟6： S的值就是計算結(jié)果，算法結(jié)束。 ―推廣該

22、算法，即修改算法中步驟2的100為n，可得 到計算1+2+???+n的算法。 計算1+2+…+100的流程圖  S - 0 I -1+1 I S—S+I 個—Y*100? W N 輸出S的值 L ￡ I ■結(jié)束 計算1+2+…+n的流程圖 舉例1：計算1+2+???+n 構(gòu)造算法另一種思想：例如，計算1+2+...+10 0時 先計算 1 + 100, 2+99, ..., 49+52, 50+51,然后用101 X50即可得到運算結(jié)果。類推，要計算1+2+...+n，只 要知道有多少個n+1，就可以得到計算結(jié)果。 步驟 1： S — n+1 步驟2：若n

23、是偶數(shù)，則S — （S X n） ：2; 否則，S — SX （ n_1） ：2 + （n + 1） ：2 步驟3： S的值就是計算結(jié)果，算法結(jié)束。 同一個問題可用不同的方法解決，即用不同算法解 決同一個問題。因此，就存在一個算法的比較（分析）和 選擇問題，比較的依據(jù)是算法的效率。 舉例2：判斷閏年問題，給定一個年號，判斷是否是閏 年。 問題分析：能被4整除，但是不能被100整除的年份 是閏年；能同時被100和400整除的年份是閏年。 步驟1：令y表示年份，給y一個年份值； 步驟2：若y能被4整除并且不能被100整除，則轉(zhuǎn)向 步驟5；否則，轉(zhuǎn)向步驟3； 步驟3：若y能被100整

24、除并且能被400整除，則轉(zhuǎn)向 步驟5；否則，轉(zhuǎn)向步驟4； 步驟4：輸出y不是閏年，算法結(jié)束； 步驟5：輸出y是閏年，算法結(jié)束。 判斷閏年的流程圖 開始 用情況語句（選擇結(jié)構(gòu)2）。選擇結(jié)構(gòu)本身不會增加計 對于一個可以存在解決算法的問題，為了能夠找到 算復(fù)雜性，但是確實算法實現(xiàn)中非常重要的表達方式， 可以有效地解決人們思維中的選擇機制問題。 a 成立 p 不成立 A B b 選擇結(jié)構(gòu)1 成立 p 不成立 A B N-S盒圖表示 情況語句（選擇結(jié)構(gòu)2）的偽碼原語，一般定義如下: 解決的算法思路，可以通過逐步求精（stepwise refinement）方法來進行

25、。逐步求精就是通過把復(fù)雜問 題不斷分解為子問題，直到分解的子問題能夠直接給出 解決思路為止；然后再逐步將子問題的解決思路一層一 層的整合起來，最終給出總問題的解決思路。問題不斷 分解的過程稱為自上而下的分析方法，將思路不斷整合  switch （變量）（ case ''取值1〃（活動1） case ''取值2〃（活動2） case ''取值n〃（活動n） ） 的過程稱為自下而上的綜合方法。這也是編制復(fù)雜軟件其中switch、case均為保留詞。 系統(tǒng)最為常用的兩種策略，非常重要。 當(dāng)然，逐步求精不是求解問題的全部，對于給定問 題如何發(fā)現(xiàn)解決的算法，永遠是一個開放的科學(xué)難題，

26、 需要人們不斷地去探索和發(fā)展新的方法。 總之，算法發(fā)現(xiàn)是一項富有挑戰(zhàn)性的技巧性工作， 也是你們聰明才智得以展現(xiàn)的最佳場所。 算法是計算步驟的有序集合，自然構(gòu)成算法是按照 一定順序排列的語句集合（順序結(jié)構(gòu)）。在算法的語句 集合中，反映算法復(fù)雜性的主要體現(xiàn)在構(gòu)成算法的具體 語句結(jié)構(gòu)之中，主要包括選擇結(jié)構(gòu)、迭代結(jié)構(gòu)和遞歸結(jié) 構(gòu)，也是分析計算復(fù)雜性的重點所在。（N-S盒圖表示 是由美國學(xué)者Nassi和Shneiderman于1973年提出地一 種新的流程圖。） 首先是選擇結(jié)構(gòu)，在算法實現(xiàn)中需要考慮多種可能 情況的不同處理策略時，就會采用算法的選擇結(jié)構(gòu)，具 體表示一般采用條件語句（選擇結(jié)構(gòu)1）

27、，有時也會采  a 情況1 v 情況n 情況2 A B C b 選擇結(jié)構(gòu)2 比如對于給定的一個數(shù)據(jù)和一張數(shù)據(jù)表，要確定該 數(shù)據(jù)是否在這張表中，就需要構(gòu)造一個算法來解決這個 問題，這樣的算法就是數(shù)據(jù)查找算法。比如查找某個人 的姓名是否出現(xiàn)在給定的名單中，就屬于這樣一種數(shù)據(jù) 查找問題。一般實現(xiàn)這一過程的偽碼可以采取選擇結(jié)構(gòu) 來構(gòu)建。具體算法表示如下頁所示。 Procedure Search （list， TargetValue） if（list為空）then （返回失?。? else（ TestEntry—在lis t中選擇第一個表項； while （TargetVa

28、lue/TestEntry 且 TestEntry不是最后一個表項） do （TestEntry—在list中選擇下一個表項）； if （TargetValue=TestEntry） then （返回成功） else （返回失?。? ）end if 其次就是迭代結(jié)構(gòu)。在算法的迭代結(jié)構(gòu)中，一組指 精品文檔 令以循環(huán)方式重復(fù)執(zhí)行。當(dāng)然，除了 while語句外（循 環(huán)結(jié)構(gòu)1），也可以采用repeat語句（循環(huán)結(jié)構(gòu)2）來實 現(xiàn)循環(huán)控制過程。 a p 不成立 成立 A b 循環(huán)結(jié)構(gòu)1 當(dāng)？成立 A N-S盒圖表示 跟while語句不同采用repea t語句來實現(xiàn)循環(huán)控制

29、 過程，其偽碼原語的使用規(guī)定如下： repeat （活動）until （條件） 其中repeat、until都是保留詞。repeat語句的含義如 圖所示，跟while語句不同之處是先執(zhí)行循環(huán)體，然后 進行條件檢查。 活動 條件 N Y repea t語句流程圖 開始 輸入正整數(shù)m和n r^m被n除的余數(shù) r不等于0? N Y m — n; n — r r^m被n除的余數(shù) 輸出n的值 結(jié)束 求最大公約數(shù)流程圖 輸入正整數(shù)m和n r—m被n除的余數(shù) 當(dāng)r不等于0 m — n; n — r r—m被n除的余數(shù) 輸出n的值 N-S盒圖表示 為了更好地理解

30、這種迭代結(jié)構(gòu)，我們再以上述數(shù)據(jù) 查找算法為例，來詳細分析迭代結(jié)構(gòu)算法的特點。在上 述算法中，為了解決姓名查找問題，我們是從名單首列 開始依次逐一將待查姓名與名單中出現(xiàn)的姓名進行比 較，找到了就查找成功；如果名單結(jié)束也沒有找到，則 查找失敗?，F(xiàn)在，如果名單是按照字母順序排列的，那 么只須按照字母順序查找即可，不必比較所有的表項。 這樣，實現(xiàn)這一過程的偽碼可以表示如下頁所示。 Procedure Search （list， TargetValue） if （list為空）then （返回失?。? else（ TestEntry—在lis t中選擇第一個表項； while （TargetVa

31、lue>TestEntry 且 TestEntry不是最后一個表項） do （TestEntry—在list中選擇下一個表項）； if （TargetValue=TestEntry） then （返回成功） else （返回失?。? ）end if 上述算法是按照字母排列順序來查找的，因此稱其 為順序查找（sequential search）算法，簡單分析可 知，計算代價主要體現(xiàn)在while語句，如果表的長度為 n的話，那么平均需要計算n/2計算步，因此算法的計算 復(fù)雜性為O （n）。實際上，該算法中while語句就是 一個迭代結(jié)構(gòu)，而其中的指令“TestEntry—在list中選

32、 擇下一個表項〃是以重復(fù)的方式被執(zhí)行的。 一般，循環(huán)控制由狀態(tài)初始化、條件檢查和狀態(tài)修 改三個環(huán)節(jié)部分組成，其中每個環(huán)節(jié)都決定著循環(huán)的成 功與否。其中狀態(tài)初始化設(shè)置一個初始狀態(tài)，并且這一 狀態(tài)是可以被修改的，直到滿足終止條件；條件檢查是 將當(dāng)前狀態(tài)與終止條件比較，如果符合就終止循環(huán)；狀 態(tài)修改就是對當(dāng)前狀態(tài)進行有規(guī)律地改變，使其朝著終 止條件發(fā)展。 最后就是遞歸結(jié)構(gòu)。比循環(huán)結(jié)構(gòu)還要復(fù)雜的算法結(jié) 構(gòu)是遞歸結(jié)構(gòu)，也可以實現(xiàn)重復(fù)計算任務(wù)。如果說循環(huán) 是通過重復(fù)執(zhí)行同樣一組指令的方式來進行的，那么遞 歸則是通過將一組指令當(dāng)作自身的一個子程序進行調(diào) 用來進行的。 開始指示代詞量詞形容詞名詞結(jié)束

33、“花哨名詞”遞歸遷移網(wǎng)（RTN） 為了直觀起見，我們下面通過一個名叫折半查找 （binary search）算法來說明算法中的遞歸結(jié)構(gòu)。對 于同樣的名字查找問題，除了順序依次比較方法外，為 了提高查找的效率，也可以采取折半查找方法來查找。 通過問題的分析，具體構(gòu)造的算法如下頁所示。注意， 算法中引入了新的語句Switch case語句，即分情況 語句，屬于條件語句的一種變形形式，其中Switch、 case均為保留詞。 procedure Search(List， TargetValue) if(list) then (返回失敗) else( TestEntry—選擇List的“中

34、間”值； Switch(TargetValue)( case(TargetValue=TestEntry)(返 回成功) case(TargetValue>TestEntry)( BList—位于 TestEntry 前半部分 List； 返回？ rocedure Search(BList， TargetValue)的返回值) case(TargetValue

35、身調(diào)用的情況，這便是 遞歸結(jié)構(gòu)。遞歸過程的控制主要是通過過程調(diào)用參數(shù)的 變化來進行的。在上述算法中這樣的參數(shù)就是列表本身。 如果追蹤某個遞歸過程，那么就會發(fā)現(xiàn)，其計算過程是 一層一層遞進的，然后再一層一層返回。對于遞歸結(jié)構(gòu) 而言，在動態(tài)執(zhí)行過程中，遞進的最大層數(shù)就稱為該遞 歸結(jié)果的遞歸深度。對上述折半算法分析可知，遞歸算 法的計算復(fù)雜性與遞歸深度密切關(guān)聯(lián)，如果表的長度為 n的話，那么平均需要計算的遞歸深度為log2n，因此算 法的計算復(fù)雜性為O (log2n)。顯然，折半查找算法的 效率要高于順序查找算法的效率。 另一個需要運用遞歸結(jié)構(gòu)來設(shè)計求解算法的就是 著名的漢諾塔問題：將A柱子上的n個

36、圓盤借助于B柱子 移到C柱子上去，問如何移動圓盤？約束規(guī)則是(1)每 次只能移動一張圓盤；(2)圓盤只能在這三個柱上存 放；(3)大盤不能壓在小盤上面。 A(源) B(輔助) 。(目的) 漢諾塔問題示意圖 (0) (1) ABC ABC 初始狀態(tài)借 助C，將A上方的三個盤移 到B 精品文檔 (2) (3) ABC ABC 將A上的最后一個盤直接移到C借助A，將B上的三個盤 移到C 漢諾塔問題遞歸解法思路(設(shè)n=4) 根據(jù)上面的分析，對于任意n，求解的方法是：將入 柱子上的n個圓盤分成兩部分：1個園盤和n-1個園盤， 然后按照如下移動園盤步驟： 第一步：將A柱子的上面n

37、-1個園盤移動到B柱子上面； 第二步：將A柱子上剩下的那個園盤移動到C柱子上面; 第三步：將B柱子上的n-1個園盤移動到C柱子上面。 第一步：將A柱子的上面n-1個園盤移動到B柱子上面 n-1 1 A(源) B(輔助) C(目的) 漢諾塔問題示意圖 n-1 1 A(源) B(輔助) C(目的) n-1 1 AB C 第二步：將A柱子上的1個園盤移動到C柱子上 n-1 1 ABC n-1 1 ABC 第三步：將B柱子上的n-1個園盤移動到C柱子上 n-1 1 ABC n-1 1 ABC 這樣，剩下的問題就是n-1個盤子的漢諾塔問題， 可以通過遞歸來求

38、解，直道n=1為止。因此，整個遞歸 算法如下： procedure hanoi(int n, char A ,char B,char C) if(n=1) then printf("%c-->%c\n", A, C); //輸出 else ( 精品文檔 hanoi(n-1,A,C,B); //左向遞歸 printf("%c-->%c\n", A, C); //輸出 hanoi(n-1, B, A, C); //右向遞歸 ) 其中“左向遞歸”是借助C,將A柱上方的n-1個盤 子移到B柱；“右向遞歸”則是借助入，將B柱上n-1個盤 子移到C柱。 1,A,B,C A C Hano

39、i(3,A,B,C) 左向遞歸 輸 出 右向遞歸 2,A,C,B A C 2,B,A,C ④ A B 1,C,A,B 1,B,C,A B C ② ⑥ CB BA 1,A,B,C AC ① ③ ⑤ ⑦  本講介紹了智能計算中最為核心，也是最為基礎(chǔ)的 內(nèi)容，即算法設(shè)計。人類的智能是否都可以用算法來表 示，這是一個開放問題，我們不得而知。但是起碼目前 來說，算法是實現(xiàn)機器智能的唯一手段，也是最為重要 的手段。因此，我們必須對這里介紹的有關(guān)算法的概念、 結(jié)構(gòu)、效率、以及構(gòu)造原語、偽碼及原則有基本的了解， 并掌握其中的核心內(nèi)容與思想，為智能系統(tǒng)的構(gòu)建，奠 定基礎(chǔ)。 練習(xí)題

40、 1、 對于給定的一個由0—9十個數(shù)字組成的數(shù)列，請設(shè) 計一個算法，能夠?qū)υ摂?shù)列作重排，使得結(jié)果數(shù)列剛好 比給定的數(shù)列大。 2、 如何構(gòu)造一個能夠計算一個字符串在另一個字符串 中出現(xiàn)次數(shù)的算法，請用偽碼來表示所給出的算法，并 分析算法的計算復(fù)雜性。 3、 設(shè)有兩個正整數(shù)口和n，如何求其最大公約數(shù)？請使 用遞歸結(jié)構(gòu)，設(shè)計一個能夠解決該問題的算法。 算法的運行圖解（設(shè)n=3） 對于遞歸算法，保證遞歸過程終止的條件也是需要 考慮的問題。比如上述折半查找算法中表列為空或者找 到目標(biāo)，可以保證遞歸過程的終止。而在漢諾塔問題中， 盤子數(shù)降到1，算法也會終止。與循環(huán)終止條件的顯式 表示不同，

41、遞歸終止條件往往是隱含表示的，因此在設(shè) 計遞歸算法時需要格外注意。因為，有時不恰當(dāng)?shù)倪f歸 也會產(chǎn)生悖論，使計算無法終止。 最后，我們強調(diào)指出，從理論上講，所有算法的結(jié) 構(gòu)，都可以看作是并化解為遞歸結(jié)構(gòu)，關(guān)鍵在于遞歸的 深度。其中作為計算理論的之一遞歸函數(shù)論，就是以遞 歸的思想，建立起完整的計算理論模型的。這就是為什 么，我們在算法構(gòu)造的原語介紹中，一開始就將各種算 法步驟的描述方式為遞歸語義結(jié)構(gòu)的原因所在。 在算法中，遞歸的思想非常重要，如果說對于計算 學(xué)科而言，玩的就是算法，那么對于算法而言，玩的就 是遞歸。從更為廣泛的視野講，遞歸也是大自然的一種 普遍現(xiàn)象，從自然界的分形，到語言、音樂、繪畫中的 嵌套結(jié)構(gòu)，無不體現(xiàn)著遞歸的本性。正是從這個意義上 講，通過遞歸，算法的方法可以被應(yīng)用到自然與人文的 各個方面，特別是可以應(yīng)用到解決我們的智能機智仿造 之中。 第03講小結(jié)