苏教版必修3 1.4 算法案例 学案.doc

问题1：如何求12与20的最大公约数？提示：短除法一般情况下数字不应过大问题2：若求6 750与3 492的最大公约数，上述方法还奏效吗？提示：数值很大时短除法不方便用问题3：对于问题1中12与20的最大公约数是4.若用20除以12余8，再用8去除12余4，再用4去除8余数为0，也可求得最大公约数为4.若对较大两数可否用此法求公约数？提示：可以1孙子问题(1)问题名称：人们将“韩信点兵孙子问题”这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”(2)问题思想：“孙子问题”相当于求关于x，y，z的不定方程组2欧几里得辗转相除法(1)含义：公元前3世纪，欧几里得在原本第七篇中介绍了求两个正整数a，b(ab)的最大公约数的方法，这种方法称为“欧几里得辗转相除法”(2)步骤：计算出ab的余数r，若r0，则b即为a，b的最大公约数；若r0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为a，b的最大公约数3两个常用函数(1)mod(a，b)表示a除以b所得的余数(2)int(x)表示不超过x的最大整数1由除法和减法的性质可知，对于任意两个正整数，辗转相除法或更相减损术总可以在有限步之后完成，故总能用这两种方法求出任意两个正整数的最大公约数2辗转相除法的理论依据是：由anbrranb得a、b与b、r有相同的公约数 例1有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码思路点拨设这三个数分别为m，m1，m2，则m满足的条件是mod(m,15)0且mod(m1,17)0且mod(m2,19)0.精解详析流程图：伪代码：m2while mod(m,15)0or mod(m1,17)0or mod(m2,19)0mm1end whileprint m，m1，m2一点通解决此类问题的方法就是从m2开始，对每一个正整数逐一检验，当m满足所有已知条件时，结束循环，输出m.1如图所示的流程图，输出的结果是_解析：m10时，不满足条件，则m107.m17时，mod(m,3)2且mod(m,5)2成立，故输出17.答案：172下面一段伪代码的功能是_m2while mod(m,2)1or mod(m,3)2or mod(m,5)3mm1end whileprint m解析：由代码含义可知，m满足的条件是除以2余1，除以3余2，除以5余3，又m逐个增大，故输出的m是满足条件的最小正整数答案：求关于x、y、z的不定方程组的最小正整数解 例2设计用辗转相除法求8 251与6 105的最大公约数的算法，并画出流程图，写出伪代码思路点拨按照辗转相除法的步骤设计算法、画流程图，根据流程图，写出伪代码精解详析算法如下s1a8 251；s2b6 105；s3如果mod(a，b)0，那么转s4，否则转s7；s4rmod(a，b)；s5ab；s6br，转s3；s7输出b.流程图与伪代码：一点通辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数3下图表示的流程图，输出的结果是_解析：第一次执行循环体：r34，a119，b34，第二次执行循环体r17，a34，b17.第三次执行循环体r0，输出b17.答案：174求三个数168,56,264的最大公约数解： 先求168与56的最大公约数168563，故168与56的最大公约数是56.再求56与264的最大公约数26456440，5640116，401628，1682.故56与264的最大公约数是8.因此168,56,264的最大公约数是8. 例3(12分)设计用二分法求方程x320在区间1,2内的近似解(误差不超过0.005)的流程图，写出伪代码思路点拨根据二分法求方程近似解的步骤画出流程图，然后根据流程图写出算法伪代码精解详析流程图如图：(6分)伪代码如下：a1b2c0.005dox0f(a)a32f(x0)2if f(x0)0 then exit doif f(a)f(x0)0 thenbx0elseax0end ifuntil |ab|68得a18，b68，由6818得b50，a18；由5018得b32，a18；由3218得b14，a18；由1814得a4，b14；由144得b10，a4；由104得b6，a4；由64得b2，a4；由42得a2，b2.满足ab，输出2.答案：2484和32的最小公倍数是_解析：先求84和32的最大公约数8432220322012201281284842.故84和32的最大公约数是4.所以84和32的最小公倍数为84324672.答案：6725下列伪代码的运行结果是_解析：此伪代码的功能是求两个正整数的最大公约数a，b的值依次是：(120,252)(120,132)(120,12)(108,12)(96,12)(84,12)(72,12)(60,12)(48,12)(36，12)(24,12)(12,12)，输出12.答案：12二、解答题6已知如图所示的流程图(其中的m、n为正整数)：(1)这个算法的功能是什么？(2)当m286，n91时，运行的结果是什么？解：(1)这个算法的功能是用辗转相除法求两个正整数的最大公约数(2)28691313,91137，286与91的最大公约数是13.故运行结果为13.7试写出用二分法求方程x3x210在0,1上的近似解的伪代码(精确度为0.01)解：伪代码如下：a0b10.01dox0(ab)/2f(a)a3a21f(x0)xx1iff(x0)0 then exit doiff(a)f(x0)0thenax0elsebx0end ifuntil |ab|end doprint x08有一堆