《算法案例》课件（2）.ppt

算法案例 问题1 如何求12与20的最大公约数 提示 短除法 一般情况下数字不应过大 问题2 若求6750与3492的最大公约数 上述方法还奏效吗 提示 数值很大时短除法不方便用 问题3 对于问题1中12与20的最大公约数是4 若用20除以12余8 再用8去除12余4 再用4去除8余数为0 也可求得最大公约数为4 若对较大两数可否用此法求公约数 提示 可以 1 孙子问题 1 问题名称 人们将 韩信点兵 孙子问题 这种问题的通用解法称为 或 中国剩余定理 孙子剩余定理 正整数 2 欧几里得辗转相除法 1 含义 公元前3世纪 欧几里得在 原本 第七篇中介绍了求两个正整数a b a b 的的方法 这种方法称为 欧几里得辗转相除法 2 步骤 计算出a b的余数r 若r 0 则b即为a b的最大公约数 若r 0 则把作为新的被除数 把作为新的除数 继续运算 直到 此时的除数即为a b的最大公约数 最大公约数 前面的除数b 余数r 余数为0 3 两个常用函数 1 mod a b 表示a除以b所得的 2 int x 表示的最大整数 余数 不超过x 1 由除法和减法的性质可知 对于任意两个正整数 辗转相除法或更相减损术总可以在有限步之后完成 故总能用这两种方法求出任意两个正整数的最大公约数 2 辗转相除法的理论依据是 由a nb r r a nb得a b与b r有相同的公约数 例1 有3个连续的正整数 其中最小的能被15整除 中间的能被17整除 最大的能被19整除 画出求满足要求的一组三个连续正整数的流程图 并写出伪代码 思路点拨 设这三个数分别为m m 1 m 2 则m满足的条件是mod m 15 0且mod m 1 17 0且mod m 2 19 0 精解详析 流程图 一点通 解决此类问题的方法就是从m 2开始 对每一个正整数逐一检验 当m满足所有已知条件时 结束循环 输出m 1 如图所示的流程图 输出的结果是 解析 m 10时 不满足条件 则m 10 7 m 17时 mod m 3 2且mod m 5 2成立 故输出17 答案 17 2 下面一段伪代码的功能是 解析 由代码含义可知 m满足的条件是除以2余1 除以3余2 除以5余3 又m逐个增大 故输出的m是满足条件的最小正整数 例2 2011 汕头六都中学高一期末 设计用辗转相除法求8251与6105的最大公约数的算法 并画出流程图 写出伪代码 思路点拨 按照辗转相除法的步骤设计算法 画流程图 根据流程图 写出伪代码 精解详析 算法如下s1a 8251 s2b 6105 s3如果mod a b 0 那么转s4 否则转s7 s4r mod a b s5a b s6b r 转s3 s7输出b 流程图与伪代码 一点通 辗转相除法是当大数被小数除尽时 结束除法运算 较小的数就是最大公约数 3 下图表示的流程图 输出的结果是 解析 第一次执行循环体 r 34 a 119 b 34 第二次执行循环体r 17 a 34 b 17 第三次执行循环体r 0 输出b 17 答案 17 4 若输入72 42 则下面一段伪代码输出的结果是 答案 6 例3 12分 设计用二分法求方程x3 2 0在区间 1 2 内的近似解 误差不超过0 005 的流程图 写出伪代码 思路点拨 根据二分法求方程近似解的步骤画出流程图 然后根据流程图写出算法伪代码 精解详析 流程图如图 12分 一点通 针对这个类型的题目书写伪代码时一定要注意伪代码的具体格式 另外循环语句中一定包含有条件结构的语句 求高次方程近似解时 一定要给出精确度 5 下面的流程图表示的算法的功能是 答案 用二分法求方程x2 3x 1 0在区间 0 1 内的一个近似解 误差不超过0 001 6 试用伪代码写出用二分法求方程2x3 4x2 3x 6 0在区间 10 10 之间的一个近似解 误差不超过0 001 的一个算法 1 用辗转相除法求两个数最大公约数的操作过程是先用较大的数除以较小的数 得商和余数 再用除数除以余数 重复操作 直