2020高中数学第章算法初步.4算法案例讲义.pdf

《2020高中数学第章算法初步.4算法案例讲义.pdf》由会员分享，可在线阅读，更多相关《2020高中数学第章算法初步.4算法案例讲义.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学必求其心得，业必贵于专精 -1-1.4 算法案例 学 习 目 标 核 心 素 养 1。通过中国古代算法案例，体会中国古代数学对世界数学发展的贡献 2能综合运用所学的算法知识解决实际问题，会用自然语言、流程图和伪代码表述问题的算法过程(重点、难点）3拓展视野，进一步感受算法的意义和价值.通过算法案例，培养学生发现、探索问题的能力，通过抽象、概括把实际问题转化为数学问题，提升学生的数学抽象、数学建模以及逻辑推理的数学核心素养.1“孙子问题是求关于x,y，z的一次不定方程组错误!的正整数解 2辗转相除法和更相减损术(1)欧几里得辗转相除法求两个正整数a，b的最大公约数的步骤是：计算出ab的余数r，

2、若r0，则b即为a,b的最大公约数；学必求其心得，业必贵于专精 -2-若r0，则把前面的除数b作为新的被除数，把余数r作为新的除数,继续运算，直到余数为 0，此时的除数即为a，b的最大公约数(2）“更相减损术”是我国的九章算术中提到的一种求两个正数最大公约数的算法，它与“辗转相除法”相似它的基本思想是：对于给定的两个数,以两个数中较大的数减去较小的数，然后将差和较小的数组成一对新数，再用两个数中较大的数减去较小的数，反复执行此步骤，直到产生一对相等的数为止，这个数就是原来两个数的最大公约数 3Int(x）和 Mod(x）函数（1)Int(x)表示不超过x的最大整数 例如：Int(5）5,Int

3、错误!0，Int(3.6）3.(2）Mod（a，b）的意义是a除以b所得的余数，因此当 Mod（a,b）0 时，表示a能被b整除，当 0Mod（a,b)b时，a不能被b整除,即b不是a的约数 4利用“二分法”求方程f(x）0 在区间a，b上的近似解的步骤 S1 取a，b的中点x0错误!（ab)，将区间一分为二；S2 若f(x0)0，则x0就是方程的根；否则判断根x在x0的左学必求其心得，业必贵于专精 -3-侧还是右侧：若f（a)f(x0)0，则x（x0，b），以x0代替a;若f（a）f(x0）0,则x*（a，x0)，以x0代替b；S3 若|abc，计算终止，此时xx0，否则转 S1.1两个整数

4、 490 和 910 的最大公约数是_ 70 9104901420,490420170,4207060，490 和 910 的最大公约数是 70.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用二分法求方程的近似解，误差不超过，则循环结构的终止条件是_ 学必求其心得，业必贵于专精 -4-|x1x2;x1x2;x1b)的

5、最大公约数为例)为：S1 输入两个正整数a,b；S2 如果 Mod（a，b）0，那么转 S3，否则，转 S6；S3 rMod(a,b）;S4 ab；学必求其心得，业必贵于专精 -8-S5 br，转 S2；S6 输出B 其流程图如图：伪代码为：错误!提醒:求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示 为了避免求循环次数(对两个具体的正整数，循环次数可以求出,但会使程序更为复杂)，最好使用“While”语句 3用辗转相除法求 261 和 319 的最大公约数 学必求其心得，业必贵于专精 -9-解 3192611（余 58），261584(余 29)，58

6、292（余 0），所以 319 与 261 的最大公约数为 29。4 运行下面伪代码，当输入 168,72 时输出的结果是_ 错误!24 伪代码是求 168 与 72 的最大公约数 二分法求方程的近似解【例 3】设计用二分法求方程x320 在区间1，2内的近似解（误差不超过 0.005）的流程图，写出伪代码 思路点拨：依据二分法求方程的近似解的步骤设计出算法再转换成流程图和伪代码，设f（x）x32 如图所示 如果估计出方程f(x）0 在某区间a，b内有一个根x,就能用二分法搜索求得符合误差限制c的近似解 用自然语言表示算法如下：S1 取a，b的中点x0错误!（ab），将区间一分为二；学必求其心

7、得，业必贵于专精 -10-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，计算终止,此时xx0,否则转 S1.解 流程图如图所示：伪代码如下：错误!1用二分法求方程近似解，必须先判断方程在给定区间上是否学必求其心得，业必贵于专精 -11-有解 2 二分法的过程是一个多次重复的过程，故可用循环结构处理 3二分法过程中需要对中点(端点)处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择 5 用区间二分法求出方程 3x

8、5x在区间1，2上的近似解（误差不超过 0.001），并写出这个算法的伪代码，画出流程图 解 设f(x)3xx5.伪代码如下：错误!其流程图如图所示：学必求其心得，业必贵于专精 -12-1本节课重点是会用孙子定理求一次不定方程组的解,会求两个数的最大公约数，用二分法求方程的近似解 2求最大公约数的两种方法步骤(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：学必求其心得，业

9、必贵于专精 -13-首先判断两个正整数是否都是偶数若是，用 2 约简，也可以不除以 2，直接求最大公约数，这样不影响最后结果。1有一堆火柴棒,三根三根地数,最后余下一根；四根四根地数,最后余下两根；五根五根地数，最后余下四根那么这堆火柴棒最少根数为（）A31 B34 C44 D54 B 由题意知，本题实际上是求关于a，b，c的不定方程组的正整数解，即错误!得m的最小值为 34.24 557 与 5 115 的最大公约数是_ 93 因为 5 1154 5571558，4 557558893，558936，所以 4 557 与 5 115 的最大公约数是 93.3Mod(100，17)_。15 Mod（a，b）c表示b除a所得余数为C10017515,故余数为 15.4根据如图所示的流程图（其中x表示不大于x的最大整数),可知输出r_.学必求其心得，业必贵于专精 -14-错误!由流程图的算法原理可知:a错误!,b错误!,n1，n(ba）错误!错误!1；n2,n（ba)2(错误!错误!）1；n3，n(ba）3(错误!错误!)1,分子有理化得错误!错误!1，此时,m3错误!6，r错误!错误!错误!,故输出r错误!.