算法特征與描述導(dǎo)學(xué)案

1、算法特征與描述導(dǎo)學(xué)案 東風(fēng)高中劉麗梅2010教學(xué)目標(biāo)1理解算法有關(guān)特征；2用自然語(yǔ)言、流程圖和偽代碼描述算法； 3了解窮舉算法。教學(xué)任務(wù)： 序號(hào)探討問(wèn)題解答1計(jì)算機(jī)解決問(wèn)題的四個(gè)步驟？2算法的特征3算法如何描述？4窮舉算法思想5VB6命令按鈕編程教學(xué)重點(diǎn)：生產(chǎn)最大收益fm.vbp, 雞兔同籠問(wèn)題JT.vbp一. 知識(shí)結(jié)構(gòu) 計(jì)算機(jī)解決問(wèn)題的過(guò)程分析問(wèn)題設(shè)計(jì)算法編寫(xiě)代碼調(diào)試運(yùn)行維護(hù)定義特征描述實(shí)例窮舉實(shí)例解析法二、知識(shí)點(diǎn)I程序設(shè)計(jì)基本步驟 1.分析問(wèn)題；2.算法設(shè)計(jì)3.代碼設(shè)計(jì)4.程序的調(diào)試與修改。其中最重要的就是算法。II.算法（Algorithm）是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確

2、的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程。算法是IT編程的“靈魂”算法定義：為解決問(wèn)題確定的方法和有限的步驟。III、算法具有五個(gè)重要特征1.有窮性： 一個(gè)算法必須保證執(zhí)行有限步驟之后結(jié)束；2.確切性： 算法的每一步驟必須有確切的定義；3.輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定出了初始條件；4.輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的； 5.可行性： 算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。IV算法描述：自然語(yǔ)言、流程圖(Float chart)、偽代碼、結(jié)構(gòu)化流程圖，PAD圖

3、或其他形式。三、算法描述實(shí)例 用自然語(yǔ)言描述算法A自然語(yǔ)言 人們?nèi)粘Ｉ钪惺褂玫恼Z(yǔ)言。 B自然 語(yǔ)言的特點(diǎn)：通俗易懂，缺乏直觀性，不簡(jiǎn)潔，且易產(chǎn)生歧義。 P3例：三種適銷產(chǎn)品甲、乙、丙每件收入分別為4萬(wàn)、3萬(wàn)、2萬(wàn)元；按工藝規(guī)定需要在A，B，C，D四種不同設(shè)備上加工，其加工所需時(shí)間見(jiàn)表。已知四種設(shè)備有效使用臺(tái)時(shí)數(shù)分別 為12、6、16、12。如何安排生產(chǎn)可使收入最大？ 產(chǎn)品甲、乙、丙在各設(shè)備上所需加工的臺(tái)時(shí)數(shù)ABCD甲2140乙2204丙1100見(jiàn)P3 設(shè)產(chǎn)品甲、乙、丙分別生產(chǎn)X，Y，Z件F(x,y,z)= 4X+3Y+2Z,2X+2Y+z<=12X+2Y+Z<=84X<=1

4、64Y<=12 用流程圖描述算法 流程圖 (Flow Chart) 也稱為程序框圖，它是算法的一種圖形化表示方法。 起止框：表示算法的開(kāi)始或結(jié)束輸入、輸出框：表示輸入、輸出操作 處理框：表示處理或運(yùn)算的功能判斷框：用來(lái)根據(jù)給定的條件是否滿足決定執(zhí)行兩條路徑中的某一路徑流線：表示程序執(zhí)行的路徑，箭頭代表方向連接符：表示算法流向的出口連接點(diǎn)或入口連接點(diǎn)，同一對(duì)出口與入口的連接符內(nèi)必須標(biāo)以相同的數(shù)字或字母. 流程圖中常用的流程圖符號(hào)有以下幾種： 美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號(hào)：起止框判斷框處理框輸

5、入/輸出框 注釋框流向線連接點(diǎn)例1 A和B互換 開(kāi)始ACBACB結(jié)束 例2從十個(gè)數(shù)中選出最大者輸一個(gè)數(shù)給B開(kāi)始輸入一個(gè)數(shù)0NABBAN+1NN9？打印出A的值結(jié)束例3 求4！用流程圖描述算法 用偽代碼描述算法 偽代碼 (Pseudocode) 是介于自然語(yǔ)言和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言之間的一種算法描述。它也是專業(yè)軟件開(kāi)發(fā)人員描述算法的一種常用方法。沒(méi)有嚴(yán)格的語(yǔ)法限制，書(shū)寫(xiě)格式也比較自由，描述的算法簡(jiǎn)單、易懂，容易修改，且容易轉(zhuǎn)化為程序語(yǔ)言代碼。 果汁酒 TBA果汁交換A，B兩個(gè)變量的值抽象簡(jiǎn)化為： T ç A A ç B B ç T四、窮舉算法與程序代碼巴科斯用于科學(xué)計(jì)

