《2018-2019学年高中数学同步苏教版必修3学案：第1章 1.4 算法案例 Word版含解析.pdf》由会员分享，可在线阅读，更多相关《2018-2019学年高中数学同步苏教版必修3学案：第1章 1.4 算法案例 Word版含解析.pdf（10页珍藏版）》请在三一文库上搜索。
1、高清试卷 下载可打印 高清试卷 下载可打印 1符号符号 Int(x)和和 Mod(a，b)的含义是什么？的含义是什么？ 2 “孙子问题”相当于怎样的数学问题？ “孙子问题”相当于怎样的数学问题？ 1 欧几里得辗转相除法是解决什么问题的数学方法，它的一般步骤是什么？ 欧几里得辗转相除法是解决什么问题的数学方法，它的一般步骤是什么？ 新新知知初初探探 1 “孙子问题”相当于求关于 “孙子问题”相当于求关于 x，y，z 的不定方程组的不定方程组Error!的正整数解的正整数解 2欧几里得辗转相除法欧几里得辗转相除法 (1)含义：求两个正数含义：求两个正数 a，b(ab)的最大公约数的方法，称为欧几里
2、得辗转相除法的最大公约数的方法，称为欧几里得辗转相除法 (2)步骤：计算出步骤：计算出 ab 的余数的余数 r，若，若 r0，则，则 b 即为即为 a，b 的最大公约数；若的最大公约数；若 r0，则把 前面的除数 ，则把 前面的除数 b 作为新的被除数，把余数作为新的被除数，把余数 r 作为新的除数，继续运算，直到余数为作为新的除数，继续运算，直到余数为 0，此时的，此时的 除数即为除数即为 a，b 的最大公约数的最大公约数 3两个常用函数两个常用函数 (1)Mod(a，b)表示表示 a 除以除以 b 所得的余数所得的余数 (2)Int(x)表示不超过表示不超过 x 的最大整数的最大整数 点睛
3、点睛 辗转相除法的理论根据是：由辗转相除法的理论根据是：由 anbrranb，得，得 a，b 与与 b，r 有相同的公约数有相同的公约数 小小试试身身手手 1Int(5)_； Int_； ( 2 3) Int(3.14)_. 算法案例算法案例 预习课本预习课本 P2631，思考并完成以下问题，思考并完成以下问题 高清试卷 下载可打印 高清试卷 下载可打印 答案：答案：5 0 4 2用辗转相除法求用辗转相除法求 32 和和 14 的最大公约数时，需要做的最大公约数时，需要做_次除法运算次除法运算 答案：答案：3 3用符号表示用符号表示 m 被被 7 除后余除后余 2 为为_ 答案：答案：Mod(
4、m,7)2 典例典例 有 有 3 个连续的正整数，其中最小的能被个连续的正整数，其中最小的能被 15 整除，中间的能被整除，中间的能被 17 整除，最大的 能被 整除，最大的 能被 19 整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码 解解 设这三个数分别为 设这三个数分别为m， m1， m2， 则， 则m满足的条件是满足的条件是Mod(m,15)0且且Mod(m 1,17)0 且且 Mod(m2,19)0. 流程图：流程图： 伪代码：伪代码： m2 While Mod(m,15) 0 or Mod(m1,17)0
5、or Mod(m2,19)0 mm1 End While Print m，m1，m2 孙子剩余定理的应用孙子剩余定理的应用 高清试卷 下载可打印 高清试卷 下载可打印 解决此类问题的方法就是从解决此类问题的方法就是从 m2 开始，对每一个正整数逐一检验，当开始，对每一个正整数逐一检验，当 m 满足所有已知条 件时，结束循环，输出 满足所有已知条 件时，结束循环，输出 m. 活学活用活学活用 下面一段伪代码的功能是下面一段伪代码的功能是_ m2 While Mod(m,2)1 or Mod(m,3)2 or Mod(m,5)3 mm1 End While Print m 解析：由代码含义可知，解
6、析：由代码含义可知，m 满足的条件是除以满足的条件是除以 2 余余 1，除以，除以 3 余余 2，除以，除以 5 余余 3，又，又 m 逐个增大，故输出的逐个增大，故输出的 m 是满足条件的最小正整数是满足条件的最小正整数 答案：求关于答案：求关于 x，y，z 的不定方程组的不定方程组Error!的最小正整数解的最小正整数解 典例典例 用辗转相除法求 用辗转相除法求 396 和和 270 的最大公约数，并设计算法，画出流程图，写出伪 代码 的最大公约数，并设计算法，画出流程图，写出伪 代码 解解 396270126,270212618,126187， 因此因此 396 和和 270 的最大公约
7、数为的最大公约数为 18. 算法如下：算法如下：S1 a396 S2 b270 S3 如果 如果 Mod(a，b)0，那么转，那么转 S4，否则转，否则转 S7 S4 rMod(a，b) S5 ab br S6 转 转 S3 S7 输出 输出 b 伪代码： 伪代码： 流程图：流程图： 欧几里得辗转相除法的应用欧几里得辗转相除法的应用 高清试卷 下载可打印 高清试卷 下载可打印 (1)求三个正整数求三个正整数 a，b，c 的最大公约数的步骤是：的最大公约数的步骤是： 先求其中两个数的最大公约数，如求先求其中两个数的最大公约数，如求 a，b 的最大公约数，用的最大公约数，用 m 表示；再求表示；再
8、求 m 与 第三个数 与 第三个数 c 的最大公约数，用的最大公约数，用 n 表示；表示；n 就是三个数就是三个数 a，b，c 的最大公约数的最大公约数 (2)整数整数 a 和和 b 的最小公倍数为，即的最小公倍数为，即(a，b 的最大公约数的最大公约数)(a，b 的最的最 ab a，b的的最最大大公公约约数数 小公倍数小公倍数)ab. 活学活用活学活用 求求 396 和和 270 的最小公倍数的最小公倍数 解：根据最大公约数和最小公倍数的关系可知这两个数的最小公倍数为解：根据最大公约数和最小公倍数的关系可知这两个数的最小公倍数为 39627018 5 940. 典例典例 在平面直角坐标系中作
9、出函数 在平面直角坐标系中作出函数y2x和和y4x的图象， 根据图象判断方程的图象， 根据图象判断方程2x 4x 的解的范围，再用二分法求这个方程的近似解的解的范围，再用二分法求这个方程的近似解(误差不超过误差不超过 0.001)，写出这个算法的伪 代码，并画出流程图 ，写出这个算法的伪 代码，并画出流程图 解解 在同一坐标系内作出函数 在同一坐标系内作出函数 y2x和和 y4x 图象如图：由图 象可知方程 图象如图：由图 象可知方程 2x4x 有一根在有一根在1,2内内 伪代码为：伪代码为： 利用二分法求方程的近似解利用二分法求方程的近似解 高清试卷 下载可打印 高清试卷 下载可打印 a1
10、b2 c0.001 While |ab| c x0( (ab) )/2 f( (a) )2aa4 f( (x0) )2x0x04 If f( (x0) )0 Then Exit While End If If f( (a) )f( (x0) )0 Then bx0 Else ax0 End If End While Print x0 流程图如下：流程图如下： (1)利用二分法求方程的近似解时，要根据二分法的步骤写出算法的每一步，再利用循 环结构写出近似解即可 利用二分法求方程的近似解时，要根据二分法的步骤写出算法的每一步，再利用循 环结构写出近似解即可 (2)要注意正好是方程根的处理 要注意正
11、好是方程根的处理 a b 2 活学活用活学活用 在平面直角坐标系内作出在平面直角坐标系内作出 yx2和和 y2x的图象，并判断方程的图象，并判断方程 x22x在在(1,0)内有无实 根若有，求出这个实根的近似值 内有无实 根若有，求出这个实根的近似值(误差不超过误差不超过 0.01)写出这个算法的伪代码写出这个算法的伪代码 解：作出解：作出 yx2和和 y2x的图象如图由图可知方程的图象如图由图可知方程 x22x在在( 1,0)内有且只有一个实根内有且只有一个实根 x0. 高清试卷 下载可打印 高清试卷 下载可打印 设设 f(x)x22x，f(1)0 ，f(0)0，以上结论正确，以上结论正确
12、求这个实根误差不超过求这个实根误差不超过 0.01 的近似值的伪代码如下：的近似值的伪代码如下： 层级一 学业水平达标层级一 学业水平达标 1Int_；Int(11.2)_. ( 37 5) 答案：答案：7 12 2用辗转相除法求用辗转相除法求 85 和和 51 的最大公约数时，需要做除法的次数为的最大公约数时，需要做除法的次数为_ 答案：答案：3 384 和和 32 的最小公倍数是的最小公倍数是_ 解析：先求解析：先求 84 和和 32 的最大公约数的最大公约数 8432220， 322012， 高清试卷 下载可打印 高清试卷 下载可打印 20128， 1284， 842. 故故 84 和和
13、 32 的最大公约数是的最大公约数是 4. 所以所以 84 和和 32 的最小公倍数为的最小公倍数为 84324672. 答案：答案：672 4下列伪代码运行的一个结果是下列伪代码运行的一个结果是_ m2 While Mod(m,4)2 or Mod(m,5)3 or Mod(m,7)3 mm1 End While Print m 解析：此伪代码的功能是求解析：此伪代码的功能是求Error! 的最小正整数，的最小正整数， m38. 答案：答案： 38 5已知如图所示的流程图已知如图所示的流程图(其中的其中的 m，n 为正整数为正整数)： (1)这个算法的功能是什么？这个算法的功能是什么？ (2
14、)当当 m286，n91 时，运行的结果是什么？时，运行的结果是什么？ 解：解：(1)这个算法的功能是用辗转相除法求两个正整数的最大公约数这个算法的功能是用辗转相除法求两个正整数的最大公约数 (2)28691313,91137， 286 与与 91 的最大公约数是的最大公约数是 13.故运行结果为故运行结果为 13. 层级二 应试能力达标层级二 应试能力达标 1下列格式中正确的是下列格式中正确的是_ Mod(2,3)3； ； Mod(3,2)2； 高清试卷 下载可打印 高清试卷 下载可打印 Mod(2,3)1; Mod(3,2)1. 答案：答案： 2用二分法求方程的近似解，精确度为用二分法求方
15、程的近似解，精确度为 e，则循环结构的终止条件是，则循环结构的终止条件是_(填序号填序号) |x1x2|e； ； x1x2e； x1ex2; |x1x2|e. 答案：答案： 3324,243,270 的最大公约数为的最大公约数为_ 解析：解析：324243181,2438130， 故故 324 和和 243 的最大公约数为的最大公约数为 81. 又又 27081327,812730， 324,243,270 的最大公约数为的最大公约数为 27. 答案：答案：27 4下列程序输出的下列程序输出的 n 的值是的值是_ j1 n0 While j 11 jj1 If Mod( (j，4) )0 Th
16、en nn1 End If jj1 End While Print n 答案：答案：3 5m 是一个正整数，对两个正整数是一个正整数，对两个正整数 a，b，如果，如果 ab 是是 m 的倍数，则称的倍数，则称 a，b 对模对模 m 同余，用符号同余，用符号 ab(Modm)表示，则下列各式中：表示，则下列各式中： 127(Mod5)；2110(Mod3)；3420(Mod2)；477(Mod40) 正确的有正确的有_(填序号填序号) 解析 ： 逐一验证， 由题意， 解析 ： 逐一验证， 由题意， 1275是是5的倍数 ； 的倍数 ； 211011不是不是3的倍数 ； 的倍数 ； 3420 14
17、 是是 2 的倍数；的倍数；47740 是是 40 的倍数故正确的倍数故正确 答案：答案： 6下列伪代码的运行结果是下列伪代码的运行结果是_ a120 b252 While a b If ab aab Else bba End If End While Print a 解析：此伪代码的功能是求两个正整数的最大公约数解析：此伪代码的功能是求两个正整数的最大公约数a，b 的值依次是：的值依次是： 高清试卷 下载可打印 高清试卷 下载可打印 (120,252)(120,132)(120,12)(108,12)(96,12)(84,12)(72,12)(60,12)(48,12) (36，12)(24
18、,12)(12,12)，输出，输出 12. 答案：答案：12 7试写出求三个正整数试写出求三个正整数 a，b，c 的最大公约数的算法语句的最大公约数的算法语句 解：先写出的伪代码是求正整数解：先写出的伪代码是求正整数 a，b 的最大公约数，设最大公约数用的最大公约数，设最大公约数用 b 表示，然后再 写出求正整数 表示，然后再 写出求正整数 b，c 的最大公约数的伪代码，并输出其最大公约数，用的最大公约数的伪代码，并输出其最大公约数，用 b 表示，可用“当型” 语句写出伪代码 表示，可用“当型” 语句写出伪代码 所求的算法语句所求的算法语句(即伪代码即伪代码)如下：如下： Read a，b，c
19、 While Mod( (a，b) ) 0 rMod( (a，b) ) ab br End While While Mod( (c，b) ) 0 rMod( (c，b) ) cb br End While Print b 8写出用二分法求方程写出用二分法求方程 x32x30 在区间在区间1,2内的一个近似解内的一个近似解(误差不超过误差不超过 0.001) 的一个算法，并画出流程图的一个算法，并画出流程图 解：本题考查了利用二分法算法求解方程近似解的方法解：本题考查了利用二分法算法求解方程近似解的方法 伪代码如下：伪代码如下： 高清试卷 下载可打印 高清试卷 下载可打印 流程图如图所示：流程图如图所示：