第11章 11.4 算法案例（课件）-2018-2019版数学创新设计课堂讲义同步系列（湘教版必修5）

第11章—— 算法初步 ‹#› 11.4　算法案例 11.4　算法案例 [学习目标] 1.通过案例，进一步体会算法的思想； 2.理解并能利用案例中的算法解决具体问题. ‹#› 11.4　算法案例 1 预习导学 挑战自我，点点落实 2 课堂讲义 重点难点，个个击破 3 当堂检测 当堂训练，体验成功 栏目索引 CONTENTS PAGE ‹#› 11.4　算法案例 [知识链接] (1)20和30的最大公约数为 . (2)已知函数f(x)＝x2＋2x－1，计算f(1)的值时用了 次乘法和 次加法运算；当函数变为f(x)＝(x＋2)x－1，求f(1)时，用了 次乘法运算和 次加法运算. 10 2 2 1 2 预习导学 挑战自我，点点落实 ‹#› 11.4　算法案例 [预习导引] 1.辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的古老而有效的算法. (2)辗转相除法的算法步骤 S1：给定 . S2：计算 . S3∶ . S4：判断r＝0是否成立，若成立，输出最大公约数a；否则返回S2. 最大公约数 两个正整数a，b a除以b所得的余数r a＝b，b＝r ‹#› 11.4　算法案例 ‹#› 11.4　算法案例 2.利用“二分法”求方程f(x)＝0在区间[a，b]上的近似解的步骤为： S1：确定解区间[a，b]和精度c； S2：取[a，b]的中点x0＝ ； S3：若 ，则进入S4；否则输出x0结束算法： S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法； S5：若 ，则解在[x0，b]，以x0替换a； 若 ，则解在[a，x0]，用x0替换b；返回S2. |a－b|≥c f(a)f(x0)>0 f(a)f(x0)<0 ‹#› 11.4　算法案例 ‹#› 11.4　算法案例 3.秦九韶算法 把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式： f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 求多项式的值时，首先计算 一次多项式的值，即v1＝ ，然后由内向外逐层计算一次多项式的值，即v2＝ ，v3＝ ，…，vn＝vn－1x＋a0. 这样，求n次多项式f(x)的值就转化为求 的值. 最内层括号内 anx＋an－1 v1x＋an－2 v2x＋an－3 n个一次多项式 ‹#› 11.4　算法案例 ‹#› 11.4　算法案例 要点一　求两个正整数的最大公约数 例1　用辗转相除法求261和319的最大公约数. 解　319÷261＝1(余58)， 261÷58＝4(余29)， 58÷29＝2(余0)， 所以319与261的最大公约数为29. 课堂讲义 重点难点，个个击破 ‹#› 11.4　算法案例 规律方法　1.利用辗转相除法求给定的两个数的最大公约数，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数. 2.求两个数的最大公约数也可以利用更相减损术. ‹#› 11.4　算法案例 ‹#› 11.4　算法案例 跟踪演练1　用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果. 解　80＝36×2＋8， 36＝8×4＋4,8＝4×2＋0， 即80与36的最大公约数是4. 验证： 80÷2＝40　36÷2＝18 40÷2＝20　18÷2＝9 ‹#› 11.4　算法案例 ‹#› 11.4　算法案例 20－9＝11　11－9＝2 9－2＝7　7－2＝5 5－2＝3　3－2＝1 2－1＝1　1×2×2＝4 所以80与36的最大公约数为4. ‹#› 11.4　算法案例