算法和算法的描述

1、高二年級(jí)信息技術(shù)學(xué)科（選修1）廣東教育出版社東平明湖中學(xué) 董愛(ài)平 第一章第二節(jié) 課題：算法和算法的描述東平明湖中學(xué)東平明湖中學(xué)東平明湖中學(xué)東平明湖中學(xué)課下自主預(yù)習(xí)（學(xué)案）課下自主預(yù)習(xí)（學(xué)案）東平明湖中學(xué)東平明湖中學(xué) 激發(fā)學(xué)習(xí)熱情，培養(yǎng)合作意識(shí)和進(jìn)取精神，初步形成嚴(yán)謹(jǐn)?shù)倪壿嬎季S習(xí)慣。 理解算法的概念及特征；用自然語(yǔ)言、流程圖等方法描述算法的過(guò)程； 通過(guò)問(wèn)題分析，選擇適當(dāng)?shù)乃惴枋龉ぞ哌M(jìn)行算法探究活動(dòng)。知識(shí)與技能情感態(tài)度與價(jià)值觀過(guò)程與方法一一東平明湖中學(xué)東平明湖中學(xué)教學(xué)重點(diǎn)教學(xué)重點(diǎn) 算法的特征以及經(jīng)歷用自然語(yǔ)言、流程圖等方法描述算法的過(guò)程。教學(xué)重點(diǎn)教學(xué)重點(diǎn) 教學(xué)重點(diǎn)教學(xué)重點(diǎn)教學(xué)難點(diǎn)教學(xué)難點(diǎn) 算法的

2、特征以及流程圖描述算法。 教學(xué)難點(diǎn)教學(xué)難點(diǎn)二二二二東平明湖中學(xué)東平明湖中學(xué)狼羊菜過(guò)河游戲有一個(gè)牧羊人帶著一頭羊,一只狼和一顆大白菜準(zhǔn)備過(guò)河,他找到一只很小的船,每次只能帶一樣?xùn)|西過(guò)去,可是如果讓狼與羊單獨(dú)在一起,狼會(huì)吃羊,讓羊與白菜單獨(dú)在一起,羊會(huì)吃白菜，牧羊人應(yīng)如何過(guò)河？要求：請(qǐng)?jiān)O(shè)計(jì)一個(gè)方案,把3樣?xùn)|西安然無(wú)恙的帶過(guò)河。東平明湖中學(xué)東平明湖中學(xué)1這個(gè)方案總共有多少步？這個(gè)方案總共有多少步？2農(nóng)夫過(guò)河問(wèn)題解決了，那到底什么是算法？農(nóng)夫過(guò)河問(wèn)題解決了，那到底什么是算法？ 合作探究一：合作探究一：總結(jié)算法的定義總結(jié)算法的定義東平明湖中學(xué)東平明湖中學(xué) 過(guò)河方案過(guò)河方案第一步：將羊運(yùn)過(guò)去第二步：人返回

3、第三步：將菜運(yùn)過(guò)去第四步：將羊運(yùn)過(guò)來(lái)第五步：將狼運(yùn)過(guò)去第六步：人返回第七步：將羊運(yùn)過(guò)來(lái)東平明湖中學(xué)東平明湖中學(xué) 算法是在有限步驟內(nèi)有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義定義明確明確的規(guī)則。通俗地說(shuō)，算法就是求解某一問(wèn)題的方法，是能被機(jī)械地執(zhí)行的動(dòng)作或指令的集合。算法就是解決問(wèn)題的方法和步驟方法和步驟有窮性有窮性 確定性確定性東平明湖中學(xué)東平明湖中學(xué)歷史上的經(jīng)典算法！輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法設(shè)給定的兩個(gè)正整數(shù)設(shè)給定的兩個(gè)正整數(shù)m=112,n=64，求它們的，求它們的最大公約數(shù)和最小公倍最大公約數(shù)和最小公倍數(shù)是多少？數(shù)是多少？數(shù)數(shù) 學(xué)學(xué) 問(wèn)問(wèn) 題題東平明湖中學(xué)東平明湖中學(xué) 最小公倍數(shù)：兩個(gè)正整數(shù)的乘積

