算法的描述與設(shè)計(jì)

算法的描述與設(shè)計(jì)現(xiàn)在是1頁\一共有19頁\編輯于星期日學(xué)習(xí)目標(biāo)：1、理解什么是算法，知道算法的多樣性；2、學(xué)會(huì)用自然語言、流程圖和偽代碼來描述算法；3、能夠?qū)υO(shè)計(jì)的算法做出簡(jiǎn)單的評(píng)價(jià)?，F(xiàn)在是2頁\一共有19頁\編輯于星期日

算法的描述與設(shè)計(jì)

有一個(gè)牧羊人帶著一頭羊,一只狼和一顆大白菜準(zhǔn)備過河,他找到一只很小的船,每次只能帶一樣?xùn)|西過去,可是如果讓狼與羊單獨(dú)在一起,狼會(huì)吃羊,讓羊與白菜單獨(dú)在一起,羊會(huì)吃白菜，牧羊人應(yīng)如何過河？

要求：現(xiàn)在請(qǐng)同學(xué)們來設(shè)計(jì)一個(gè)方案,把3樣?xùn)|西安然無恙的帶過河。農(nóng)夫問題現(xiàn)在是3頁\一共有19頁\編輯于星期日

思考：123這個(gè)方案總共有多少步？

哪幾步順序可以顛倒？同學(xué)們農(nóng)夫過河問題解決了，那到底什么是算法？現(xiàn)在是4頁\一共有19頁\編輯于星期日

過河方案牧

羊

人

過

河

方

案第一步：將羊運(yùn)過去第二步：人返回第三步：將菜運(yùn)過去第四步：將羊運(yùn)過來第五步：將狼運(yùn)過去第六步：人返回第七步：將羊運(yùn)過來現(xiàn)在是5頁\一共有19頁\編輯于星期日算法就是解決問題的方法和步驟。

算法是程序設(shè)計(jì)的“靈魂”，世界著名計(jì)算機(jī)科學(xué)家尼克勞斯·沃思（N·wirth）指出：算法+數(shù)據(jù)結(jié)構(gòu)(DataStructure)=程序，可見，算法在程序設(shè)中具有多么重要的地位。算法獨(dú)立于任何具體的程序設(shè)計(jì)語言，一個(gè)算法可以用多種程序設(shè)計(jì)語言來實(shí)現(xiàn)。

算法的概念

算法

那算法都有哪些特征呢？也就是問題的解決都有哪些特點(diǎn)，我們應(yīng)該注意些什么呢？現(xiàn)在是6頁\一共有19頁\編輯于星期日算法的特征有窮性：執(zhí)行有限步，每一步執(zhí)行時(shí)間有限;確定性：每一步都有確切的含義;輸入：有零個(gè)或多個(gè)輸入;輸出：至少產(chǎn)生一個(gè)輸出;可行性：原則上能精確運(yùn)行，用紙和筆做有限次運(yùn)算后即可完成?，F(xiàn)在是7頁\一共有19頁\編輯于星期日如何描述算法算法可以用多種方法來描述1、用自然語言來描述。2、用流程圖來描述。3、用偽代碼描述算法?，F(xiàn)在是8頁\一共有19頁\編輯于星期日

實(shí)踐活動(dòng)：韓信點(diǎn)兵問題:“今有物不知其數(shù)，三三數(shù)之余二，五五數(shù)之余三，七七數(shù)之余二，問物幾何？”現(xiàn)在是9頁\一共有19頁\編輯于星期日

實(shí)踐活動(dòng)：自

然

語

言用自然語言描述“韓信點(diǎn)兵問題”

:現(xiàn)在是10頁\一共有19頁\編輯于星期日

自然語言

用自然語言表達(dá)算法，就是把算法的各個(gè)步驟，依次用人們熟悉的自然語言表示出來。優(yōu)點(diǎn)：容易理解。缺點(diǎn)：書寫較煩、不確定性、對(duì)復(fù)雜的問題難以表達(dá)準(zhǔn)確、不能被計(jì)算機(jī)識(shí)別和執(zhí)行。自然語言描述現(xiàn)在是11頁\一共有19頁\編輯于星期日流程圖流程圖現(xiàn)在是12頁\一共有19頁\編輯于星期日

流程圖

也稱為程序框圖，它是算法的一種圖形化表示方法。流程圖描述現(xiàn)在是13頁\一共有19頁\編輯于星期日

描述“韓信點(diǎn)兵”算法的兩種方法流程圖

S1：將N初始值賦值為1；

S2：若N被3、5、7整除后的余數(shù)分別為2、3、2，則輸出N的值，轉(zhuǎn)S4；

S3：將N的值加1，轉(zhuǎn)S2；

S4：結(jié)束程序。自然語言現(xiàn)在是14頁\一共有19頁\編輯于星期日

偽代碼偽代碼描述初始化N=1DOIfN整除3余2、整除5余3、整除7余2then

輸出N的值ExitDOEndIfN=N+1Loop現(xiàn)在是15頁\一共有19頁\編輯于星期日偽代碼描述Ifa除以2余數(shù)為0then

輸出“a為偶數(shù)”判斷某個(gè)數(shù)是否偶數(shù)Else x=-b/aEndif

求解ax+b=0Else

輸出“a不是偶數(shù)”Endif輸入正數(shù)a輸入a,bIfa=0thenifb=0then

輸出x為任意值else

輸出x無實(shí)數(shù)解

endif現(xiàn)在是16頁\一共有19頁\編輯于星期日

偽代碼

偽代碼是介于自然語言和計(jì)算機(jī)程序語言之間的一種算法描述。優(yōu)點(diǎn)：簡(jiǎn)潔、易懂、修改容易。缺點(diǎn)：不直觀、一旦出現(xiàn)邏輯錯(cuò)誤不容易排查。偽代碼描述現(xiàn)在是17頁\一共有19頁\編輯于星期日小結(jié)特征：有輸入確定性有窮性有輸出可行性算法的描述用自然語言描述算法用流程圖描述算法用偽代碼描述算法算法——解決問題的方法和步驟

一個(gè)問題，可能有多種算法，應(yīng)該通過分析、比較、挑選一種最優(yōu)的算法。一個(gè)好