第二章计算机算法 第二章 瑞士科学家沃思( Nikiklaus wirth)提出(1976),程序应包括两方面的内容 1数据的描述即如何在计算机中表示数据(数据结构 data structure 问题:如一个内存单元(即Byte,共8个二进制位)的所有位均为l,即: 11111111 值 有符号数(int) (无符号数( unsigned int→28-1=255注意:补码的概念 浮点数(foat) 1111 内存中同样的数据, 符号整数符号纯小数 型不同,其值不相同 阶码 尾数 !高级语言中用户可通过定义变量(补) (原) 的类型来实现数据描述而不必关心数(-1)2(-0.1112=-09375 据在内存中的具体存放形式。 2-1×-09375=0.46875
第二章 有符号数(int) -1 无符号数(unsigned int) 2 8－1=255 浮点数(float) 1 1 1 1 1 1 1 1 符号 整数 符号 纯小数 阶码 尾数 （补） （原） （ -1）2 （-0.1111) 2= -0.9375 2 -1×-0.9375=-0.46875 1 1 1 1 1 1 1 1 内存中同样的数据, 类型不同, 其值不相同! 注意: 补码的概念 值=? !!在高级语言中,用户可通过定义变量 的类型来实现数据描述,而不必关心数 据在内存中的具体存放形式。 瑞士科学家沃思（Nikiklaus Wirth)提出（1976）,程序应包括两方面的内容 1.数据的描述 即如何在计算机中表示数据（数据结构data structure） 问题:如一个内存单元（即1Byte,共8个二进制位）的所有位均为1，即：
第二章 2.计算步骤一算法。解决“做什么”“怎么做”,是程序的“骨架” ∴程序=数据结构+算法+程序设计方法+语言工具及运行环境 遵循科学有效的借助于程序设计语言 定义数据类型骨架」方法一“结构化程和操作系统 序设计方法” §21算法的概念 概念 算法—为解决一个实际问题而采取的方法和有限的计算(操作) 步骤。 例:输入100个数,示总和。 算法1:(1)第1个数输入计算机 (2)第2个数输入计算机 a2 (3)以上两数相加 sum←a1+a2 (4)输入第3个数 3
第二章 2. 计算步骤—算法。解决“做什么”“怎么做”，是程序的“骨架” ∴程序=数据结构+算法+程序设计方法+语言工具及运行环境 定义数据类型 骨架 遵循科学有效的 方法—“结构化程 序设计方法” 借助于程序设计语言 和操作系统 一.概 念 算法——为解决一个实际问题而采取的方法和有限的计算（操作） 步骤。 例： 输入100个数，示总和。 算法1： (1)第1个数输入计算机 a1 (2) 第2个数输入计算机 a2 (3)以上两数相加 sum←a1+a2 (4)输入第3个数 a3 §2.1 算 法 的 概 念
第二章第1节 (5)第3个数与前两数之和相加sum←sum+a3 198将第100个数输入 a100 (199)与前9个数之和相加sum←sum+a100 (200)打印输出总和 问题:书写太长。如输入1000个数,更长。不具有普遍意义 算法2(1)设一个“计数变量”N,令初值N=0 (2)设一个“累加变量”sum,令初值sum=0 (3)输入一个数给变量a (4)sum←sum+a (5)N的值加1,(表示已经加了一个数)N←N+1 (6)如N100则返回(3,否则执行(7) 或:如N>100则返回(7),否则执行3) (7)打印输出sum 优点:算法精练,有一定的通用性
第二章 第1节 (5)第3个数与前两数之和相加 sum ←sum+a3 ………….. (198)将第100个数输入 a100 (199)与前99个数之和相加 sum ←sum+a100 (200)打印输出总和 问题: 书写太长。如输入1000个数，更长。不具有普遍意义 算法2 (1) 设一个“计数变量”N ，令初值N=0 (2) 设一个“累加变量”sum ， 令初值sum=0 (3) 输入一个数给变量 a (4) sum ←sum+a (5) N的值加1，（表示已经加了一个数）N ←N+1 (6) 如N≤100 则返回(3), 否则执行(7) 或:如N>100 则返回(7), 否则执行(3) (7) 打印输出sum 优点: 算法精练, 有一定的通用性
第二章第1节 二.算法的分类 1.数值运算算法 如:求线性方程组,求非性线方根的根,计算定积分等 《计算方法》研究本类问题 2.非数值运算算法 如:资料检索,调度,人工智能等—→有待于进一步完善 对算法的要求 1.正确性 尤其重要 2.容易阅读理解 3.计算机执行时具有较高的效率 1)得到结果的时间少(步骤不能太多 2)占用内存少(程序不能太长,变量不能太多
第二章 第1节 二. 算法的分类 1. 数值运算算法 如： 求线性方程组, 求非性线方根的根, 计算定积分等 《计算方法》研究本类问题 2. 非数值运算算法 如：资料检索,调度,人工智能等 有待于进一步完善 三. 对算法的要求 1. 正确性 2. 容易阅读理解 3. 计算机执行时具有较高的效率 1) 得到结果的时间少 (步骤不能太多) 2)占用内存少 (程序不能太长,变量不能太多) 尤其重要
第二章第2节 §22简单算法举例 例2.1求1×2×3×4×5 (1)设一个“计数变量”i 初值i=1 (2)设一个“积 初值p=1(注p≠0) (3)计算p×i,结果仍赋给p i (4)i加1 i←i+1(为下一次计算 作准备) (5)判还5?成立,返回3) 不成立,转入(6) (6)输出p 问题:求1×3×5×7×9×11? s6:输出p SL: p p←-p s4:i←i+2 s5如i≤11T转向s3 F转向s6
第二章 第2节 例 2. 1 求1×2×3×4×5 (1) 设一个“计数变量”i, 初值 i=1 (2) 设一个“积”p, 初值p=1(注p ≠ 0) (3) 计算p × i , 结果仍赋给p p p × i (4) i自加1 i i+1 (为下一次计算 作准备) (5) 判 i≤5 ? 成立,返回(3) 不成立,转入(6) (6) 输出p 问题: 求1×3×5×7×9 ×11 ? s1: i 1 s6: 输出 p s2: p 1 s3: p p*i s4: i i +2 s5 如 i ≤11 T 转向s3 F 转向s6 §2.2 简单算 法 举例