1、算法和程序設(shè)計,第2課 算法和算法描述的方法,第2課 算法和算法描述的方法,一個實例,求：s=1+2+3+4+5 的問題,兩種解題方法的區(qū)別,1、理解和分析面臨的問題,2、尋找解題方法,3、用紙、筆、計算器進(jìn)行計算,4、驗證計算結(jié)果,人工解題：,計算機(jī)解題：,1、理解和分析求解的問題,2、尋找解題方法,3、生成解題算法,4、選擇語言并根據(jù) 算法騙寫程序,5、編輯、編譯、連接產(chǎn)生計算機(jī)能識別的指令,6、執(zhí)行指令,求：s=1+2+3+4+5,規(guī)律：ss+i,ii+1, 求：s=1+2+3+4+5 的問題,解一：,(1+5)5/2=15,解二：,S=0,S=1,S=1+2,S=1+2+3,（等差）,

2、ss+i,ii+1,第2課 算法和算法描述的方法,另一個實例,1、農(nóng)夫帶狼、山羊、蔬菜過河的問題,一個農(nóng)夫帶著一條狼、一頭山羊和一籃蔬菜過河，但只有一條小船。每次只能讓農(nóng)夫帶一樣?xùn)|西過河，而且農(nóng)夫在場的情況下三樣?xùn)|西將相安無事。一旦農(nóng)夫不在，狼會吃羊，羊會吃蔬菜。問農(nóng)夫如何能安全地帶這三樣?xùn)|西過河？,過河步驟：,1、農(nóng)夫帶羊過河,2、農(nóng)夫回來,3、把狼帶過河,4、把羊帶回來,5、帶蔬菜過河,6、農(nóng)夫回來,7、把羊帶過河,解一：,解二：,1、農(nóng)夫帶羊過河,2、農(nóng)夫回來,3、帶蔬菜過河,4、把羊帶回來,5、把狼帶過河,6、農(nóng)夫回來,7、把羊帶過河,過河步驟區(qū)別：,1、農(nóng)夫帶羊過河,2、農(nóng)夫回來,3

3、、把狼帶過河,4、把羊帶回來,5、帶蔬菜過河,6、農(nóng)夫回來,7、把羊帶過河,3、帶蔬菜過河,5、把狼帶過河,什么是算法 ALGORITHM,(求解某一問題，所執(zhí)行的一系列操作步驟的規(guī)則。),（特點(diǎn)：有限的、可行的、確定的）,算法:是在有限步驟內(nèi)求解某一問題所使用的一組定 義明確的規(guī)則,算法的表示方法,自然語言描述算法=日常語言+數(shù)學(xué)符號,自然語言 流程圖 偽代碼,過河步驟：,1、農(nóng)夫帶羊過河,2、農(nóng)夫回來,3、把狼帶過河,4、把羊帶回來,5、帶蔬菜過河,6、農(nóng)夫回來,7、把羊帶過河,解一：,解二：,1、農(nóng)夫帶羊過河,2、農(nóng)夫回來,3、帶蔬菜過河,4、把羊帶回來,5、把狼帶過河,6、農(nóng)夫回來,7

4、、把羊帶過河, 用自然語言描述算法：,2、s0,3、i1,4、如果i=n ，做5,5、ss+i,6、ii+1,7、執(zhí)行4,否則輸出s，結(jié)束,1、輸入n的值, 求：s=1+2+3+4+5 的問題, 用流程圖來描述算法,起始,輸入n,i1,s0,i=n,ss+i,ii+1,輸出 s,結(jié)束,y,n, 用偽代碼(類C)來描述算法,算法開始,輸入n的值;,i1;,s0;,While(i=n),ss+i;,ii+1;,輸出 s 的值;,算法結(jié)束,可以加注解,/*為 i 賦初值*/,/*為s 賦初值*/,/*循環(huán)語句*/,/*循環(huán)開始*/,/*把 i 累加到 s*/,/*記數(shù)*/,/*循環(huán)結(jié)束*/,兩個基本

5、要素：,A、變化規(guī)律,B、初始狀態(tài),s=1+2+3+4+5, 1、用自然語言描述算法：,s=1+2+3+4+5,S=0,S=0+1,S=1+2 (s=3),S=1+2+3 (s=6),S=1+2+3+4 (s=10),S=1+2+3+4+5 (s=15),i,規(guī)律：,ss+i,請用自然語言描述下題的算法：,S=1+2+3+4+5+6 (s=21),S=1+2+3+4+5+6+7 (s=28),S=1+2+3+4+5+6+7+8 (s=36),+6+7+8,ii+1,i=1,i=2,i=3,i=4,i=5,i=6,i=7,i=8,s=1+2+3+4+5,S=0,S=0+1,S=1+2,S=1+2

6、+3,S=1+2+3+4,S=1+2+3+4+5,用自然語言描述算法：,規(guī)律：ss+i,ii+1,1、s0,2、i1,3、ss+i,4、ii+1,5、執(zhí)行3,1、s0,2、i1,3、如果i=5 ，做4,4、ss+i,5、ii+1,6、執(zhí)行3,否則輸出s，結(jié)束,+6+7+8,S=1+2+3+4+5+6,S=1+2+3+4+5+6+7,S=1+2+3+4+5+6+7+8,8,+n,n,輸入n的值,初值？,2、用流程圖來描述算法,流程圖符號說明：,開始、結(jié)束,處理框,判斷框,流程線,y,n,1、用自然語言描述算法：,2、s0,3、i1,4、如果i=n ，做5,5、ss+i,6、ii+1,7、執(zhí)行4,

7、否則輸出s，結(jié)束,1、輸入n的值,2、用流程圖來描述算法,流程圖符號說明：,輸入n,s0,i1,i=n,ss+i,ii+1,輸出 s,y,n, 用流程圖來描述算法, 用自然語言描述算法：,2、s0,3、i1,4、如果i=n ，做5,5、ss+i,6、ii+1,7、執(zhí)行4,否則輸出s，結(jié)束,1、輸入n的值,起始,結(jié)束, 用流程圖來描述算法,輸入n,s0,i1,i=n,ss+i,ii+1,輸出 s,y,n,算法的執(zhí)行過程：,n: s: i: 條件 i=n:,6,1,0,真,+1,+1,真,+2,+1,真,+3,+1,真,+4,+1,真,+5,+1,真,+6,+1,假,輸出 s 的值為：21,起始,結(jié)束,用流程圖表示：s=12345 n,修改此流程圖,S=1,S=12,S=123,S=1234,S=12345,規(guī)律：,ii+1,用流程圖表示：s=12345 n,初值：,ssi,s1,i1,1,用流程圖表示：s=12345 n,1,輸入n,s1,i1,i