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

第1章算法初步1.4算法案例 学习目标1.理解解决“韩信点兵孙子问题”的算法思想；2.理解辗转相除法与更相减损术的数学原理；3.能用伪代码实现二分法求方程的近似解. 题型探究问题导学内容索引 当堂训练 问题导学 知识点一本节涉及的内置函数就像木工不必自己造锯一样，VB也把一些常用基础工具做成内置函数，以备使用者直接调用，下面是本节涉及的内置函数：函数功能例子Mod(a，b)得到a除以b的余数Mod(9，2)1Val()将字符串转换为数值Int(x)表示不超过x的最大整数Int(3.9)3 思考知识点二“ 韩信点兵一孙子问题” 的数学本质“三三数之剩二”是什么意思？如何用代数式表示？“三三数之剩二”意思是一堆东西，三个三个地分组，余二个.设这堆东西数目为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)辗转相除法的运算步骤：第一步，给定.第二步，计算 .第三步， .第四步，若r0，则m，n的最大公约数等于 ；否则，返回.第二步两个正整数m，n(mn)m除以n所得的余数rm n，n r m (2)更相减损术的运算步骤：第一步，任意给定两个正整数，判断它们是否都是.若是，用约简；若不是，执行.第二步，以的数减去的数，接着把所得的差与的数比较，并以大数减小数，继续这个操作，直到所得的数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.相等偶数2第二步较大较小较小 思考知识点四二分法的实现你还能回忆起二分法的作用和原理吗？二分法是用来求方程近似解的，其原理是先确定一个解所在的大致区间，然后借助零点存在定理，不断缩小这个区间.答案 梳理求方程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；S3r Mod(a，b)；S4a b；S5b r，转S2；S6输出b.流程图如图： 伪代码如下：Reada，bWhileMod(a，b) 0r Mod(a，b)a bb rEndWhilePrintb 利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数. 反 思 与 感悟 跟踪训练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)的一个算法流程图并编写伪代码. 解答 流程图如图：a 1b 1.5c 0.001Do f(a) a3 a 1Iff(x0) 0ThenExitDoIff(a)f(x0)0Then b x 0Else a x0EndIfUntil|a b|cEndDoPrintx0 伪代码如图： 在此算法中用到了条件语句和循环语句，所以用“ Do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“ For”语句.反 思 与 感悟 跟踪训练3改造例3中伪代码，用来求f(x)lnx2x1在区间a，b上的一个近似解(误差不超过c). 解析 伪代码如图：Read a， b， cDo f(a) lna 2a 1 f(x0) lnx0 2x0 1If f(x0) 0 Then Exit DoIf f(a)f(x0)0 Then b x0Else a x 0End IfUntil |a b|cEnd DoPrint x0 当堂训练 2 3 41 1.m是一正整数，对两个正整数a，b，若ab是m的倍数，则称模m同余，用符号a b(Modm)表示.则a 5(Mod27)中，a的取值最小为_. 答案32 2.用更相减损术求36与134的最大公约数，第一步应为_. 36与134都是偶数，第一步应为：先除以2，得到18与67.先除以2，得到18与67 2 3 41答案 解析 3.求方程x5y3(其中y为自然数)的所有小于100的x的正整数解，用伪代码表示.算法的伪代码如图：解答y 0 x 0Whilex100 x 5y3Printxy y1EndWhile 2 3 41 4.求两个正数8251和6105的最大公约数.8251610512146；6105214621813；214618131333；18133335148；333148237；1483740；则37为8251与6105的最大公约数. 解答 2 3 41 规 律 与 方法1.求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示.为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂)，最好使用“ While”语句.2.用二分法求方程近似解，必须先判断方程在给定区间上是否有解.3.二分法的过程是一个多次重复的过程，故可用循环结构处理.4.二分法过程中需要对中点(端点)处函数值的符号进行判定，故实现算法需用选择结构，即用条件语句进行分支选择. 本课结束