4、除以最大公約數(shù) 設(shè)給定的兩個(gè)正整數(shù)為m和n，求它們的最大公約數(shù)的步驟為：（1）以m除以n，令所得的余數(shù)為r。（2）若r=0，則輸出結(jié)果n，算法結(jié)束；否則，繼續(xù)步驟（3）。（3）令m=n，n=r，并返回步驟（1）繼續(xù)進(jìn)行。歐幾里得輾轉(zhuǎn)相除法東平明湖中學(xué)東平明湖中學(xué) 利用輾轉(zhuǎn)相除法求最大公約數(shù)和最利用輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)小公倍數(shù)P9(P9(實(shí)踐一和實(shí)踐二實(shí)踐一和實(shí)踐二) )試試 一一 試試總結(jié)算法的特征總結(jié)算法的特征東平明湖中學(xué)東平明湖中學(xué)（1）輸輸 入。入。一個(gè)算法有零零個(gè)(算法本身給了一個(gè)初始值)或多多個(gè)輸入。（2）確定性確定性。算法的每一個(gè)步驟必須要確切地定義確切地定義。（3）

5、有窮性有窮性。一個(gè)算法的計(jì)算步驟是有限有限的。（4）輸輸 出出。算法有一一個(gè)或多多個(gè)輸出。 學(xué)業(yè)水平考試學(xué)業(yè)水平考試考點(diǎn)（5）能行性能行性。計(jì)算機(jī)解決問(wèn)題能不能精確地進(jìn)行。東平明湖中學(xué)東平明湖中學(xué)1、這個(gè)人好說(shuō)話。課課 堂堂 檢檢 測(cè)：測(cè)：2、S1: sum=0 S2: I=1 S3: sum=sum+I S4: I=I+1 S5: 若sum=0 ，返回s3;否則，算法結(jié)束。違反了算法的（ ）特征東平明湖中學(xué)東平明湖中學(xué) 3、算法要有一個(gè)清晰的起始步清晰的起始步，表示處理問(wèn)題的起點(diǎn)，且每一個(gè)步驟只能有一個(gè)確定的只能有一個(gè)確定的后繼步驟( )，從而組成一個(gè)步驟的有限有限序列( )；要有一個(gè)終止步

6、一個(gè)終止步(序列的終止)表示問(wèn)題得到解決或不能得到解決；每條規(guī)則必須是確定的、可行的(3 )、不能存在二義性。算法總是對(duì)數(shù)據(jù)進(jìn)行加工處理，因此，算法的執(zhí)行過(guò)程中通常要有數(shù)據(jù)4 4輸入輸入( )和數(shù)據(jù)5 5輸出輸出（ ）的步驟。 算法的算法的確定性確定性算法的有算法的有窮性性窮性性算法的可算法的可行性行性0個(gè)或多個(gè)或多個(gè)個(gè)至少一個(gè)至少一個(gè)東平明湖中學(xué)東平明湖中學(xué)1在在【輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法】中，我們是用什么來(lái)描述算法的？中，我們是用什么來(lái)描述算法的？ 2算法還有其他的描述方法嗎？算法還有其他的描述方法嗎？ 東平明湖中學(xué)東平明湖中學(xué)自自 然然 語(yǔ)語(yǔ) 言、流程圖言、流程圖1、用自然語(yǔ)言描述算法，就是

7、把算法的各個(gè)步驟，、用自然語(yǔ)言描述算法，就是把算法的各個(gè)步驟，依次用人們熟悉的自然語(yǔ)言表示出來(lái)。依次用人們熟悉的自然語(yǔ)言表示出來(lái)。 2、也稱為程序框圖，它是算法的一種圖形化表示方法。東平明湖中學(xué)東平明湖中學(xué) 3、偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)程序語(yǔ)言之間、偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)程序語(yǔ)言之間的文字、符號(hào)來(lái)描述算法的方法。的文字、符號(hào)來(lái)描述算法的方法。偽代碼偽代碼東平明湖中學(xué)東平明湖中學(xué)三種方法描述輾轉(zhuǎn)相除法：三種方法描述輾轉(zhuǎn)相除法：給定兩個(gè)正整數(shù)m和n；以m除以n，令所得的余數(shù)為r；若r=0，則輸出結(jié)果n，算法結(jié)束；否則，繼續(xù)步驟 ；令m=n，n=r，并返回步驟繼續(xù)進(jìn)行。 歐幾里得輾轉(zhuǎn)相除法

