算法描述與設計完整版

算法描述(miáoshù)與設計第一頁，共十六頁。農(nóng)夫(nóngfū)問題：有一個牧羊人帶著一頭羊,一只狼和一顆大白菜準備過河,他找到一只很小的船,每次只能帶一樣東西(dōngxī)過去,可是如果讓狼與羊單獨在一起,狼會吃羊,讓羊與白菜單獨在一起,羊會吃白菜，牧羊人應如何過河？要求：現(xiàn)在請同學們來設計一個方案,把3樣東西(dōngxī)安然無恙的帶過河。第二頁，共十六頁。思考(sīkǎo)：★這個方案總共有多少步？★哪幾步順序可以顛倒？★同學們農(nóng)夫過河問題解決了，那到底什么(shénme)是算法？第三頁，共十六頁。過河方案(fāngàn)：第一步：將羊運過去第二步：人返回(fǎnhuí)第三步：將菜運過去第四步：將羊運過來第五步：將狼運過去第六步：人返回第七步：將羊運過來第四頁，共十六頁。算法(suànfǎ)：概念：算法就是解決問題的方法和步驟

算法是程序設計的“靈魂”，世界著名計算機科學家尼克勞斯·沃思指出：算法+數(shù)據(jù)結構(DataStructure)=程序，可見，算法在程序設中具有多么(duōme)重要的地位。算法獨立于任何具體的程序設計語言，一個算法可以用多種程序設計語言來實現(xiàn)。

那算法都有哪些特征(tèzhēng)呢？也就是問題的解決都有哪些特點，我們應該注意些什么呢？第五頁，共十六頁。算法(suànfǎ)特征：有窮性：執(zhí)行有限步，每一步執(zhí)行時間有限；確定性：每一步都有確切的含義；輸入：有零個或多個輸入；輸出：至少產(chǎn)生一個(yīɡè)輸出；可行性：原則上能精確運行，用紙和筆做有限次運算后即可完成。第六頁，共十六頁。如何(rúhé)描述算法：算法可以用多種方法(fāngfǎ)來描述1、用自然語言來描述(miáoshù)。2、用流程圖來描述。3、用偽代碼描述算法。第七頁，共十六頁。課堂(kètáng)實踐：韓信點兵問題：

如果每3個人(gèrén)編為一隊，那最后剩下2個人；如果每5個人編為一隊，那最后剩下3個人；如果每7個人編為一隊，最后剩下2個人。請你自己算一下，我有多少士兵？”第八頁，共十六頁。自然語言描述(miáoshù)：第九頁，共十六頁。流程圖描述(miáoshù)：開始N=1N被3、5、7整除后余數(shù)為2、3、2輸出N的值N=N+1結束YN第十頁，共十六頁。任意給定3個正實數(shù)，判斷以這3個正實數(shù)能否(nénɡfǒu)構成三角形。請用流程圖描述(miáoshù)下題中的算法：開始輸入a，b，ca+b>c,b+c>ac+a>b是否同時成立？結束能構成三角形不能構成三角形否是第十一頁，共十六頁。自然語言描述(miáoshù)與流程圖描述(miáoshù)的比較自然語言描述流程圖描述直觀清晰確定性繁瑣程度是否容易修改通俗易懂第十二頁，共十六頁。初始化N=1DOIfN整除(zhěngchú)3余2、整除5余3、整除7余2then

輸出N的值ExitDOEndIfN=N+1Loop偽代碼(dàimǎ)描述：第十三頁，共十六頁。偽代碼(dàimǎ)：優(yōu)點：簡潔、易懂、修改容易，且容易轉化(zhuǎnhuà)為程序語言代碼。缺點：不直觀、一旦出現(xiàn)邏輯錯誤不容易排查。

偽代碼是介于自然語言和計算機程序語言之間的一種算法描述。

它是專業(yè)軟件開發(fā)人員描述算法的一種常用方法。沒有(méiyǒu)嚴格的語法限制，書寫格式較自由，一般關鍵詞用英文單詞。第十四頁，共十六頁。小結(xiǎojié)：特征：有輸入(shūrù)確定性有窮性有輸出可行性算法的描述用自然語言描述算法用流程圖描述算法用偽代碼描述算法算法(suànfǎ)——解決問題的方法和步驟

一個問題，可能有多種算法，應該通過分析、比較、挑選一種最優(yōu)的算法。一個好算法必須用到科學的方法，應該好好學習各學科處理問題的科學方法。第十五頁，共十六頁。內容(nèiróng)總結算法描述與設計。算法獨立于任何具體的程序設計語言，一個算法可以用多種程序設計語言來實現(xiàn)。有窮性：執(zhí)行有限步，每一步(yībù)執(zhí)行時間有限。輸入：有零個或多個輸入。輸出：至少產(chǎn)生一個輸出。如果每3個人編為一隊，那最后剩下2個人。如