1、目标导航预习导引目标导航预习导引121.孙子剩余定理“韩信点兵孙子问题”的算法最早出现在我国算经十书之一的孙子算经中.原文是:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二.问物几何?答曰:二十三.”自从孙子算经中提出这个“物不知数”问题之后,它便引起了人们很大的兴趣.南宋数学家秦九韶对此加以推广,又发现了一种新的解法,叫“大衍求一术”.这种解法后来传入欧洲,欧洲学者发现此解法和高斯的解法本质上是一致的,但比高斯早了500余年.所以,人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”.预习交流1孙子剩余定理的实质是什么问题?提示:孙子剩余定理一般解决的是求总数问题,其实
2、质就是利用求余的方法求不定方程(组)的整数解问题.目标导航预习导引122.辗转相除法与更相减损术 目标导航预习导引12预习交流2实际应用更相减损术时要做的第一步工作是什么?提示:先判断a,b是否为偶数,若是都除以2再进行.目标导航预习导引12预习交流3(1)25与35的最大公约数为.(2)用辗转相除法求两个正整数a,b(ab)的最大公约数时,得到表达式a=nb+r(nN),这里r的取值范围是.提示:(1)35=125+10,25=210+5,10=25,所以25与35的最大公约数为5.(2)0rb问题导学即时检测一二三一、孙子剩余定理的理解及应用活动与探究1有3个连续的自然数,其中最小的能被1
3、5整除,中间的能被17整除,最大的能被19整除,求满足要求的一组3个连续的自然数,画出流程图,并用伪代码表示算法.思路分析:本题其实就是求关于x,y,z的不定方程组 的正整数解.问题导学即时检测一二三解:流程图如图所示: 问题导学即时检测一二三伪代码如下: m1While Mod(m,15)0 orMod(m+1,17)0 orMod(m+2,19)0mm+1End WhilePrint m,m+1,m+2问题导学即时检测一二三迁移与应用1.下列各式中正确的是()Mod(3,2)=2;Mod(3,2)=1;Mod(2,3)=1;Mod(105,7)=0;Mod(8,3)=2.A.B.C.D.解
4、析:Mod(a,b)的意义是ab所得的余数.3=21+1,Mod(3,2)=1.2=03+2,Mod(2,3)=2.105=157,Mod(105,7)=0.8=32+2,Mod(8,3)=2.正确.答案:D问题导学即时检测一二三2.已知一个班的学生人数在30至56之间,现按3人一排,多出1人;按5人一排,多出3人;按7人一排,多出1人,则该班级人数为.解析:设此班有m人,问题转化为解关于x,y,z的不定方程组 又m(30,56),可得m的值为43.答案:43问题导学即时检测一二三1.Int(x)表示不超过x的最大整数.2.解不定方程的思想在算法中有着广泛的应用,特别是求不定方程的整数解,常规
5、解法就是试值的方法.一般情况下,由于试值的次数比较多,工作量较大,此时我们可以编写程序,由计算机代替人工单一重复的计算.问题导学即时检测一二三二、求两数的最大公约数活动与探究2导学号51810022求两个正整数8 251和6 105的最大公约数.思路分析:解答本题首先明确8 251与6 105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,再根据已有的知识即可求出最大公约数.问题导学即时检测一二三解:8 251=6 1051+2 146,显然8 251与6 105的最大公约数也必是2 146的约数.同样,6 105与2 146的公约数也必是8 251的约数,所以8 251与6 105
6、的最大公约数也是6 105与2 146的最大公约数.6 105=2 1462+1 8132 146=1 8131+3331 813=3335+148333=1482+37148=374+0则37为8 251与6 105的最大公约数.问题导学即时检测一二三迁移与应用1.用更相减损术求294与84的最大公约数时,需做减法的次数是.解析:294与84都是偶数,首先除以2得到147,42,再求147与42的最大公约数,147-42=105,105-42=63,63-42=21,42-21=21,共做了4次减法.答案:42.请用辗转相除法求1 734和816的最大公约数.解:辗转相除法的求解过程如下:第
7、一步,1 734=2816+102;第二步,816=8102+0;因此,102是1 734和816的最大公约数.问题导学即时检测一二三(1)辗转相除法适合求两个数的最大公约数.利用辗转相除法,直到余数为0时即可求出最大公约数.三个数的最大公约数分别是每个数的约数,因此也是任意两个数的最大公约数的约数.也就是说,三个数的最大公约数是其中任意两个数的最大公约数与第三个数的最大公约数.(2)对于求多个数的最大公约数,也可以用更相减损术.用更相减损术求两个数的最大公约数的步骤是用较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得数相等为止,则这个数(等数)就是所
8、求的最大公约数.问题导学即时检测一二三三、二分法求方程的近似解活动与探究3已知函数f(x)=x2-5,画出求方程f(x)=0在2,3上的一个近似解(差不超0.001)的流程,并写出代.思路分析:解答本题可先回忆一下二分法求近似 解的步骤,由步骤画出流程图,然后再写出算法的 伪代码.解:流程图如图所示:问题导学即时检测一二三伪代码为: x12x23DoIf f(x0)=0 Then Exit DoIf f(x1)f(x0)0 Thenx2x0Elsex1x0问题导学即时检测一二三x1x0End IfUntil |x1-x2|0.001End DoPrint x0问题导学即时检测一二三迁移与应用导
9、学号51810023写出用二分法求方程x5-3x+1=0在(0,1)上的一个近似解的伪代码,精确到0.001.解:伪代码为:x10 x21DoIf f(x0)=0 Then Exit DoIf f(x1)f(x0)0 Then问题导学即时检测一二三x2x0Elsex1x0End IfUntil |x1-x2|0.001End DoPrint x0问题导学即时检测一二三给定误差c,用二分法求函数f(x)的零点x0的近似值的步骤如下:(1)确定区间a,b,验证f(a)f(b)0,给定误差值;(2)求区间(a,b)的中点x1;(3)计算f(x1),若f(x1)=0,则x1就是函数的零点;若f(a)f
10、(x1)0,则令b=x1(此时零点x0(a,x1);若f(x1)f(b)0,则令a=x1(此时零点x0(x1,b);(4)判断,若|a-b|c,计算终止,此时,x0 x1,否则重复步骤(2)(4).问题导学即时检测123451.对于“韩信点兵孙子问题”的方程组解的问题,以下理解正确的是.A.只有一组正整数解B.只有一组小于100的正整数解C.可能没有正整数解D.可能没有小于100的正整数解答案:B问题导学即时检测123452.Mod(m,a)=3的含义是.答案:m被a除后余3问题导学即时检测123453.用二分法求方程log2x=3-x在区间a,b内的一个近似解(误差不超过0.001)时,利用循环语句“DoEnd Do”编写伪代码,其循环的终止条件是.答案:|a-b|0.001问题导学即时检测123454.用辗转相除法求480和288的最大公约数时,需要做除法的次数是.解析:用辗转相除法求最大公约数的各步骤结果是(480,288),(288,192),(192,96),此时相除余数为0,共进行了三次除法.答案:3问题导学即时检测123455.导学号51810024用 相除法逐步列出求98和63的最大公数的步.解:S198=631+35;S263=351+28;S335=281+7;S428=74.最大公约数为7.
