苏教版必修三 §1.4　算法案例 学案.docx

学习目标1.理解剩余定理的内涵.2.能利用剩余定理解决“韩信点兵孙子问题”.3.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析.4.能根据算法与流程图的知识设计完整的流程图并写出算法语句知识点一“孙子问题”“孙子问题”是求关于x，y， 的一次不定方程组的正整数解知识点二辗转相除法欧几里得辗转相除法求两个正整数a，b的最大公约数的步骤是：计算出ab的余数r，若r0，则b即为a，b的最大公约数；若r0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为a，b的最大公约数知识点三利用“二分法”求方程f(x)0在区间a，b上的近似解的步骤为：s1取a，b的中点x0(ab)，将区间一分为二；s2若f(x0)0，则x0就是方程的根；否则判断根x 在x0的左侧还是右侧：若f(a)f(x0)0，则x (x0，b)，以x0代替a；若f(a)f(x0)0，则x (a，x0)，以x0代替b；s3若 ab c，计算终止，此时x x0，否则转s1.题型一孙子剩余定理的应用例1有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码解流程图：伪代码：m2while mod(m，15)0ormod(m1，17)0ormod(m2，19)0mm1end whileprint m，m1，m2反思与感悟解决此类问题的方法就是从m2开始，对每一个正整数逐一检验，当m满足所有已知条件时，结束循环，输出m.跟踪训练1如图所示的流程图，输出的结果是_答案17解析m10时，不满足条件，则m107.m17时，mod(m,3)2且mod(m,5)2成立，故输出17.题型二求两个正整数的最大公约数例2设计用辗转相除法求8251与6105的最大公约数的算法，并画出流程图，写出伪代码解算法如下：s1a8251；s2b6105；s3如果mod(a，b)0，那么转s4，否则转s7；s4rmod(a，b)；s5ab；s6br，转s3；s7输出b.流程图与伪代码：a8 251b6 105while mod(a，b)0rmod(a，b)abbrend whileprint b反思与感悟辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数跟踪训练2用辗转相除法求261和319的最大公约数解3192611(余58)，261584(余29)，58292(余0)，所以319与261的最大公约数为29.题型三二分法求方程的近似解例3设计用二分法求方程x320在区间1,2内的近似解(误差不超过0.005)的流程图，写出伪代码解流程图如图：伪代码如下：a1b2c0.005dox0(ab)/2f(a)a32f(x0)2if f(x0)0then exit doif f(a) f(x0)0 thenbx0elseax0end ifuntil ab cend doprint x0反思与感悟针对这个类型的题目书写伪代码时一定要注意伪代码的具体格式，另外循环语句中一定包含有选择结构的语句求高次方程近似解时，一定要给出精确度跟踪训练3下面的流程图表示的算法的功能是_.答案用二分法求方程x23x10在区间0,1内的一个近似解(误差不超过0.001)1两个整数490和910的最大公约数是_答案70解析4907225,91013725，最大公约数为72570.2mod(8,3)_.答案2解析mod(8,3)表示8除以3所得的余数8232，mod(8,3)2.3若int(x)表示不超过x的最大整数，对于下列等式：int(10.01)10；int(1)1；int(5.2)5.其中正确的有_个答案2解析正确，错误因为int(x)表示的是不超过x的最大整数int(5.2)6.4用更相减损术求36与134的最大公约数，第一步应为_答案先除以2，得到18与67解析36与134都是偶数，第一步应为：先除以2，得到18与67.51337与382的最大公约数是_答案191解析利用辗转相除法3821912，故两数的最大公约数为191.1.求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“while”语句2用二分法求方程近似解