6、算的公式翻譯語(yǔ)言（FORmula TRANslator）FORTRAN摘取了1977年度圖林獎(jiǎng)。60年代美國(guó)達(dá)特默斯學(xué)院約翰·凱梅尼（J. Kemeny）和托馬斯·卡茨（T.Kurtz）研制出 “初學(xué)者通用符號(hào)指令代碼”（Beginners All purpose Symbolic Instruction Code），簡(jiǎn)稱BASIC。由于BASIC語(yǔ)言易學(xué)易用，很快就成為最流行的電腦語(yǔ)言之一，幾乎所有小型電腦和個(gè)人電腦都在使用它。不斷改進(jìn)一直沿用至今，出現(xiàn)了像QBASIC、VB等新一代BASIC版本。1971年，瑞士聯(lián)邦技術(shù)學(xué)院尼克勞斯·沃爾斯（N. Wirth）

7、教授發(fā)明了以帕斯卡命名PASCAL語(yǔ)言,獲得了1984年度圖林獎(jiǎng)。1983年度的圖林獎(jiǎng),則授予了AT&T貝爾實(shí)驗(yàn)室的兩位科學(xué)家鄧尼斯·里奇 （D.Ritchie）和他的協(xié)作者肯·湯姆森（K. Thompson），以表彰他們共同發(fā)明著名C語(yǔ)言,現(xiàn)今軟件工程師最寵愛(ài)的語(yǔ)言之一。窮舉算法：對(duì)于結(jié)果有窮的求解問(wèn)題，利用計(jì)算機(jī)高速運(yùn)算的特點(diǎn)，將所有可能情況進(jìn)行逐一驗(yàn)證，從而獲得所有解答。例P3.vbpStep1. F(x,y,z)=4*X+3*Y+2*ZStep2. 從所有(x,y,z)/x0,4,y0,3,z0,8中，找出最大值fm=MAXf (0,0,0), f(4,3,

8、8)Step3. 輸出fm, x, y, z Step4. 結(jié)束Privte sub command1_click()Dim x As integer, y As integer, z As integerDim xm As integer, ym As integer, zm As integerDim f(4, 3, 8) As Single, fm As Singlefm = 0For x = 0 To 4 For y = 0 To 3 For z = 0 To 8 If (2 * x + 2 * y + z <= 12) And (x + 2 * y + z <= 8) T

9、hen f(x, y, z) = 4 * x + 3 * y + 2 * z Print "f=" f(x,y,z), x, y, z Else f(x, y, z) = 0End If If fm < f(x, y, z) Then fm = f(x, y, z) xm = x : ym = y : zm = z End IfNext zNext yNext xPrint "f_max=" fm, xm, ym, zmend sub五、操作實(shí)踐（復(fù)習(xí)式）5-1啟動(dòng)VB6.0，創(chuàng)建工程，新建文件， 5-2添加命令按鈕 5-3command1_cli

10、ck代碼編程（粘貼代碼）5-4保存文件/編譯/連接/運(yùn)行/返回。五、拓展：學(xué)生集體改編練習(xí): 雞兔同籠問(wèn)題求解雞兔同籠：四十九個(gè)頭，一百只腳，(頭35，足94 ), 問(wèn)雞兔各幾何？（輸入a只頭，b只腳，顯示雞兔分別有多少只）設(shè)雞X只，兔Y只， 那么X+Y=a2X +4Y=b 求x,y, 方法不止一種。 測(cè)試數(shù)據(jù)一：頭49, 足100 測(cè)試數(shù)據(jù)二：頭35, 足94方法一：解析法Setp1. 輸入a,bStep2. 解方程得 X=2a-b/2 Y=b/2-aStep3. 輸出X，YPrivte sub command2_click()A=Inputbox(“ Input heads =?”)B=I

11、nputbox(“Input feet =?”)X=2*a-b/2Y=b/2-aPrint “x =”; x , Print ”y =”;y end sub方法二：窮舉法X，Y 取值范圍 : 0Xa , 0Ya X 0 0 1 aY 0 1 0 a 限制條件：X+Y=a 且2X +4Y=b； 輸入a=35個(gè)頭，b=94只腳；Privte sub command3_click()Dim x As Integer, y As IntegerClsa = InputBox(" heads a=?")b = InputBox(" feet b=?")F

