1、1.4算法案例学习目标1.理解解决“韩信点兵孙子问题”的算法思想.2.理解辗转相除法与更相减损术的数学原理知识点一“韩信点兵一孙子问题”的数学本质思考“三三数之剩二”是什么意思？如何用代数式表示？答案“三三数之剩二”意思是一堆东西，三个三个地分组，余二个设这堆东西数目为m，则m3x2，其中x指组数梳理“韩信点兵孙子问题”是求关于x，y，z的一次不定方程组的正整数解知识点二辗转相除法与更相减损术的算法原理思考我们知道20485234.为什么204与85的最大公约数就是85与34的最大公约数？答案设204与85的最大公约数为a，则a能整除204，故能整除85234.又因为a也是85的约数，故a能整
2、除852，所以a必能整除34，即a是34的约数，从而是85与34的最大公约数，显然，204与85的公约数问题转化成了85与34的公约数问题，问题难度降低了梳理一般地，有2种算法求两个正整数的最大公约数：(1)辗转相除法的运算步骤：第一步，给定两个正整数m，n(mn)第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r0，则m，n的最大公约数等于m；否则，返回第二步(2)更相减损术的运算步骤：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为
3、止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数1辗转相除法也叫欧几里得算法()2辗转相除法的基本步骤是用较大的数除以较小的数()3求最大公约数的方法除辗转相除法之外，没有其他方法()4编写辗转相除法的程序时，要用到循环语句()类型一孙子剩余定理的应用例1(1)方程组的整数解有_组答案无数解析方程组中的两方程相减并化简整理得x1y.当y取3的整数倍时，x就可以取到相应的整数，因此，原方程组的整数解有无数组(2)有三个连续的自然数，其中最小的能被15整除，中间的能被17整除；最大的能被19整除，求满足要求的一组3个连续的自然数，画出流程图，并用伪代码表示算法解流程图如图所示：伪代
4、码如下：m1While Mod(m,15)0 or Mod(m1,17)0 or Mod(m2,19)0mm1End WhilePrint m，m1，m2反思与感悟(1)孙子剩余定理常用来解决求不定方程(组)的正整数解问题，需要熟练掌握算术中的整除知识和算法中的循环结构(2)设计算法时要选择循环结构(直到型或当型)跟踪训练1有一堆围棋子，五个五个地数，最后余下2个；七个七个地数，最后余下3个；九个九个地数，最后余下4个请用伪代码表示“求出这堆棋子至少有多少个”的一种算法解算法的伪代码如下：m2While Mod(m,5)2 or Mod(m,7)3 or Mod(m,9)4mm1End Whi
5、lePrint m类型二求两个正整数的最大公约数例2设计用辗转相除法求8 251与6 105的最大公约数的算法，并画出流程图，写出伪代码解算法如下：S1a8 251；S2b6 105；S3如果Mod(a，b)0，那么转S4，否则转S7；S4rMod(a，b)；S5ab；S6br，转S3；S7输出b.流程图与伪代码：a8 251b6 105While Mod(a，b)0 rMod(a，b) ab brEnd WhilePrint b反思与感悟利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大
6、数被小数除尽，则这时的较小数就是原来两个数的最大公约数跟踪训练2用辗转相除法和更相减损术求261和319的最大公约数解辗转相除法：3192611(余58)，261584(余29)，58292(余0)，所以319与261的最大公约数为29.更相减损术：31926158，26158203，20358145，1455887，875829，582929，29290，所以319与261的最大公约数是29.类型三求方程f(x)0近似解的算法例3画出用区间二分法求方程x3x10在区间1，1.5上的一个近似解(误差不超过0.001)的一个算法流程图并编写伪代码解流程图如图： 伪代码如图：a1b1.5c0.00
7、1Dox0f(a)a3a1f(x0)x01If f(x0)0 Then Exit DoIf f(a)f(x0)0 Thenbx0Elseax0End IfUntil |ab|cEnd DoPrint x0 反思与感悟在此算法中用到了条件语句和循环语句，所以用“Do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“For”语句跟踪训练3改造例3中的伪代码，用来求方程ln x2x10在区间a，b上的一个近似解(误差不超过c)解伪代码如图：Reada，b，cDox0f(a)ln a2a1f(x0)ln x02x01If f(x0)0 Then Exit DoIf f(a)f(x0)0
8、 Thenbx0Elseax0End IfUntil|ab|cEnd DoPrintx01两个整数490和910的最大公约数是_答案70解析4907225,91013725，最大公约数为72570.2m是一正整数，对两个正整数a，b，若ab是m的倍数，则称a，b模m同余，用符号ab(Modm)表示则a5(Mod27)中，a的取值最小为_答案323用更相减损术求36与134的最大公约数，第一步应为_答案先除以2，得到18与67解析36与134都是偶数，第一步应为：先除以2，得到18与67.4求方程x5y3(其中y为自然数)的所有小于100的x的正整数解，用伪代码表示解算法的伪代码如图：y0x0W
9、hile x100x5y3Print xyy1End While5求a204与b85的最大公约数解20485，余数r1为34，所以20485234；8534，余数r2为17，所以8534217；3417，余数为0，所以34172.因此，204与85的最大公约数是r217.1求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“While”语句2用二分法求方程近似解，必须先判断方程在给定区间上是否有解3二分法的过程是一个多次重复的过程，故可用循环结构处理4二分法过程中需要对中点(端点)处函数值的符号进行判断，故实现算法需用选择结构，即用条件语句进行分支选择
