2019_2020学年高中数学第1章算法初步1.3算法案例学案新人教A版必修3

《2019_2020学年高中数学第1章算法初步1.3算法案例学案新人教A版必修3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3　算法案例学习目标核心素养1.会用辗转相除法与更相减损术求两数的最大公约数．(重点、易混点)2．会用秦九韶算法求多项式的值．(重点)3．会在不同进位制间进行相互转化．(难点)1.通过古代传统算法，培养数学运算素养．2．借助算法案例，提升逻辑推理素养.1．辗转相除法与更相减损术(1)辗转相除法①辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．②所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数．若余数不为零，则将余数和较小

2、的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．(2)更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的方法．其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数．2．秦九韶算法把一个n次多项式f(x)＝anxn＋an－1x

3、n－1＋…＋a1x＋a0改写成如下形式：f(x)＝(…((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)的值的方法叫秦九韶算法．3．进位制(1)进位制是人们为了计数和运算方便而约定的记数系统．“满k进一”就是k进制，k进制的基数是k．(2)将k进制数化为十进制数的方法是：先把k进制数写成各位

4、上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果．(3)将十进制数化为k进制数方法是：除k取余法．即用k连续去除十进制数所得的商，直到商为零为止，然后把各步得到的余数倒排写出．就是相应的k进制数．1．在对16和12求最大公约数时，整个操作如下：16－12＝4，12－4＝8，8－4＝4.由此可以看出12和16的最大公约数是(　　)A．4　　　B．12C．16D．8A　[根据更相减损术的方法判断．]2．下列有可能是4进制数的是(　　)A．5123B．6542C．3103D．4312C　[4进制中逢

5、4进1，每位上的数字一定小于4.]3．已知多项式f(x)＝4x5＋3x4＋2x3－x2－x－，用秦九韶算法求f(－2)等于(　　)A．－B．C．D．－A　[∵f(x)＝((((4x＋3)x＋2)x－1)x－1)x－，∴f(－2)＝－.]4．利用辗转相除法求3869与6497的最大公约数时，第二步是________3869＝2628×1＋1241　[第一步应为6497＝3869×1＋2628；第二步应为3869＝2628×1＋1241.]求最大公约数【例1】　求228与1995的最大公约数．思路点拨：求两个正整数的

6、最大公约数可以用辗转相除法，也可以用更相减损术．[解]　法一：(辗转相除法)1995＝8×228＋171，228＝1×171＋57，171＝3×57，所以228与1995的最大公约数为57.法二：(更相减损术)1995－228＝1767，1767－228＝1539，1539－228＝1311，1311－228＝1083，1083－228＝855，855－228＝627，627－228＝399，399－228＝171，228－171＝57，171－57＝114，114－57＝57.所以228与1995的最大公约数为

7、57.求最大公约数的两种方法(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：第一步判断两个正整数是否都是偶数，若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为

8、止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．1．用辗转相除法和更相减损术求1515与600的最大公约数，需要运算的次数分别为(　　)A．4，15　　　B．5，14C．5，13D．4，12B　[辗转相除法：1515＝600×2＋315；600＝315×1＋285，315＝285×1＋30，285＝30×9＋15，30＝15×2，故最大公约数为15，且需