算法特征與描述導學案

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

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

3、或其他形式。三、算法描述實例 用自然語言描述算法A自然語言 人們?nèi)粘Ｉ钪惺褂玫恼Z言。 B自然 語言的特點：通俗易懂，缺乏直觀性，不簡潔，且易產(chǎn)生歧義。 P3例：三種適銷產(chǎn)品甲、乙、丙每件收入分別為4萬、3萬、2萬元；按工藝規(guī)定需要在A，B，C，D四種不同設備上加工，其加工所需時間見表。已知四種設備有效使用臺時數(shù)分別 為12、6、16、12。如何安排生產(chǎn)可使收入最大？ 產(chǎn)品甲、乙、丙在各設備上所需加工的臺時數(shù)ABCD甲2140乙2204丙1100見P3 設產(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) 也稱為程序框圖，它是算法的一種圖形化表示方法。 起止框：表示算法的開始或結束輸入、輸出框：表示輸入、輸出操作 處理框：表示處理或運算的功能判斷框：用來根據(jù)給定的條件是否滿足決定執(zhí)行兩條路徑中的某一路徑流線：表示程序執(zhí)行的路徑，箭頭代表方向連接符：表示算法流向的出口連接點或入口連接點，同一對出口與入口的連接符內(nèi)必須標以相同的數(shù)字或字母. 流程圖中常用的流程圖符號有以下幾種： 美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸

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

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

7、教授發(fā)明了以帕斯卡命名PASCAL語言,獲得了1984年度圖林獎。1983年度的圖林獎,則授予了AT&T貝爾實驗室的兩位科學家鄧尼斯·里奇 （D.Ritchie）和他的協(xié)作者肯·湯姆森（K. Thompson），以表彰他們共同發(fā)明著名C語言,現(xià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. 結束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五、操作實踐（復習式）5-1啟動VB6.0，創(chuàng)建工程，新建文件， 5-2添加命令按鈕 5-3command1_cli

10、ck代碼編程（粘貼代碼）5-4保存文件/編譯/連接/運行/返回。五、拓展：學生集體改編練習: 雞兔同籠問題求解雞兔同籠：四十九個頭，一百只腳，(頭35，足94 ), 問雞兔各幾何？（輸入a只頭，b只腳，顯示雞兔分別有多少只）設雞X只，兔Y只， 那么X+Y=a2X +4Y=b 求x,y, 方法不止一種。 測試數(shù)據(jù)一：頭49, 足100 測試數(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個頭，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 （ ） 請?zhí)羁?For y = 0 To （ ） 請?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)化？六、歸納總結算法的表示: 自然語言,傳統(tǒng)流程圖,結構化流程圖,偽代碼,PAD圖分析比較算法的三種描述方法。  窮舉算法：對于結果有窮的求解問題，利用計算機高速運算的特點，將所有可能情況進

13、行逐一驗證，從而獲得所有解答。同類問題擴展：1、整幣換零2、3、百馬問題Horse.vbp 4、鬼谷算七、知識拓展一Visual C+語言程序新建 工程WIN32 console application控制臺應用程序新建 文件C+ source file程序位置d: P3.C C語言源程序#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 ) ;知識拓展二窮舉算法. 1、百雞問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。 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)化百雞問題三 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張，且要求每種不少于一張，問有哪幾種組合？算法：設5元票i張、1元票j張, 0.5元票k張， I+j+k=100 5i+j+0.5k=100 (或 10i+2j+k=200)三個變量只能列出兩個方程，不能解，必須一個一個組合地去試，看是否能滿足條件。文件名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、百馬問題:大馬每匹馱三塊瓦，老馬每匹馱二塊瓦，小馬兩匹合馱一塊瓦。用一百匹馬馱一百塊瓦，問大馬，老馬和小馬各幾匹？ 4、九九表Tab99.c 5、古典算術：我國漢代有一位大將，名叫韓信。他每次集合部隊，都要求部下報三次數(shù)，第一次按13 報數(shù)，第二次按 15 報數(shù)，第三次按 17 報數(shù)，每次報數(shù)后都要求最后一個人報告他報的數(shù)是幾，這樣韓信就知道一共到了多少人。他的這種巧妙算法，人們稱為“鬼谷算