算法与程序设计第一课.ppt

第一章 揭开计算机解决问题的神秘面纱1、计算机解决问题的过程2、算法和算法的描述3、程序与程序设计语言具体问题：具体问题：华南太阳能设备厂在计划期内拟生产甲、乙、丙三种适销产品，每件销售收分别为4万元、3万元、2万元。按工艺规定，甲、乙、丙三种产品都需要在A、B、C、D四种不同的设备上加工，其加工所需要的时间见下表。已知A、B、C、D四种设备在计划期内有效使用台时数分别为12、8、16、12。如何安排生产可使收入最大？1.1、计算机解决问题的过程表1-1 产品甲、乙、丙在各设备上所需加工的台时数ABCD甲2140乙2204丙1100产品设备表1-2 探究问题记录表探究的问题探究过程找出已知和未知明确已知和未知之间的关系人工求解问题写出解题的算法已知甲乙丙销售收入，ABCD四种设备有效使用台时数，甲乙丙加工的台时数，未知的是甲乙丙的产量及总销售额。甲乙丙加工的台时数不能超过ABCD有效使用台时数。甲乙丙的产量及总销售额。穷举法2x+2y+z12X+2y+z 84x 164y 120 x 6; 0 y 6; 0 z 120 x 8; 0 y 4; 0 z 80 x 40 y 30 x 40 y 30 z 8(1)分析问题x、y、z满足以下关系式解题的目标是：求出适当的x、y、z使 f（ x、y、z ）=4x+3y+2z 取得最大值（2）设计算法第一步：把符合条件的x、y、z代入f（ x、y、z ）=4x+3y+2z 第二步：在所有 f（ x、y、z ）函数值中，找出最大值第三步：输出 f（ x、y、z ）的最大值及x、y、z的值第四步：结束以上是我们人类大概的一个解题思路，还不能让计算机直接执行。Dim x As Integer, y As Integer, z As IntegerDim x_max As Integer, y_max As Integer, z_max As IntegerDim f(4, 3, 8) As SingleDim f_max As SingleFor x = 0 To 4For y = 0 To 3For z = 0 To 8If (2 * x + 2 * y + z = 12) And (x + 2 * y + z = 8) Thenf(x, y, z) = 4 * x + 3 * y + 2 * zElsef(x, y, z) = 0End IfNext zNext yNext x源程序f_max = 0For x = 0 To 4For y = 0 To 3For z = 0 To 8If f_max f(x, y, z) Thenf_max = f(x, y, z)x_max = xy_max = yz_max = zEnd IfNext zNext yNext xPrint 当x=; x_max; ,y=; y_max; ,z=; z_max; 时,Print f(x,y,z)的最大值=; f_max具体问题分析问题设计算法编写程序运行程序验证结果得到答案用计算机解决问题的步骤实践操作实践操作1）、新建工程；2）、在窗体添加按钮控件；3）、给按钮添加单击事件过程；4）、在单击事件过程内输入编写好的程序；5）、运行程序调试结果。6、在计算机上执行该指令序列5、通过编辑、编译和连接产生计算机能够识别的指令序列4、选用一种编程语言根据算法编写程序3、生成解题算法2、寻找解题的途径和方法1、理解和分析所要解决的问题计算机解题步骤计算机解题步骤人工解题步骤人工解题步骤4、验证计算结果3、用笔、纸和算盘、计算器等工具进行计算2、寻找解题的途径和方法1、理解和分析所面临的问题人与计算机解决问题的区别相同点：无论何种解题方式，在解决某一实际问题时，都应该正确的理解问题的题意，从看似复杂的问题中整理出一个头绪，然后通过算法（即解决问题的一个一个步骤）描述出某一问题的解决过程，进行一定量的计算，最后都必须验证计算结果。 不同点：当计算量较大时，人工解题就有点力不从心了，而计算机每秒上亿次的计算速度却不在话下，并且只要算法正确，编程语句无误的话，使用计算机编写的解题程序可以反复使用。例如：sum=1+2+3+4+5+（n-1）+n这样的问题。 1.2 算法和算法描述1、算法2、算法的描述3、算法的地位和作用（1）算法的概念）算法的概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。即，用计算机求解某一问题的方法,是能被机械地执行的动作或指令的有穷集合。1）、输 入。解题算法中可以没有数据输入，也可以同时输入多个需 要算法处理的数据。 2）、确定性。解题方法中的任何一个操作步骤都是清晰无误的，不会使人产生 歧义或者误解。 3）、有穷性。任何一种提出的解题方法都是在有限的操作步骤内可以完成的， 哪怕是失败的解题方法。 4）、输 出。一个算法执行结束之后必须有数据处理结果输出，哪怕 是输出错误的数据结果，没有输出的算法使毫无意义的。 5）、能行性。解题方法中的任何一个操作步骤在现有计算机软硬件条件下和逻 辑思维中都能够实施实现。 （2）算法的特征：）算法的特征：2、算法的描述（1）、自然语言（2）、流程图（3）、伪代码自然语言平时大家所说的语言流程图 流程图也称为程序框图，它是算法的一种图形化表示方法。流程图图例开始或结束输入或输出判断处理连接点流程线伪代码 伪代码是介于自然语言和计算机程序语言之间的一种算法描述，也是专业软件开发人员描述算法的一种常用方法。辗转相除法 又名欧几里德算法（Euclidean algorithm）是求两个正整数之最大公约数的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的几何原本（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的九章算术。它并不需要把二数作质因子分解。 1. a b，令r为所得余数（0rb），若 r = 0，b 即为最大公约数；算法结束 。 2. 互换：置 ab，br，并返回第一步。 例如:求112和64的最大公约数.算法如下: (1).112除以64,余数为_; (2)_除以_余数为_; (3)_除以_余数为_. 答：112和64的最大公约数为_.两数的最大公约数乘以其最小公倍数=两数相乘例如：求112和64的最小公倍数 (1).利用辗转相除法求得它们的最大公约数为_; (2).利用表达式求得最小公倍数： 答： 112和64的最小公倍数为_.486448164816016112*64/16=44816表示算法的语言有自然语言、流程图、伪代码等。1）、用自然语言描述算法；2）、用流程图描述算法：掌握流程图的基本图形及其功能。3）、用伪代码描述算法。注意对比三种算法描述方式的优劣。1).输入m和n的值;2).r=m除以n的余数;3).如果r=0,则输出n值; 否则令m=n,n=r返回第2步;4).结束.输入正整数m和nr=m除以n的余数r=0m=n, n=r输出n的值是否输入m和n值r =m Mod ndo while r0m=nn=rr=m mod nloop输出n值开始结束优点缺点自然语言不需专门训练,通俗易懂P10流程图描述清晰简洁,容易表达选择结构;利于不同环境的程序设计.P11无法被计算机直接接受并进行操作伪代码书写方便,格式紧凑,易于理解,便于向计算机程序设计语言过渡.P12种类繁多,语句不容易规范.P12三种算法描述方式的优劣三种算法描述方式的优劣在运用计算机程序解决问题的过程中,算法设计有着举足轻重的地位和作用,算法是程序设计的核心,是程序设计的灵魂.算法的好坏,直接影响着程序的通用性和有效性,影响着问题解决的效率.程序的编制依赖于算法的设计。程序的效率主要取决于算法的效率。3、算法的地位和作用1.3、程序与程序设计语言程序设计语言的产生与发展（P18）（1）、机器语言：由“0”和“1”组成的二进制代码，是能够被计算机直接接受和 执行的计算机语言。（2）、汇编语言：采用类似英语缩写略词且带有助记性的符号形式代替二进制 机器代码的计算机语言。是符号化了的机器语言。用能反映 指令功能的助记符表达的计算机语言。（3）、高级语言：相对于汇编语言而言，它并不是特指某一种具体的语言，而是包括了很多编程语言，如VB、C、C+，VC、Java等。语言种类优势不足机器语言能被计算机直接接受和执行程序设计任务繁重，效率低下，与自然语言存在巨大鸿沟，程序员不易培养。汇编语言比机器语言更易理解必须有语言翻译器支持，效率低，汇编源程序较冗长、复杂，容易出错。高级语言更接近自然语言，移植性好。要语言翻译器支持。各种程序设计语言的比较