12、or x = 0 To （ ） 請(qǐng)?zhí)羁?For y = 0 To （ ） 請(qǐng)?zhí)羁?If (x + y = a) And (2 * x + 4 * y = b) Then Print "chiken " x, "babbits " y MsgBox ("單擊確定返回") End If Next y Next xend sub思考：程序如何優(yōu)化？六、歸納總結(jié)算法的表示: 自然語(yǔ)言,傳統(tǒng)流程圖,結(jié)構(gòu)化流程圖,偽代碼,PAD圖分析比較算法的三種描述方法。  窮舉算法：對(duì)于結(jié)果有窮的求解問(wèn)題，利用計(jì)算機(jī)高速運(yùn)算的特點(diǎn)，將所有可能情況進(jìn)

13、行逐一驗(yàn)證，從而獲得所有解答。同類問(wèn)題擴(kuò)展：1、整幣換零2、3、百馬問(wèn)題Horse.vbp 4、鬼谷算七、知識(shí)拓展一Visual C+語(yǔ)言程序新建 工程WIN32 console application控制臺(tái)應(yīng)用程序新建 文件C+ source file程序位置d: P3.C C語(yǔ)言源程序#include <stdio.h>main()int x,y,z,xm,ym,zm, f549, fm =0;for (x =0 ;x<=4;x+) for (y=0;y<=3;y+) for (z=0;z<=8;z+) if (2*x+2*y+z<=12) &&

14、amp; (x+2*y+z<=8) fxyz= 4*x+3*y+2*z; else fxyz=0; /* printf("f=%d %d %d %dn",fxyz,x,y,z); */ if (fm< fxyz) fm= fxyz; xm=x; ym=y; zm=z; printf("fm=%d xm= %d ym=%d zm=%dn", fm, xm , ym, zm ) ;知識(shí)拓展二窮舉算法. 1、百雞問(wèn)題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。 X+Y+Z=100 （只 ）5*X+3*Y+z/3=100 （錢 ）不定方程求整數(shù)

15、解，用窮舉法.Cock XX. vbpCock XX. cppDim c as integerC=0FOR X=0 to 100 FORY= 0 to100For Z=0 to 100 IF ( X+Y+Z=100) AND (5*X+3*Y+z/3=100) THEN Print x, y ,z C=c+1 End if Next zNext yNext xPrint “total =”;cend#include <stdio.h>main() int c=0,x,y,z;for (x=0;i<100;x+） for (y= 0 ;y<100;y+)for (z=0

16、;z<100;z+) if ( x+y+z=100)&& (15*x+9*y+z=300) printf(“x=%d,y=%d,z=%dn”,x,y,z); c+; printf(“total=%d”,cn);改編窮舉算法，優(yōu)化百雞問(wèn)題三 for(i=0; i<100; i+) for(i=0; i<100; i+)k=100-i-j;if ( i +j + k = = 100) && (5*I+j+0.5*k = =100) printf (“%d, %d, %d” , i , j , k); 2、整幣換零。將一張面值100元的人民幣換成5元

17、、1元和0.5元面值的零幣共100張，且要求每種不少于一張，問(wèn)有哪幾種組合？算法：設(shè)5元票i張、1元票j張, 0.5元票k張， I+j+k=100 5i+j+0.5k=100 (或 10i+2j+k=200)三個(gè)變量只能列出兩個(gè)方程，不能解，必須一個(gè)一個(gè)組合地去試，看是否能滿足條件。文件名Money.vbp附Money.c#include <stdio.h>main() int i,j,k=0 ,c=0; /*將累加器c初始化為0*/ for(i=1; i<100; i+) for(i=1; i<100; i+)k=100-i-j;if ( (i+j+k= =100) && (5*i+j+0.5*k= =100) printf("%d,%d,%dn",I,j,k);c+; 3、百馬問(wèn)題:大馬每匹馱三塊瓦，老馬每匹馱二塊瓦，小馬兩匹合馱一塊瓦。用一百匹馬馱一百塊瓦，問(wèn)大馬，老馬和小馬各幾匹？ 4、九九表Tab99.c 5、古典算術(shù)：我國(guó)漢代有一位大將，名叫韓信。他每次集合部隊(duì)，都要求部下報(bào)三次數(shù)，第一次按13 報(bào)數(shù)，第二次按 15 報(bào)數(shù)，第三次按 17 報(bào)數(shù)，每次報(bào)數(shù)后都要求最后一個(gè)人報(bào)告他報(bào)的數(shù)是幾，這樣韓信就知道一共到了多少人。他的這種巧妙算法，人們稱為“鬼谷算