11.4 算法案例（课件）-2018年数学同步优化指导（湘教版必修5）(共39张PPT)

第11章　算法初步 11.4　算法案例 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 1．了解辗转相除法、中国剩余定理、二分法、秦九韶算法中蕴含的数学原理，并能根据这些原理进行算法分析； 2．基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序． 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 1．辗转相除法 (1)辗转相除法，是一种求两个正整数的______________的古老而有效的算法． (2)辗转相除法的算法步骤 S1：输入______________________； S2：计算____________________，即r＝a MOD b； S3：____________； S4：判断r＝0是否成立，若成立，则输出最大公约数_____； 否则返回________. 最大公约数　 两个正整数a，b(a>b)　 a除以b所得的余数r　 a＝b，b＝r　 a　 S2　 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 下列说法中正确的有(　　) ①辗转相除法也叫欧几里得算法； ②辗转相除法的基本步骤是用较大的数除以较小的数； ③求最大公约数的方法，除辗转相除法之外，没有其他方法； ④编写辗转相除法的伪代码，要用到循环语句． A．1个　　　　　　　　 B．2个 C．3个 D．4个 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 解析　③不正确，因为除了辗转相除法，还有其他方法，如更相减损术．故选C． 答案：C 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 2．中国剩余定理 中国剩余定理是求一个不定方程组，如eq \b\lc\{\rc\ (\a\vs4\al\co1(m＝3x＋a,m＝5y＋b,m＝7z＋c))的正整数解的最小值．(其中a是m除3的余数，b是m除5的余数，c是m除7的余数，如a＝2，b＝3，c＝2.) 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 中国剩余定理的算法思路： 假定所求的数为m，分别计算m被3,5,7除所得的余数a，b，c，即a＝m MOD 3，b＝m MOD 5，c＝m MOD 7， 可以从m＝________开始检验三个条件a＝2，b＝3，c＝2是否同时成立，若三个条件中有任何一个不成立，则m递增________，当三个条件同时成立时，则m即为所求的最小正整数． 3　 1　 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 提示：不一定，a，b，c是具体一个问题给出的分别小于3,5,7的正整数．例如a，b，c也可以是a＝2，b＝3，c＝4等． 不定方程组eq \b\lc\{\rc\ (\a\vs4\al\co1(m＝3x＋a,m＝5y＋b,m＝7z＋c))中的a，b，c是否一定是a＝2，b＝3，c＝2? 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 3．秦九韶算法 把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式： f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 求多项式的值时，首先计算________________一次多项式的值，即v1＝____________，然后由内向外逐层计算一次多项式的值，即 最内层括号内　 anx＋an－1　 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 v2＝____________， v3＝____________， …… vn＝____________ 这样，求n次多项式f(x)的值就转化为求________________的值． v1x＋an－2　 v2x＋an－3　 vn－1x＋a0　 n个一次多项式　 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 · 当堂达标 用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2，当x＝4时的值时，先算的是(　　) A．4×4＝16　　　　　　 B．7×4＝28 C．4×4×4＝64 D．7×4＋6＝34 解析　因为f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 所以用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4时的值时，先算的是7×4＋6＝34. 答案：D 课堂 · 互动探究 数学　必修5（F版） 课前 · 自主学习 反馈 ·