高中数学 第一章 算法初步 1.4 算法案例课件 苏教版必修3

1、第1章算法初步1.4算法案例学习目标1.理解解决“韩信点兵孙子问题”的算法思想；2.理解辗转相除法与更相减损术的数学原理；3.能用伪代码实现二分法求方程的近似解.题型探究问题导学内容索引当堂训练问题导学知识点一本节涉及的内置函数就像木工不必自己造锯一样，vb也把一些常用基础工具做成内置函数，以备使用者直接调用，下面是本节涉及的内置函数：函数功能例子mod(a，b)得到a除以b的余数mod(9，2)1val()将字符串转换为数值int(x)表示不超过x的最大整数int(3.9)3思考知识点二“韩信点兵一孙子问题”的数学本质“三三数之剩二”是什么意思？如何用代数式表示？“三三数之剩二”意思是一堆东

2、西，三个三个地分组，余二个.设这堆东西数目为m，则m3x2，其中x指组数.答案梳理梳理“韩信点兵孙子问题”是求关于x，y，z的一次不定方程组_的正整数解.思考知识点三辗转相除法与更相减损术的算法原理我们知道20485234.为什么204与85的最大公约数就是85与34的最大公约数？设204与85的最大公约数为a，则a能整除204，故能整除85234.又因为a也是85的约数，故a能整除852，所以a必能整除34，即a是34的约数，从而是85与34的最大公约数，显然，204与85的公约数问题转化成了85与34的公约数问题，问题难度降低了.答案梳理梳理一般地，有2种算法求两个正整数的最大公约数：(1

3、)辗转相除法的运算步骤：第一步，给定.第二步，计算 .第三步， .第四步，若r0，则m，n的最大公约数等于 ；否则，返回.第二步两个正整数m，n(mn)m除以n所得的余数rmn，nrm(2)更相减损术的运算步骤：第一步，任意给定两个正整数，判断它们是否都是.若是，用约简；若不是，执行.第二步，以的数减去的数，接着把所得的差与的数比较，并以大数减小数，继续这个操作，直到所得的数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.相等偶数2第二步较大较小较小思考知识点四二分法的实现你还能回忆起二分法的作用和原理吗？二分法是用来求方程近似解的，其原理是先确定一个解所在的大致区间，然后

4、借助零点存在定理，不断缩小这个区间.答案梳理梳理求方程f(x)0在区间a，b上的近似解的步骤为：s1取a，b的中点x0(ab)，将区间一分为二.s2若 ，则x0就是方程的根，否则判断根x*在x0的左侧还是右侧：若 ，则x*(x0，b)，以x0代替a；若 ，则x*(a，x0)，以x0代替b.s3若|ab|0f(a)f(x0)b)的最大公约数的一个算法吗？并画出流程图，编写伪代码.类型二辗转相除法的现代实现解答算法如下：s1输入两个正整数a，b；s2若mod(a，b)0，那么转s3，否则转s6；s3rmod(a，b)；s4ab；s5br，转s2；s6输出b.流程图如图：伪代码如下：reada，bw

5、hilemod(a，b)0rmod(a，b)abbrendwhileprintb利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.反思与感悟跟踪训练跟踪训练2用辗转相除法和更相减损术求261和319的最大公约数.解答辗转相除法：3192611(余58)，261584(余29)，58292(余0)，所以319与261的最大公约数为29.更相减损术：31926158，26158203，20358145，1455887，875829，582

6、929，29290，所以319与261的最大公约数是29.类型三求方程 f(x)0近似解的算法例例3画出用区间二分法求方程x3x10在区间1，1.5上的一个近似解(误差不超过0.001)的一个算法流程图并编写伪代码.解答流程图如图：a1b1.5c0.001do f(a)a3a1iff(x0)0thenexitdoiff(a)f(x0)0then bx0else ax0endifuntil|ab|cenddoprintx0伪代码如图：在此算法中用到了条件语句和循环语句，所以用“do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“for”语句.反思与感悟跟踪训练跟踪训练3改造例3

7、中伪代码，用来求f(x)lnx2x1在区间a，b上的一个近似解(误差不超过c).解析伪代码如图：reada，b，cdo f(a)lna2a1 f(x0)lnx02x01iff(x0)0thenexitdoiff(a)f(x0)0then bx0else ax0endifuntil|ab|cenddoprintx0当堂训练23411.m是一正整数，对两个正整数a，b，若ab是m的倍数，则称模m同余，用符号ab(modm)表示.则a5(mod27)中，a的取值最小为_.答案322 . 用 更 相 减 损 术 求 3 6 与 1 3 4 的 最 大 公 约 数 ， 第 一 步 应 为_.36与134

8、都是偶数，第一步应为：先除以2，得到18与67.先除以2，得到18与672341答案解析3.求方程x5y3(其中y为自然数)的所有小于100的x的正整数解，用伪代码表示.算法的伪代码如图：解答y0 x0whilex100 x5y3printxyy1endwhile23414.求两个正数8251和6105的最大公约数.8251610512146；6105214621813；214618131333333148237；1483740；则37为8251与6105的最大公约数.解答2341规律与方法1.求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示.为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“while”语句.2.用二分法求方程近似解，必须先