算法特征与描述导学案

1、算法特征与描述导学案 东风高中刘丽梅2010教学目标1理解算法有关特征；2用自然语言、流程图和伪代码描述算法； 3了解穷举算法。教学任务： 序号探讨问题解答1计算机解决问题的四个步骤？2算法的特征3算法如何描述？4穷举算法思想5VB6命令按钮编程教学重点：生产最大收益fm.vbp, 鸡兔同笼问题JT.vbp一. 知识结构 计算机解决问题的过程分析问题设计算法编写代码调试运行维护定义特征描述实例穷举实例解析法二、知识点I程序设计基本步骤其中最重要的就是算法。II.算法（Algorithm）是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。算法是IT编程的“灵魂

2、”算法定义：为解决问题确定的方法和有限的步骤。III、算法具有五个重要特征1.有穷性： 一个算法必须保证执行有限步骤之后结束；2.确切性： 算法的每一步骤必须有确切的定义；3.输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4.输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5.可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。IV算法描述：自然语言、流程图(Float chart)、伪代码、结构化流程图，PAD图或其他形式。三、算法描述实例 用自然语言描述算法A自然语言 人

3、们日常生活中使用的语言。 B自然 语言的特点：通俗易懂，缺乏直观性，不简洁，且易产生歧义。 P3例：三种适销产品甲、乙、丙每件收入分别为4万、3万、2万元；按工艺规定需要在A，B，C，D四种不同设备上加工，其加工所需时间见表。已知四种设备有效使用台时数分别 为12、6、16、12。如何安排生产可使收入最大？ 产品甲、乙、丙在各设备上所需加工的台时数ABCD甲2140乙2204丙1100见P3 设产品甲、乙、丙分别生产X，Y，Z件F(x,y,z)= 4X+3Y+2Z,2X+2Y+z<=12X+2Y+Z<=84X<=164Y<=12 用流程图描述算法 流程图 (Flow C

4、hart) 也称为程序框图，它是算法的一种图形化表示方法。 起止框：表示算法的开始或结束输入、输出框：表示输入、输出操作 处理框：表示处理或运算的功能判断框：用来根据给定的条件是否满足决定执行两条路径中的某一路径流线：表示程序执行的路径，箭头代表方向连接符：表示算法流向的出口连接点或入口连接点，同一对出口与入口的连接符内必须标以相同的数字或字母. 流程图中常用的流程图符号有以下几种： 美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：起止框判断框处理框输入/输出框 注释框流向线连接点例1 A和B互换 开始ACBAC

5、B结束 例2从十个数中选出最大者输一个数给B开始输入一个数0NABBAN+1NN9？打印出A的值结束例3 求4！用流程图描述算法 用伪代码描述算法 伪代码 (Pseudocode) 是介于自然语言和计算机程序设计语言之间的一种算法描述。它也是专业软件开发人员描述算法的一种常用方法。没有严格的语法限制，书写格式也比较自由，描述的算法简单、易懂，容易修改，且容易转化为程序语言代码。 果汁酒 TBA果汁交换A，B两个变量的值抽象简化为： T ç A A ç B B ç T四、穷举算法与程序代码巴科斯用于科学计算的公式翻译语言（FORmula TRANslator）FOR

6、TRAN摘取了1977年度图林奖。60年代美国达特默斯学院约翰·凯梅尼（J. Kemeny）和托马斯·卡茨（T.Kurtz）研制出 “初学者通用符号指令代码”（Beginners All purpose Symbolic Instruction Code），简称BASIC。由于BASIC语言易学易用，很快就成为最流行的电脑语言之一，几乎所有小型电脑和个人电脑都在使用它。不断改进一直沿用至今，出现了像QBASIC、VB等新一代BASIC版本。1971年，瑞士联邦技术学院尼克劳斯·沃尔斯（N. Wirth）教授发明了以帕斯卡命名PASCAL语言,获得了1984年度图林

7、奖。1983年度的图林奖,则授予了AT&T贝尔实验室的两位科学家邓尼斯·里奇 （D.Ritchie）和他的协作者肯·汤姆森（K. Thompson），以表彰他们共同发明著名C语言,现今软件工程师最宠爱的语言之一。穷举算法：对于结果有穷的求解问题，利用计算机高速运算的特点，将所有可能情况进行逐一验证，从而获得所有解答。例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)Step3. 输出fm, x, y, z Step4. 结

8、束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) Then f(x, y, z) = 4 * x + 3 * y

9、+ 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，创建工程，新建文件， 5-2添加命令按钮 5-3command1_click代码编程（粘贴代码）5-4保存文件/编译/连接/运行/返回

10、。五、拓展：学生集体改编练习: 鸡兔同笼问题求解鸡兔同笼：四十九个头，一百只脚，(头35，足94 ), 问鸡兔各几何？（输入a只头，b只脚，显示鸡兔分别有多少只）设鸡X只，兔Y只， 那么X+Y=a2X +4Y=b 求x,y, 方法不止一种。 测试数据一：头49, 足100 测试数据二：头35, 足94方法一：解析法Setp1. 输入a,bStep2. 解方程得 X=2a-b/2 Y=b/2-aStep3. 输出X，YPrivte sub command2_click()A=Inputbox(“ Input heads =?”)B=Inputbox(“Input feet =?”)X=2*a-b

11、/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=?")For x = 0 To （ ） 请填空 For y = 0 T

12、o （ ） 请填空 If (x + y = a) And (2 * x + 4 * y = b) Then Print "chiken " x, "babbits " y MsgBox ("单击确定返回") End If Next y Next xend sub思考：程序如何优化？六、归纳总结算法的表示: 自然语言,传统流程图,结构化流程图,伪代码,PAD图分析比较算法的三种描述方法。  穷举算法：对于结果有穷的求解问题，利用计算机高速运算的特点，将所有可能情况进行逐一验证，从而获得所有解答。同类问题扩展：1、整币换零2、3

13、、百马问题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) && (x+2*y+z<=8) fxyz= 4*x+

14、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 （钱 ）不定方程求整数解，用穷举法.Cock XX. vbpCock XX. cpp

15、Dim 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 ;z<100;z+) if ( x+y+z=100)&a

16、mp;& (15*x+9*y+z=300) printf(“x=%d,y=%d,z=%dn”,x,y,z); c+; printf(“total=%d”,cn);改编穷举算法，优化百鸡问题三 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元、1元和0.5元面值的零币共100张，且要求每种不少于一张，问

17、有哪几种组合？算法：设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、古典算术：我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按13 报数，第二次按 15 报数，第三次按 17 报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一共到了多少人。他的这种巧妙算法，人们称为“鬼谷算”