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

1、LOGO算法的描述與設(shè)計高級中學(xué)趙曉樂高級中學(xué)趙曉樂 算法的描述與設(shè)計有一個牧羊人帶著一頭羊,一只狼和一顆大白菜準備過河,他找到一只很小的船,每次只能帶一樣?xùn)|西過去,可是如果讓狼與羊單獨在一起,狼會吃羊,讓羊與白菜單獨在一起,羊會吃白菜，牧羊人應(yīng)如何過河？要求：現(xiàn)在請同學(xué)們來設(shè)計一個方案,把3樣?xùn)|西安然無恙的帶過河。農(nóng)夫問題1234這個方案總共有多少步？這個方案總共有多少步？ 哪幾步順序可以顛倒？哪幾步順序可以顛倒？同學(xué)們農(nóng)夫過河問題解決了，那到底什么是算法？同學(xué)們農(nóng)夫過河問題解決了，那到底什么是算法？ 【農(nóng)夫問題】中，我們是用什么來描述算法的？【農(nóng)夫問題】中，我們是用什么來描述算法的？ 5算

2、法還有其他的描述方法嗎？算法還有其他的描述方法嗎？ 過河方案牧羊人過河方案第一步：將羊運過去第二步：人返回第三步：將菜運過去第四步：將羊運過來第五步：將狼運過去第六步：人返回第七步：將羊運過來算法就是解決問題的方法和步驟方法和步驟 一個能被解決的問題，其中都包含著算法一個能被解決的問題，其中都包含著算法 算法是程序設(shè)計的算法是程序設(shè)計的“靈魂靈魂”，世界著名計算機科學(xué)家尼克勞斯，世界著名計算機科學(xué)家尼克勞斯沃思（沃思（N Nwirthwirth）指出：算法）指出：算法+ +數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structure)=(Data Structure)=程序，可見，算法在程序設(shè)程序，可見，算

3、法在程序設(shè)中具有多么重要的地位。算法獨立于任何具體的程序設(shè)計語言，一個算法可中具有多么重要的地位。算法獨立于任何具體的程序設(shè)計語言，一個算法可以用多種程序設(shè)計語言來實現(xiàn)。例如，以用多種程序設(shè)計語言來實現(xiàn)。例如，“雞兔同籠問題雞兔同籠問題”的算法可以用的算法可以用BASICBASIC語言來實現(xiàn)，也可以用語言來實現(xiàn)，也可以用C C語言來實現(xiàn)。語言來實現(xiàn)。 算法的概念算法的概念 算法 那算法都有哪些那算法都有哪些特征特征呢？也就是問題的解決都有哪些特點，我們應(yīng)該注意呢？也就是問題的解決都有哪些特點，我們應(yīng)該注意些什么呢？些什么呢？算法的特征 有窮性有窮性：執(zhí)行有限步，每一部執(zhí)行時間有限 確定性確定性

4、：每一步都有確切的含義 輸入輸入：有零個或多個輸入 輸出輸出：至少產(chǎn)生一個輸出 可行性可行性：原則上能精確運行，用紙和筆做有限次運算后即可完成 自然語言 用自然語言表達算法，就是把算法的各個步驟，依次用人們熟悉的自然語言表示出來。優(yōu)點：容易理解缺點：書寫較煩、不確定性、對復(fù)雜的問題難以表達準確、不能被計算機識別和執(zhí)行自然語言描述自然語言描述 實踐活動二 S1：輸入a，b的值，確定方程； S2：若a=0，b0，方程無解，結(jié)束； S3：若a=0，b=0，x為任意值，結(jié)束； S4：若a不等于0，移項得 ax=-b則x=- b/a，結(jié)束。自然語言用自然語言描述求解ax+b=0的過程（注意討論a，b的情

5、況） 算法的描述方法算法的描述用自然語言描述算法用流程圖描述算法用偽代碼描述算法 用?描述解方程ax+b=0流程圖算法的開始或結(jié)束算法的開始或結(jié)束輸入或輸出信息輸入或輸出信息條件判斷條件判斷程序框名稱功能開始/結(jié)束算法的開始或結(jié)束輸入/輸出輸入或輸出信息處理計算與賦值判斷條件判斷流程線算法中的流向連接圈表示算法流向出口或入口連接點常用的“流程圖”所用的基本符號 流程圖 也稱為程序框圖，它是算法的一種圖形化表示方法。優(yōu)點：形象、直觀、容易理解流程圖描述流程圖描述 描述解方程ax+b=0算法的兩種方法流程圖 S1：輸入a，b的值，確定方程； S2：若a=0，b0，方程無解，結(jié)束； S3：若a=0，

6、b=0，x為任意值，結(jié)束； S4：若a不等于0，移項得 ax=-b則x=- b/a，結(jié)束。自然語言自然語言描述與流程圖描述的比較自然語言描述流程圖描述直觀清晰確定性繁瑣程度是否容易修改通俗易懂 偽代碼偽代碼表示舉例偽代碼表示舉例（1）表示條件判斷 （2）表示循環(huán)處理 if 條件 then do while 條件 執(zhí)行語句一 循環(huán)處理語句 else loop 執(zhí)行語句二 end if偽代碼描述If a除以2余數(shù)為0 then 輸出“a為偶數(shù)”判斷某個數(shù)是否偶數(shù)ElseElsex= -b/ax= -b/aEnd ifEnd if求解ax+b=0Else 輸出“a不是偶數(shù)”End if輸入正數(shù)a輸入

7、輸入 a , ba , bIf a = 0 thenIf a = 0 thenif b = 0 thenif b = 0 then 輸出輸出x x為任意值為任意值 elseelse 輸出輸出x x無實數(shù)解無實數(shù)解 end ifend if 偽代碼 偽代碼是介于自然語言和計算機程序語言之間的一種算法描述。優(yōu)點：簡潔、易懂、修改容易缺點：不直觀、一旦出現(xiàn)邏輯錯誤不容易排查偽代碼描述偽代碼描述描述求解ax+b=0的三種方法輸入輸入 a , ba , bIf a = 0 thenIf a = 0 then if b = 0 then if b = 0 then 輸出輸出x x為任意值為任意值 else

8、else 輸出輸出x x無實數(shù)解無實數(shù)解 end ifend ifElseElse x= -b/a x= -b/aEnd ifEnd if偽代碼描述 S1 S1：輸入：輸入a a，b b的值，的值，確定方程；確定方程； S2S2：若：若a=0a=0，b0b0，方，方程無解，結(jié)束；程無解，結(jié)束； S3S3：若：若a=0a=0，b=0b=0，x x為為任意值，結(jié)束；任意值，結(jié)束； S4S4：若：若a a不等于不等于0 0，移，移項得項得 ax=-bax=-b則則x=- x=- b/ab/a，結(jié)束。，結(jié)束。自然語言描述流程圖描述根據(jù)具體的情況選擇不同的方法小結(jié)特征：特征：有輸入 確定性 有窮性 有輸出 可行性 算法的描述算法的描述用自然語言描述算法用流程圖描述算法用偽代碼描述算法算法算法解決問題的方法和步驟 一個問題，可能