算法與程序設計

信息技術（選修1）1.2算法和算法的描述導入新課

我們上節(jié)課通過“韓信點兵”的例子探討了計算機解決問題的步驟，你們還記得計算機解決問題的步驟嗎？計算機解決問題的步驟分析問題設計算法編寫程序調(diào)試程序得出答案具體問題思考有一個牧羊人帶著一頭羊，一只狼和一棵大白菜準備過河，他找到一只很小的船，每次只能帶一樣東西過去，如果狼和羊單獨在一起，狼會吃羊，讓羊和白菜單獨在一起，羊會吃白菜，牧羊人應如何過河？新課導入要求：現(xiàn)在請同學們設計個方案，把3樣東西安然無恙的度過河步驟1：步驟2：步驟3：步驟4：人和羊過河，人返回，留下羊人和狼過河，人和羊返回，留下狼人和菜過河，人返回，留下菜人和羊過河新課導入一、算法1、算法的概念

算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗地說，算法就是求解某一問題的方法，是能被機械地執(zhí)行的動作或指令的集合。一、算法2、算法的特征（1）輸入。一個算法有零個或多個輸入。零個輸入的例子：Privatesubcommand1_click()a=3:b=4Printa*bEndsub（2）確定性。算法的每一個步驟必須要確切地定義。例1：這個人好說話。例2：健美操中一個動作：“手舉過頭頂”。一、算法2、算法的特征（3）有窮性。一個算法在執(zhí)行有窮步之后必須結束。反例：S1:sum=0S2:I=1S3:sum=sum+IS4:I=I+1S5:若sum>=0，返回s3;否則，算法結束。（4）輸出。算法有一個或多個輸出。（5）能行性。二、算法的描述表示算法的語言有哪幾種？表示算法的語言有自然語言、流程圖、偽代碼。1、用自然語言描述算法例:求200-500能被5整除的所有正整數(shù)。（1）分析問題。

設能被5整除的數(shù)為I,令I=200,201,202，……，500，如果I是能被5整除的數(shù)，則輸出I；否則，檢查下一個I，直到I=500為止。（2）設計算法①令I=200;②如果I能被5整除，則輸出I;③I=I+1;④如果I<=500，則返回第②；⑤結束。二、算法的描述1、用自然語言描述算法用自然語言描述算法優(yōu)點：描述的算法通俗易懂。缺點：自然語言具有歧義性，容易導致算法執(zhí)行的不確定性。自然語言描述的算法太長。當算法中循環(huán)和分支較多時，很難清晰地表示出來。自然語言表示的算法不便翻譯成計算機程序設計語言。二、算法的描述2、用流程圖描述算法圖形名稱功能起始/結束表示算法的開始或結束

輸入/輸出表示算法中變量的輸入或輸出

處理表示算法中變量的計算或賦值

判定表示算法中的判斷

流程線表示算法中的流向

連接點表示算法流向出口或入口連接點二、算法的描述2、用流程圖描述算法例:求200-500能被5整除的所有正整數(shù)。開始I=200I能被5整除輸出I的值I=I+1I<=500結束是否否是二、算法的描述2、用流程圖描述算法用流程圖描述算法優(yōu)點：描述清晰簡潔，不依賴計算機和計算機程序設計語言。缺點：畫起來費事，難以閱讀，難以修改。二、算法的描述3、用偽代碼描述算法Inputm,nr=mmodnDowhiler<>0m=nn=rr=mmodnLoopPrintn例：用輾轉(zhuǎn)相除法求兩個數(shù)的最大公約數(shù)的偽代碼。

偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法的工具。二、算法的描述3、用偽代碼描述算法用偽代碼描述算法優(yōu)點：書寫方便，格式緊湊，易于理解，便于向計算機程序設計語言過度。缺點：由于語言的種類繁多，偽代碼的語句不容易規(guī)范。三、算法在解決問題中的地位和作用探究：運行這兩個程序，比較它們的效率，把你觀察到的現(xiàn)象填在表1-6中。同學甲的算法：同學乙的算法：PrivateSubCommand1_Click()m=9147485n=5147480r=mModnDoWhiler<>0m=nn=rr=mModnLoopPrint"最大公約數(shù)=";nEndSubPrivateSubCommand1_Click()m=9147485n=5147480i=mDoWhilemModi<>0OrnModi<>0i=i-1LoopPrint"