1.3 算法案例（课件+课时训练）-2019-2020学年高中数学必修3【高考领航】一线课堂高中同步核心辅导（人教A版）

1．3　算法案例 [课标领航]　1.理解辗转相除法与更相减损术的定义．(重点)　2.掌握秦九韶算法及进位制之间的转化．(重点)　3.理解三种算法的程序框图及程序的转化．(难点) 1．辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法． (2)辗转相除法的算法步骤 第一步，给定两个正整数m，n. 第二步，计算m除以n所得的余数r. 第三步，m＝n，n＝r. 第四步，若r＝0，则m、n的最大公约数等于m；否则返回第二步． 2．更相减损术 (1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法． (2)其基本过程是： 第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． ①辗转相除法与更相减损术有什么区别与联系？ 【提示】 名称 辗转相除法 更相减损术 区别[来源:学+科+网] ①以除法为主． ②两个整数差值较大时运算次数较少． ③相除余数为零时得结果. ①以减法为主． ②两个整数的差值较大时，运算次数较多． ③相减，两数相等得结果． ④相减前要做是否都是偶数的判断． 联系 ①都是求最大公约数的方法． ②二者的实质都是递推的过程． ③二者都是用循环结构来实现. 3.秦九韶算法 功能 它是一种用于计算一元n次多项式的值的方法 改写 后的 形式 f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0 ＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0 ＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0 ＝… ＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0 计算 方法 从括号最内层开始，由内向外逐层计算 v1＝anx＋an－1， v2＝v1x＋an－2， v3＝v2x＋an－3， … vn＝vn－1x＋a0， 这样，求n次多项式f(x)的值就转化为求n个一次多项式的值. ②用秦九韶算法求x＝2时，f(x)＝x3＋3x2＋x＋1的值，第一个一次多项式的值为多少？ 【提示】　由秦九韶算法知f(x)＝[(x＋3)x＋1]x＋1，所以由内到外第一个一次多项式的值为2＋3＝5. 4．进位制 (1)进位制是人们为了计算和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几． (2)其他进制与十进制间的转化 ①其他进制化成十进制 其他进位制的数化成十进制时，表示成不同位上数字与基数的幂的乘积之和的形式． ②十进制化成k进制的方法——“除k取余法”． ③如何进行不同进位制间的互化？ 【提示】　两个非十进制间的数进行互化时，要借助十进制数进行．即先把k1进制的数化为十进制数，再把这个十进制数化为k2进制数． 1．有关辗转相除法，下列说法正确的是(　　) A．它和更相减损术一样是求多项式值的一种方法 B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至r＜n为止 C．基本步骤是用较大的数m除以较小的数n得到除式m＝qn＋r(0≤r＜n)，反复进行，直到r＝0为止 D．以上说法皆错 解析：选C.由辗转相除法的含义可得． 2．用更相减损术求459和357的最大公约数，需做减法的次数为(　　) A．4　　　　　　 B．5 C．6 D．7 解析：选B.使用更相减损术有：459－357＝102；357－102＝255；255－102＝153；153－102＝51；102－51＝51，共做了5次减法． 3．已知函数f(x)＝x3－2x2－5x＋6，则f(5)＝________. 解析：用秦九韶算法，将多项式化为： f(x)＝((x－2)x－5)x＋6，由内到外计算． v0＝1，v1＝1×5－2＝3，v2＝3×5－5＝10，v3＝10×5＋6＝56. 答案：56 4．将二进制数101101(2)化为十进制数其结果为________． 解析：101101(2)＝1×20＋0×21＋1×22＋1×23＋0×24＋1×25＝1＋4＋8＋32＝45. 答案：45 类型一　求最大公约数 例1►求80与36的最大公约数． 【导析】　(1)→→ (2)→→ 【解】　法一：(辗转相除法) 80＝36×2＋8， 36＝8×4＋4， 8＝4×2＋0. 故80和36的最大公约数是4. 法二：(更相减损术) 80－36＝44， 44－36＝8， 36－8＝28， 28－8＝20， 20－8＝12， 12－8＝4， 8－4＝4， ∴80和36的最大公约数是4. 【方法总结】　1.由该题可以看出，辗转相除法求