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

1.3算法案例学 习 目 标核 心 素 养1会用辗转相除法与更相减损术求两数的最大公约数(重点、易混点)2会用秦九韶算法求多项式的值(重点)3会在不同进位制间进行相互转化(难点)1通过古代传统算法，培养数学运算素养2借助算法案例，提升逻辑推理素养.1辗转相除法与更相减损术(1)辗转相除法辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数(2)更相减损术更相减损术是我国古代数学专著九章算术中介绍的一种求两数最大公约数的方法其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数2秦九韶算法把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：f(x)(anxan1)xan2)xa1)xa0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1anxan1，然后由内向外逐层计算一次多项式的值，即v2v1xan2，v3v2xan3，vnvn1xa0，这种求n次多项式f(x)的值的方法叫秦九韶算法3进位制(1)进位制是人们为了计数和运算方便而约定的记数系统“满k进一”就是k进制，k进制的基数是 k.(2)将k进制数化为十进制数的方法是：先把k进制数写成各位上的数字与k的幂的乘积之和的形式，再按照十进制数的运算规则计算出结果(3)将十进制数化为k进制数方法是：除k取余法即用k连续去除十进制数所得的商，直到商为零为止，然后把各步得到的余数倒排写出就是相应的k进制数1在对16和12求最大公约数时，整个操作如下：16124,1248,844.由此可以看出12和16的最大公约数是()a4b12c16d8a根据更相减损术的方法判断2下列有可能是4进制数的是()a5123b6542c3103d4312c4进制中逢4进1，每位上的数字一定小于4.3已知多项式f(x)4x53x42x3x2x，用秦九韶算法求f(2)等于()a bcdaf(x)(4x3)x2)x1)x1)x，f(2).4利用辗转相除法求3 869与6 497的最大公约数时，第二步是_3 8692 62811 241第一步应为6 4973 86912 628；第二步应为3 8692 62811 241.求最大公约数【例1】求228与1995的最大公约数思路点拨：求两个正整数的最大公约数可以用辗转相除法，也可以用更相减损术解法一：(辗转相除法)1 9958228171,228117157,171357，所以228与1 995的最大公约数为57.法二：(更相减损术)1 9952281 767,1 7672281 539，1 5392281 311,1 3112281 083，1 083228855,855228627，627228399,399228171，22817157,17157114，1145757.所以228与1 995的最大公约数为57.求最大公约数的两种方法(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：第一步判断两个正整数是否都是偶数，若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.1用辗转相除法和更相减损术求1 515与600的最大公约数，需要运算的次数分别为()a4,15b5,14c5,13d4,12b辗转相除法：1 5156002315；6003151285,315285130,28530915,30152，故最大公约数为15，且需计算5次用更相减损术：1 515600915,915600315,600315285,31528530,28530255,25530225,22530195,19530165,16530135,13530105,1053075,753045,453015,301515.故最大公约数为15，且需计算14次秦九韶算法【例2】已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值思路点拨：可根据秦九韶算法的原理，将所给的多项式改写，然后由内到外逐次计算解将f(x)改写为f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由内向外依次计算一次多项式，当x5时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72 826.2；v52 826.250.814 130.2.所以当x5时，多项式的值等于14 130.2.利用秦九韶算法求多项式的值的步骤2用秦九韶算法计算多项式f(x)1235x8x26x45x53x6在x4时，v3的值为()a144b136c57d34b根据秦九韶算法多项式可化为f(x)(3x5)x6)x0)x8)x35)x12.由内向外计算v03；v13(4)57；v27(4)634；v334(4)0136.进位制及其转化探究问题1数学上通常使用什么进位制？它的原理是什么？提示十进制十进制的原理是满十进一一个十进制正整数n可以写成an10nan110n1a1101a0100的形式，其中an，an1，a1，a0都是0至9中的数字，且an0.例如36531026105.2你还知道哪些进位制？它们与目前我们使用的进位制数之间能否转化？提示(1)二进制使用0和1这两个数字，基数为2.(2)八进制使用0,1,2,3,4,5,6,7这八个数字，基数为8.(3)十六进制使用0,1,2,3,4,5,6,7,8,9，a，b，c，d，e，f这十六个符号，基数为16.其中a，b，c，d，e，f分别相当于十进制中的10,11,12,13,14,15.它们与十进位制数之间可以转化，两个非十进制数之间也可以以十进制作“桥梁”，进行相互转化3不同的进位制数如何区分？提示一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k)，以示区别例如270(8)表示270是一个8进制数但十进制一般省略不写【例3】下列四个数中，最大的是()a11011(2)b103(4)c44(5)d25思路点拨：先将各数都转化为十进制数，再比较大小a11011(2)12412302212112027，103(444(5)45145024.27252419，最大数是11011(2)1(变条件)210(6)化成十进制数为_78210(6)2621678.2(变结论)把1234(5)化成七进制数为_365(7)1234(5)153252351450194.而1 234(5)194365(7)进位制的转换方法(1)要把k进制数化为十进制数，首先把k进制数表示成不同位上数字与k的幂的乘积之和，其次按照十进制的运算规则计算和(2)十进制数化为k进制数(除k取余法)的步骤1求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止2秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行3把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数1判断下列结论的正误(正确的打“”，错误的打“”)(1)用辗转相除法与更相减损术都可以求两个正整数的最大公约数()(2)秦九韶算法的优点是减少了乘法运算的次数，提高了运算效率()(3)不同进位制中，十进制的数比二进制的数大()答案(1)(2)(3)2用辗转相除法求72与120的最大公约数时，需要做除法次数为()a4b3c5d6b12072148,7248124,48242.3将八进制数123(8)化为十进制数，结果为_831822813806416383.4用秦九韶算法求多项式f(x)