算法和算法的描述資料.ppt

,高二年級信息技術(shù)學(xué)科（選修1）廣東教育出版社,東平明湖中學(xué)董愛平,第一章第二節(jié)課題：算法和算法的描述,復(fù)習(xí),計算機解決問題的過程,課下自主預(yù)習(xí)（學(xué)案）,激發(fā)學(xué)習(xí)熱情，培養(yǎng)合作意識和進取精神，初步形成嚴(yán)謹(jǐn)?shù)倪壿嬎季S習(xí)慣。,理解算法的概念及特征；用自然語言、流程圖等方法描述算法的過程；,通過問題分析，選擇適當(dāng)?shù)乃惴枋龉ぞ哌M行算法探究活動。,知識與技能,情感態(tài)度與價值觀,過程與方法,二,重點難點,（環(huán)節(jié)一）情境引入,狼羊菜過河游戲,有一個牧羊人帶著一頭羊,一只狼和一顆大白菜準(zhǔn)備過河,他找到一只很小的船,每次只能帶一樣?xùn)|西過去,可是如果讓狼與羊單獨在一起,狼會吃羊,讓羊與白菜單獨在一起,羊會吃白菜，牧羊人應(yīng)如何過河？要求：請設(shè)計一個方案,把3樣?xùn)|西安然無恙的帶過河。,農(nóng)夫過河問題解決了，那到底什么是算法？,合作探究一：,總結(jié)算法的定義,過河方案,算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗地說，算法就是求解某一問題的方法，是能被機械地執(zhí)行的動作或指令的集合。,算法就是解決問題的方法和步驟,（環(huán)節(jié)二）學(xué)習(xí)新知,有窮性確定性,合作探究二：算法的特征,最小公倍數(shù)：兩個正整數(shù)的乘積除以最大公約數(shù),設(shè)給定的兩個正整數(shù)為m和n，求它們的最大公約數(shù)的步驟為：（1）以m除以n，令所得的余數(shù)為r。（2）若r=0，則輸出結(jié)果n，算法結(jié)束；否則，繼續(xù)步驟（3）。（3）令m=n，n=r，并返回步驟（1）繼續(xù)進行。,歐幾里得輾轉(zhuǎn)相除法,利用輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)P9(實踐一和實踐二),試一試,總結(jié)算法的特征,（1）輸入。一個算法有零個(算法本身給了一個初始值)或多個輸入。,（2）確定性。算法的每一個步驟必須要確切地定義。,（3）有窮性。一個算法的計算步驟是有限的。,（4）輸出。算法有一個或多個輸出。,學(xué)業(yè)水平考試考點,（5）能行性。計算機解決問題能不能精確地進行。,1、這個人好說話。,課堂檢測：,2、S1:sum=0S2:I=1S3:sum=sum+IS4:I=I+1S5:若sum=0，返回s3;否則，算法結(jié)束。,違反了算法的（）特征,3、算法要有一個清晰的起始步，表示處理問題的起點，且每一個步驟只能有一個確定的后繼步驟()，從而組成一個步驟的有限序列()；要有一個終止步(序列的終止)表示問題得到解決或不能得到解決；每條規(guī)則必須是確定的、可行的(3)、不能存在二義性。算法總是對數(shù)據(jù)進行加工處理，因此，算法的執(zhí)行過程中通常要有數(shù)據(jù)4輸入()和數(shù)據(jù)5輸出（）的步驟。,算法的確定性,算法的有窮性性,算法的可行性,0個或多個,至少一個,合作探究三：算法的描述,自然語言、流程圖,1、用自然語言描述算法，就是把算法的各個步驟，依次用人們熟悉的自然語言表示出來。,2、也稱為程序框圖，它是算法的一種圖形化表示方法。,3、偽代碼是介于自然語言和計算機程序語言之間的文字、符號來描述算法的方法。,偽代碼,三種方法描述輾轉(zhuǎn)相除法：,給定兩個正整數(shù)m和n；以m除以n，令所得的余數(shù)為r；若r=0，則輸出結(jié)果n，算法結(jié)束；否則，繼續(xù)步驟；令m=n，n=r，并返回步驟繼續(xù)進行。,歐幾里得輾轉(zhuǎn)相除法：,INPUTm,nr=mmodnDoWhiler0m=nn=rr=mmodnLoopPrintn,交換兩個杯子中的液體,A,B,提問同學(xué)，如何處理？將杯子A中的液體倒給杯子C；將杯子B中的液體倒給杯子A；將杯子C中的液體倒給杯子B。,開始,A-C,B-A,C-B,輸出A,B,結(jié)束,交換兩個杯子中的液體,三種描述方法的優(yōu)點與缺點,不能被計算機識別,用偽代碼描述算法,優(yōu)點：書寫方便，格式緊湊，易于理解，便于向計算機程序設(shè)計語言過度。,缺點：由于語言的種類繁多，偽代碼的語句不容易規(guī)范。,優(yōu)點與缺點,（環(huán)節(jié)三）鞏固練習(xí),1、關(guān)于算法的描述，下列選項中正確的是（）A、一個算法的執(zhí)行步驟可以是無限的B、一個算法可以沒有輸入C、一個算法，當(dāng)沒有輸入時，也沒有輸出D、算法只能用流程圖來表示,B,2、下列關(guān)于算法的描述錯誤是（）。A、一個有效的算法至少要有一個或多個輸入B、算法是解決某一類問題的方法和步驟C、算法必須在有限步驟內(nèi)實現(xiàn)D、算法可以使用自然語言、偽代碼、流程圖等多種不同的方法來描述,A,如圖所示的算法流程圖，執(zhí)行情況如下：當(dāng)輸入a,b的值分別為3，8時，輸出結(jié)果為5當(dāng)輸入a,b的值分別為11，7時，輸出結(jié)果為4,3、分析解答問題（學(xué)業(yè)水平考試題）,問題：依據(jù)問題所選流程圖，當(dāng)輸入a,b的值分別為9，6時，輸出結(jié)果為（）,C=abs(a-b),1、已知圓半徑，求面積（用流程圖描述算法）,（環(huán)節(jié)四）：課下作業(yè),2、預(yù)習(xí)第三節(jié)程序與程序設(shè)計語言（學(xué)案）,（環(huán)節(jié)五）課堂小結(jié),輸入確定性有窮性有輸出可行性,概念：,考點,解決問題的方法和步驟,特征：,制作單位：東平明湖中學(xué),時間：2016年4月,人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋?！蓖ㄟ^閱讀科技