1、認(rèn)識(shí)算法,教學(xué)目標(biāo),1.通過對(duì)解決具體問題的過程和步驟的分析，體會(huì)算法的基本思想，了解算法的含義。 2.學(xué)會(huì)使用流程圖表示算法,重點(diǎn)難點(diǎn),重點(diǎn)：算法的特點(diǎn)和描述方式 難點(diǎn)：將具體問題轉(zhuǎn)換成算法,問題引入：一個(gè)農(nóng)夫帶著一條狼、一頭山羊和一籃蔬菜過河，但只有一條小船。乘船時(shí)，農(nóng)夫只能帶一樣?xùn)|西。當(dāng)農(nóng)夫在場(chǎng)的時(shí)候，這三樣?xùn)|西相安無事，一旦農(nóng)夫不在，狼會(huì)吃羊，羊會(huì)吃菜。請(qǐng)?jiān)O(shè)計(jì)一個(gè)方案，使農(nóng)夫能安全的將這三樣?xùn)|西帶過河 。,第一步：農(nóng)夫帶羊過河 第二步：農(nóng)夫獨(dú)自回來 第三步：農(nóng)夫帶狼過河 第四步：農(nóng)夫帶羊回來 第五步：農(nóng)夫帶菜過河 第六步：農(nóng)夫獨(dú)自回來 第七部：農(nóng)夫帶羊過河,算法的概念,為解決一個(gè)問題而

2、采取的方法和步驟，稱為“算法”（Algorithm）?；蛘哒f，算法是解題方法的精確描述，解決一個(gè)問題的過程就是實(shí)現(xiàn)一個(gè)算法的過程。,簡(jiǎn)單算法舉例（1）,有兩個(gè)杯子A和B，分別盛放酒和醋，要求將它們互換（即A杯原來盛放酒，現(xiàn)要改盛醋，B杯則相反）,空,算法,必須增加一個(gè)空杯C作為過渡，其算法可以表示為： 步驟一：先將A杯中的酒倒在C杯中； 步驟二：再將B杯中的醋倒在A杯中； 步驟三：最后將C杯中的酒倒在B杯中；,上面的算法可以簡(jiǎn)化表示如下： AC BA CB,簡(jiǎn)單算法舉例（2）,如何從十個(gè)數(shù)中挑選出最大的數(shù)？ 思路：這個(gè)問題的解決思路可以用“打擂臺(tái)”來比喻：先有任意一人在臺(tái)上，然后第二個(gè)人與他比

3、武，勝者留在臺(tái)上，如此繼續(xù)下去，直到第十個(gè)人比完為止（一共比次）？，最后留在臺(tái)上者為勝。,算法, 先任選一數(shù)放在一個(gè)匣子A中； 將第二個(gè)數(shù)與A匣子中的數(shù)相比，大者放入A匣子中； 再將第三個(gè)數(shù)與A匣子中的數(shù)相比，大者放入A匣子中； 最后將第十個(gè)數(shù)與A匣子中的數(shù)相比，大者放入A匣子中，此時(shí)A匣子中數(shù)就是最大的數(shù)；,算法的特點(diǎn),一個(gè)正確的算法應(yīng)該有如下特征： 一.有窮性 二.確定性 三.可行性 四.有零個(gè)或多個(gè)輸入 五.有一個(gè)或多個(gè)輸出,算法的特點(diǎn),一.有窮性：一個(gè)算法必須保證它的執(zhí)行步驟是有限的 二.確定性：步驟必須有確切含義 三.可行性：算法原則上能夠精確地運(yùn)行 四.有零個(gè)或多個(gè)輸入（即可以沒有

4、輸入） 五.有一個(gè)或多個(gè)輸出（即必須要有輸出）,算法的描述,1.自然語言 2.偽代碼 3.流程圖,偽代碼,偽代碼,代碼,#includemain()int a,b,c,max;printf(input 3 numbers:);scanf(%d%d%d,例如：輸入3個(gè)數(shù)，打印輸出其中最大的數(shù)。,Begin（算法開始） 輸入 A，B，C IF AB 則 AMax 否則 BMax IF CMax 則 CMax Print Max End （算法結(jié)束）,算法,必須增加一個(gè)空杯C作為過渡，其算法可以表示為： 步驟一：先將A杯中的酒倒在C杯中； 步驟二：再將B杯中的醋倒在A杯中； 步驟三：最后將C杯中的酒

5、倒在B杯中；,上面的算法可以簡(jiǎn)化表示如下： AC BA CB,流程圖表示法圖例,用流程圖來描述算法要遵循一定的標(biāo)準(zhǔn)，這套標(biāo)準(zhǔn)中最常用的符號(hào)有：,開始或結(jié)束,輸入或輸出,判斷,處理,連接線,0,N,Y,輸出方程無解,輸出x,開始,結(jié)束,思考題(1),問題：任意給定3個(gè)正實(shí)數(shù),設(shè)計(jì)一個(gè)算法,判斷分別以這三個(gè)數(shù)為三邊邊長(zhǎng)的三角形是否存在.畫出這個(gè)算法的程序框圖.,開始,輸入a,b,c,三角形存在,結(jié)束,a+bc,a+cb, b+ca是否 同時(shí)成立?,三角形不存在,Y,N,思考題(2),問題：已知矩形的長(zhǎng)和寬，求矩形的面積。 求矩形面積的方法是：矩形面積=長(zhǎng)寬。如果設(shè)計(jì)的程序只能計(jì)算固定的長(zhǎng)和寬，那么

6、，這個(gè)程序就沒有什么實(shí)用性了。 用變量a、b、s分別代表矩形的長(zhǎng)、寬、面積，則s的值應(yīng)該是ab的計(jì)算結(jié)果。,程序的執(zhí)行流程應(yīng)該是：,輸入兩個(gè)數(shù)值給a、b,通過計(jì)算ab，將結(jié)果給變量s,輸出變量s的值,用流程圖表示上述算法,開始,輸入長(zhǎng)到變量a,輸入長(zhǎng)到變量b,計(jì)算：sab,輸出面積s,結(jié)束,表示先計(jì)算ab的值，然后將計(jì)算的結(jié)果存入變量s中。 “”稱為賦值符，它的計(jì)算過程是：先計(jì)算符號(hào)右側(cè)的代數(shù)式的結(jié)果，然后將計(jì)算結(jié)果存儲(chǔ)到符號(hào)左側(cè)的變量中。,思考題(3),問題：設(shè)計(jì)一算法，求和:1+2+3+100,開始,i=1，S=0,S=S+i,i=i+1,i100,輸出S,結(jié)束,Y,N,思考題(4),設(shè)計(jì)“判斷大于1的整數(shù)n是否為質(zhì)數(shù)”的算法 第一步：判斷n是否等于2，若n=2，則n是質(zhì)數(shù)；若n2，則執(zhí)行第二步。 第二步：用n除以2，得到余數(shù)r，若r=0，則n能被2整除，n不是質(zhì)數(shù)，算法結(jié)束，否則執(zhí)行下一步。 第三步：用n除以3，得到余數(shù)r，若r=0，則n能被3整除，n不是質(zhì)數(shù)，算法結(jié)束，否則執(zhí)行下一步。 第n-1步：用n除以(n-1)，得到余數(shù)r，若r=0，則n能被(n-1)整除，n不是質(zhì)數(shù)，算法結(jié)束，否則n是質(zhì)數(shù) 。,第二步：依次從2（n-1）檢驗(yàn)是不是 n 的因數(shù)，即整除 n 的數(shù)。若有這樣的數(shù)，則n不是質(zhì)數(shù)，若沒