8、：INPUT m,nr= m mod nDo While r0 m=n n=r r=m mod nLoopPrint n東平明湖中學(xué)東平明湖中學(xué)交換兩個(gè)杯子中的液體交換兩個(gè)杯子中的液體AB提問(wèn)同學(xué)，如何處理？提問(wèn)同學(xué)，如何處理？將杯子將杯子A中的液體倒給杯子中的液體倒給杯子C；將杯子將杯子B中的液體倒給杯子中的液體倒給杯子A；將杯子將杯子C中的液體倒給杯子中的液體倒給杯子B。C引入一個(gè)空杯子引入一個(gè)空杯子?xùn)|平明湖中學(xué)東平明湖中學(xué)開(kāi)開(kāi)始始A-CB-AC-B輸出輸出A,B結(jié)結(jié)束束交換兩個(gè)杯子中的液體交換兩個(gè)杯子中的液體東平明湖中學(xué)東平明湖中學(xué)三種描述方法的優(yōu)點(diǎn)與缺三種描述方法的優(yōu)點(diǎn)與缺 點(diǎn)點(diǎn)自然語(yǔ)

9、言描述 流程圖描述直觀清晰確定性繁瑣程度是否容易修改通俗易懂不不 能能 被被 計(jì)計(jì) 算算 機(jī)機(jī) 識(shí)識(shí) 別別東平明湖中學(xué)東平明湖中學(xué)用偽代碼描述算法優(yōu)點(diǎn)：書寫方便，格式緊湊，易于理解，便于向計(jì)算機(jī) 程序設(shè)計(jì)語(yǔ)言過(guò)度。缺點(diǎn)：由于語(yǔ)言的種類繁多，偽代碼的語(yǔ)句不容易規(guī)范。優(yōu)優(yōu) 點(diǎn)點(diǎn) 與與 缺缺 點(diǎn)點(diǎn)東平明湖中學(xué)東平明湖中學(xué)（環(huán)節(jié)三）鞏固練習(xí)（環(huán)節(jié)三）鞏固練習(xí)1、關(guān)于算法的描述，下列選項(xiàng)中正確的是（ ） A、一個(gè)算法的執(zhí)行步驟可以是無(wú)限的 B、一個(gè)算法可以沒(méi)有輸入 C、一個(gè)算法，當(dāng)沒(méi)有輸入時(shí)，也沒(méi)有輸出 D、算法只能用流程圖來(lái)表示B學(xué)業(yè)水平考試題學(xué)業(yè)水平考試題東平明湖中學(xué)東平明湖中學(xué)2、下列關(guān)于算法的描

10、述錯(cuò)誤是（ ）。A、一個(gè)有效的算法至少要有一個(gè)或多個(gè)輸入B、算法是解決某一類問(wèn)題的方法和步驟C、算法必須在有限步驟內(nèi)實(shí)現(xiàn)D、算法可以使用自然語(yǔ)言、偽代碼、流程圖等多種不同的方法來(lái)描述學(xué)業(yè)水平考試題學(xué)業(yè)水平考試題A東平明湖中學(xué)東平明湖中學(xué) 如圖所示的算法流程圖，執(zhí)行情況如下：如圖所示的算法流程圖，執(zhí)行情況如下：當(dāng)輸入當(dāng)輸入a,b的值分別為的值分別為3，8時(shí)，輸出結(jié)果為時(shí)，輸出結(jié)果為5當(dāng)輸入當(dāng)輸入a,b的值分別為的值分別為11，7時(shí)，輸出結(jié)果為時(shí)，輸出結(jié)果為43、分析解答問(wèn)題（學(xué)業(yè)水平考試題）、分析解答問(wèn)題（學(xué)業(yè)水平考試題） 問(wèn)題：依據(jù)問(wèn)題所選流程圖，當(dāng)輸入a,b的值分別為9，6時(shí)，輸出結(jié)果為 （ ） 學(xué)業(yè)水平考試題學(xué)業(yè)水平考試題C=abs(a-b)東平明湖中學(xué)東平明湖中學(xué) 1、已知圓半徑，求面積（用流程圖描已知圓半徑，求面積（用流程圖描述算法）述算法）（環(huán)節(jié)四）：課下作業(yè)（環(huán)節(jié)四）：課下作業(yè)2、預(yù)習(xí)第三節(jié)程序與程序、預(yù)習(xí)第三節(jié)程序與程序設(shè)計(jì)語(yǔ)言（學(xué)案）設(shè)計(jì)語(yǔ)言（學(xué)案）東