第二章计算机算法 第二章 瑞士科学家沃思( 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 简单算 法 举例
第二章第2节 例22求:1-+ 一+. 99100 思考:Sm=Smt 符号:初值sign=1 sign←(-1)*sign 算法:A 算法:B sl: sign=l sI: SIgn s2:和sum=1(将第一项直接纳入总和)s2:和sum=0 s3:分母den=2(第二项分母)3:分母deno=1(第一项分母) 4: sign=(-1)*sigl S4: sign=(-1)*sign s5:项term=sgn(eno)s5:项term=sgn(1/deno) s6: sum=sum+term s6: sum=sum+term s7:den0=deno+1(下一个分母)s7:deno=deno1(下一个分母) s8:deno<100?T转s4 s8:den0<100?T转s F输出sum F输出sum
例2.2 求： 思考： 符号：初值sign=1 sign (-1)*sign 算法：A 算法: B s1: sign=1 s2: 和sum=1(将第一项直接纳入总和) s3: 分母deno=2 (第二项分母) s4: sign=(-1)*sign s5: 项 term=sign*(1/deno) s6: sum=sum+term s7: deno=deno+1(下一个分母） s8: deno≤100? T 转 s4 F 输出sum 第二章 第2节 100 1 99 1 ... 5 1 4 1 3 1 2 1 1− + − + + + − n sum sum 1 = s1: sign= -1 s2: 和sum=0 s3: 分母deno=1 (第一项分母) s4: sign=(-1)*sign s5: 项 term=sign*(1/deno) s6: sum=sum+term s7: deno=deno+1(下一个分母） s8: deno≤100? T 转s4 F 输出sum
第二章第2节 思考:1)1-1+1-1 +一 3579 1+- . 21×2×31×2×3×4 例24对一个大于或等于3的正整数,判断它是否为素数 思考:对于正整数n,用2至m1的各个整数作除数与n相除,若都 不能整除(即余数0),则n为素数;否则只要有一个数能与n整除,则 n不为素数。 s1:输入n s2:除数i←2 3:计算r= n mod i(MOD求余数运算) s4:判r=0?T则输出“n不是素数”,结束 F转入s5 s5:i=i+1 s6:判还n-1?T返回S3 F则输出“n是素数”,结束
思考: 1) 2) ) 4 ...... ( 9 1 7 1 5 1 3 1 1 − + − + + = ! 1 ... 1 2 3 4 1 1 2 3 1 2 1 1 n + + + + + 例2.4 对一个大于或等于3的正整数, 判断它是否为素数。 思考：对于正整数n , 用2 至 n-1的各个整数作除数与 n 相除，若都 不能整除（即余数≠0)，则 n 为素数; 否则只要有一个数能与n 整除，则 n不为素数。 s1: 输入n s2: 除数 i ←2 s3: 计算 r = n MOD i (MOD——求余数运算） s4: 判r = 0 ? T 则输出“ n不是素数”,结束 F 转入 s5 s5: i=i+1 s6: 判 i≤ n-1? T 返回 S3 F 则输出“ n是素数”, 结束 第二章 第2节
第二章第3节 §23算法的特性 1.有穷性 有限的计算(操作)步骤 2.确定性 确切的数据参加运算,得确切的结果 3.有零个、1个、多个输入; 4.有一个、多个输出。如无解也要明确指出“无解” 5.有效性 每一步都要能有效执行 如:有语句 b-3 c-sart (a 必须考虑a有可能小于0的情况 d=5/a a不能为0 故:a>0,b>3
第二章 第3节 §2.3 算 法 的 特 性 1. 有穷性 有限的计算(操作)步骤 2. 确定性 确切的数据参加运算，得确切的结果。 3. 有零个、1个、多个输入； 4. 有一个、多个输出。如无解也要明确指出 “无解” 5. 有效性 每一步都要能有效执行 如： 有语句 a=b-3 c=sqrt (a) 必须考虑a有可能小于0的情况 d= 5/a a不能为0 故: a>0, b>3
§24算法的描述 第二章第4节 如何表示算法 一.用自然语言表示算法 用文字叙述来表示算法 问题:描述不够准确,有“歧义性”,只用于简单的算法。 如:a、b相除,结果赋给c「c=a/b c=b/a 用流程图表示算法 用图形符号 计算或操作 带箭头线条 执行顺序 由ANSI规定,国标GB152689引用 起止框 输入、输出框 处理框,计算
第二章 第4节 §2.4 算 法 的 描 述 如何表示算法 一. 用自然语言表示算法 ——用文字叙述来表示算法 问题：描述不够准确，有“歧义性”，只用于简单的算法。 如：a、b相除，结果赋给c c=a / b c=b / a ? 二 . 用流程图表示算法 用图形符号 计算或操作 带箭头线条 执行顺序 由ANSI规定， 国标GB1526—89引用 起止框 输入、输出框 处理框，计算
第二章第4节 判断框 流程线 连接点 注释框 egin 求1×2×3×4×5 (1)设一个“计数变量”i,初值ⅰ=1 (2)设一个“积”p,初值p=1 (3)p←p×i (4)i自加,i←i计+1 +1 (5)判i5?成立返回(3) 不成立转入(6) <5 (6)输出p 输出p end
第二章 第4节 判断框 流程线 连接点 注释框 求1×2×3×4×5 (1) 设一个“计数变量”i, 初值 i=1 (2) 设一个“积”p,初值p=1 (3) p p × i (4) i自加1, i i+1 (5) 判 i≤5 ? 成立,返回(3) 不成立,转入(6) (6) 输出p begin i=1 ; p=1 p = p * i i=i+1 i≤5 T 输出p end F