1.4 算法案例导学案

1、1.4 算法案例自主学习1符号Int(x)和Mod(a，b)的含义是什么？2“孙子问题”相当于怎样的数学问题？3.欧几里得辗转相除法是解决什么问题的数学方法，它的一般步骤是什么？初探新知1“孙子问题”相当于求关于x，y，z的不定方程组eq blcrc (avs4alco1(m3x2，,m5y3，,m7z2)的正整数解2欧几里得辗转相除法(1)含义：求两个正数a，b(ab)的最大公约数的方法，称为欧几里得辗转相除法(2)步骤：计算出ab的余数r，若r0，则b即为a，b的最大公约数；若r0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为a，b的最大公约

2、数3两个常用函数(1)Mod(a，b)表示a除以b所得的余数(2)Int(x)表示不超过x的最大整数点睛辗转相除法的理论根据是：由anbrranb，得a，b与b，r有相同的公约数小试牛刀1Int(5)_；Inteq blc(rc)(avs4alco1(f(2,3)_；Int(3.14)_.答案：5042用辗转相除法求32和14的最大公约数时，需要做_次除法运算答案：33用符号表示m被7除后余2为_答案：Mod(m,7)2典型题例 典例1有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码解设这三个数分别为m

3、，m1，m2，则m满足的条件是Mod(m,15)0且Mod(m1,17)0且Mod(m2,19)0.流程图：伪代码：m2While Mod(m,15)0or Mod(m1,17)0orMod(m2,19)0mm1End WhilePrint m，m1，m2举一反三下面一段伪代码的功能是_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的不定方程组eq blcrc (avs4alco1(

4、m2x1，,m3y2，,m5z3)的最小正整数解典例2用辗转相除法求396和270的最大公约数，并设计算法，画出流程图，写出伪代码解396270126,270212618,126187，因此396和270的最大公约数为18.算法如下：S1a396S2b270S3如果Mod(a，b)0，那么转S4，否则转S7S4rMod(a，b)S5abbrS6转 S3S7输出b伪代码：流程图： 举一反三求396和270的最小公倍数解：根据最大公约数和最小公倍数的关系可知这两个数的最小公倍数为396270185 940.典例3在平面直角坐标系中作出函数y2x和y4x的图象，根据图象判断方程2x4x的解的范围，再

5、用二分法求这个方程的近似解(误差不超过0.001)，写出这个算法的伪代码，并画出流程图解在同一坐标系内作出函数y2x和y4x图象如图：由图象可知方程2x4x有一根在1,2内伪代码为：eq x(aal(a1,b2,c0.001,While|ab|c,x0ab/2,fa2aa4,fx02x0 x04,If fx00 ThenExit While,EndIf,Iffafx00Then,bx0,Else,ax0,EndIf,EndWhile,Printx0)流程图如下：举一反三在平面直角坐标系内作出yx2和y2x的图象，并判断方程x22x在(1,0)内有无实根若有，求出这个实根的近似值(误差不超过0.

6、01)写出这个算法的伪代码解：作出yx2和y2x的图象如图由图可知方程x22x在(1,0)内有且只有一个实根x0.设f(x)x22x，f(1)0 ，f(0)0，以上结论正确求这个实根误差不超过0.01的近似值的伪代码如下：达标训练基础训练1Inteq blc(rc)(avs4alco1(f(37,5)_；Int(11.2)_.答案：7122用辗转相除法求85和51的最大公约数时，需要做除法的次数为_答案：3384和32的最小公倍数是_解析：先求84和32的最大公约数8432220，322012，20128，1284，842.故84和32的最大公约数是4.所以84和32的最小公倍数为843246

7、72.答案：6724下列伪代码运行的一个结果是_m2While Mod(m,4)2 orMod(m,5)3 orMod(m,7)3mm1End WhilePrint m解析：此伪代码的功能是求eq blcrc (avs4alco1(m4x2，,m5x3，,m7x3) 的最小正整数，m38.答案： 385已知如图所示的流程图(其中的m，n为正整数)：(1)这个算法的功能是什么？(2)当m286，n91时，运行的结果是什么？解：(1)这个算法的功能是用辗转相除法求两个正整数的最大公约数(2)28691313,91137，286与91的最大公约数是13.故运行结果为13.能力提升1下列格式中正确的是

8、_Mod(2,3)3；Mod(3,2)2；Mod(2,3)1; Mod(3,2)1.答案：2用二分法求方程的近似解，精确度为e，则循环结构的终止条件是_(填序号)|x1x2|e；x1x2e；x1ex2; |x1x2|e.答案：3324,243,270的最大公约数为_解析：324243181,2438130，故324和243的最大公约数为81.又27081327,812730，324,243,270的最大公约数为27.答案：274下列程序输出的n的值是_eq x(aal(j1,n0,Whilej11,jj1,IfModj，40Then,nn1,EndIf,jj1,EndWhile,Printn)

9、答案：35m是一个正整数，对两个正整数a，b，如果ab是m的倍数，则称a，b对模m同余，用符号ab(Modm)表示，则下列各式中：127(Mod5)；2110(Mod3)；3420(Mod2)；477(Mod40)正确的有_(填序号)解析：逐一验证，由题意，1275是5的倍数；211011不是3的倍数；342014是2的倍数；47740是40的倍数故正确答案：6下列伪代码的运行结果是_eq x(aal(a120,b252,Whileab,Ifab,aab,Else,bba,End If,EndWhile,Printa)解析：此伪代码的功能是求两个正整数的最大公约数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.答案：127试写出求三个正整数a，b，c的最大公约数的算法语句解：先写出的伪代码是求正整数a，b的最大公约数，设最大公约数用b表示，然后再写出求正整数b，c的最大公约数的伪代码，并输出其最大公约数，用b表示，可用“当型”语句写出伪代码所求的算法语句(即伪代码)如下：eq x(aal(Reada，b，c,WhileModa，b0,rM