[计算机软件及应用]第02章_算法.pptVIP

第2章 算 法 2.1 算法的概念 2.2 计算机算法的表示方法 2.3 算法的特点及算法设计的要求 2.4 计算机程序设计的基本方法 本章重点 算法的表示方法 结构化算法的三种基本结构 算法的特点及算法设计的要求 计算机程序设计的基本方法 2 . 1 算法的概念 广义地说，为解决问题而采取的方法和步骤就称为算法。不同的问题有不同的算法，同一个问题也可以有不同的算法。 计算机中的算法是指用计算机语言解决问题的方法和步骤。 计算机处理问题的一般过程为： 计算机算法分为两类： 有数值运算算法和非数值运算算法。 数值运算：求数值解。如求方程的根、函数的积分等数学运算。 非数值运算：包括面很广。常见的如事物管理领域的金融、财务管理，人事管理，图书检索、行车调度管理等。 算法举例 【例2.1】 有8只外形相同的球，其中7只重量相同，1只较轻。用一台没有砝码的天平找出较轻的球，怎样称法？ 【方法一】 逐个球比较。 先任取2只球，分放天平的两边。若轻球已在其中，一次即可找出。若头两只球等重，则取走其中一只球，换上另一球再称，以此类推，直至分出轻重。 这种称法，碰得巧只称1次（当轻球在头两只球中时）就可找到轻球；也可能称2次、3次、……，最多要称7次（当最后一球为轻球时）。 算法举例 【方法二】 8 只球一起称。 第1步: 将8 只球平均分成两组，分放天平两边， 找出较轻的一组4 只球； 第2步: 将较轻这组的4 只球再平分为二组，分放 天平两边，找出较轻的一组2 只球； 第3步: 最后将较轻的这组2 只球分放天平两边， 即可找出轻的球。 这种称法的特点是，称一次去掉一半的球，把有哪些信誉好的足球投注网站范围缩小一半。有哪些信誉好的足球投注网站范围从8球到4球到2球，称3次即可得到结果。 依此类推，若有16只球则需称4次，32只球则称5次即可。 算法举例 【例2.2】 求sum=1+2+3+…+100 设两个变量sum和 i分别放和、加数, 将每一步的部分和放到sum变量中，算法如下： 第1步: sum=0 第2步: i=1 第3步: sum + i ? sum 第4步: i+1 ? i 第5步: 若i=100 ,则返回第3步再次执行该步及其以后各步，直到i100 ，结束算法。 可以看出，算法就是对解题过程的具体描述。 2.2 计算机算法的表示方法 2.2.1 自然语言表示算法 用人类语言描述算法，通俗易懂。 下面通过几个例子，说明用自然语言描述的计算机解题的算法。 【例2.3】任意输入三个数，按小到大排序输出。 分析：设用键盘分别输入三个数给a、b、c，大小是任意的，通过排序处理后，应使a中的数值最小，c中的数值最大，然后按a、b、c的顺序输出。 算法描述如下： S1: 输入a、b、c; S2: 如果ab，则交换a和b的内容，否则 a、b的内容不变； S3: 如果ac，则交换a和c的内容，否则 a、c的内容不变； S4: 如果bc，则交换b和c的内容，否则 b、c的内容不变； S5: 按a、b、c 的顺序输出a、b、c的值 S6: 结束。 【例2.4】 输入一个年号, 判断输出该年是否为闰年。 闰年的条件： 1.能被4整除但不被100整除的年份 2.能被100整除且能被400整除的年份 设 y 中放被检测的年份，则算法描述如下： S1: 输入年号到y变量； S2: 若y能被100整除，做第S3步判断，否则转到 S4； S3: 若 y能被400整除，则输出y是闰年，否则输 出y不是闰年；转到S5结束； S4: 若y能被4整除，则输出 y是闰年，否则输出 y不是闰年； S5: 程序结束。 【例2.5】 求 10！ 分析：设两个变量p和 i分别放被乘数和乘数，将每一步的部分积放到被乘数的变量p中。算法描述如下： S1: 设置p的初始值: p ? 1 S2: 设置i的初始值: i ? 2 S3: 得到前i项的乘积: p ? p ? i S4: 得到下一次要乘的项: i ? i+1 S5: 若i=10 , 则返回S3再次执行该步及其以 后各步, 否则输出结果p 中的值 S6: 结束。 【例2.6】求 用变量如下： sign—符号(取值:+1 或-1) , sum— 和 d—分母 , i—某一项= sign ? (1/d) 设计算法如下： S1: 符号的初始状态：sign?1 S2: 设和的初值：sum?0 S3: 设分母的初值：d?1