第二章 程序的灵魂-算法.pptVIP

第二章 程序的灵魂-算法 2.1 计算机算法的概念 算法举例 ⒉算法与计算方法 算法确定性举例 ⒋算法的表示 自然语言 伪 代 码 流 程 图 计算机语言 2.2 程序流程图 流程图描述算法举例 2.3 预备知识 符号的表示：补码 小数点的表示 思考题： * 第二章 程序的灵魂-算法 Wudaixian ⒈算法（Algorithm）的定义： 广义地讲：算法是解决问题的逻辑步骤，是对特定问题求解步骤的一种描述。 计算机算法：是用程序解决问题的逻辑步骤，是指令的有限序列。 只有通过算法能够描述出来的问题，才能够通过计算机求解。能够用算法描述的问题称为可以形式化的问题。 正确的算法有三个条件： ⑴每个逻辑步骤有可以实现的语句来完成； ⑵每个步骤间的关系是唯一的； ⑶算法要能终止（防止死循环）。 ⒈求表达式sum=1+2+…+n的值sum,当sum10000时结束。 步骤： ①sum=0 ②n=0 ③n加1 ④sum加n ⑤判sum是否大于10000 如果满足关系结束； 不满足关系继续执行③。 ⒉欧几里德求m，n(mn)的最大公约数算法 ①m除以n的余数为k ②如果k不为0，n?m,k?n重复①。 ③如果k为0，n为最大公约数。 计算方法（Computational Method）: 求数学近似解的方法，如SinX=X-X3/3!+X5/5!-X7/7!+… 算法(Algorithm)：逻辑步骤,过程。 ⒊算法的特征 有穷性：有限次完成； 确定性：各步骤之间的关系要确定； 有输入：有原始数据输入； 有输出：有结果输出； 可行性：可以编程实现； 高效性：执行速度快、占用资源少； 健壮性：对数据响应正确。 商店A 图书馆l 三岔路口b 如果走近路 如果路过医院 如果路过教室 医院h 教室s 死过程 a?b if( d min)b ?l else if(to h)b ?h,h ?l else if (to s)b ?s,s ?l end a?b if(to h)b ?h，h ?l else if(to s）b ?s，s ?l else if(d min)b ?l end 1、传统流程图 概念：以特定的图形符号加上说明，表示算法的图 ，称为流程 图或框图。 规则：从上到下，从左到右。 符号及其意义： 端点框 流程线 连接点 处理框 判断框 I/O框 过程框 用框图描述函数 1 x ? 0 y =? -1 x 0 start 输入x A x ?0? y=1 y=-1 yes no A 输出y end 2、N-S流程图（自学） ⒈计算机中数值的表示方法 数值型数据的表示有三个要素： ⑴数值的绝对值； ⑵符号； ⑶小数点。 计算机内部的量都是用二进制表示的。数学表示称为真值，计 算机内部的表示称为机器数。真值转换为机器数称为编码。 计算机的计数系统是有模系统。有模系统当计数值超过系统的 “模”时系统重新计数。 如：时钟从9点，调整到6点有两种方法： 9- 3=6 9+9=12+6 12为计数系统的模，3，9互为补数。 计算机内部的量都是用二进制表示的。数学表示称为真值，计 算机内部的表示称为机器数。真值转换为机器数称为编码。 补码编码方式：2n+x。 8bit表示一个数： +1010110 100000000 + -1010110 100000000 - 10101010 最高位表示符号，其余位数表示数值。1代表-， 0代表+。 定点纯小数 0.1010100定点纯整数 -1010110浮点表示 表示的量为： M?2N M称为尾数，用定点纯小数表示。 N称为阶码，用定点纯整数表示。 定点表示 ⒉字符的表示 计算机中字符数据，用ASCII码表示，如A表示成65。 约定的小数点位置。 约定的小数点位置。 * 第二章 程序的灵魂-算法 Wudaixian