《算法案例》复习教案

　　此资源为用户分享，在本站免费下载，只限于您用于个人教学研究。

约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）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.