《算法案例》复习教案
- 资源简介:
约2230字。
§ 13.3 算法案例
一、知识导学
1.算法设计思想:
(1)“韩信点兵—孙子问题”对正整数m从2开始逐一检验条件,若三个条件中有任何一个不满足,则m递增1,一直到m同时满足三个条件为止(循环过程用Goto语句实现)
(2)用辗转相除法找出 的最大公约数的步骤是:计算出 的余数 ,若 ,则 为 的最大公约数;若 ,则把前面的除数 作为新的被除数,继续运算,直到余数为0,此时的除数即为正整数 的最大公约数.
2.更相减损术的步骤:(1)任意给出两个正数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.(2)以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数.
(3)二分法求方程 在区间 内的一个近似解 的解题步骤可表示为
S1 取[ ]的中点 ,将区间 一分为二;
S2 若 ,则 就是方程的根;否则判别根 在 的左侧还是右侧:
若 , ,以 代替 ;
若 ,则 ,以 代替 ;
S3 若 ,计算终止,此时 ,否则转S1.
二、疑难知识导析
1. 表示不超过 的整数部分,如 ,但当 是负数时极易出错,如 就是错误的,应为-2.
2. 表示 除以 所得的余数,也可用 表示.
3.辗转相除法与更相减损术求最大公约数的联系与区别:
(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显.
资源评论
共有 0位用户发表了评论 查看完整内容我要评价此资源