优化方案高中数学 第一章 算法初步 1.3算法案例学案 新人教A版必修3.doc

13算法案例1问题导航(1)什么叫辗转相除法？(2)什么叫更相减损术？(3)辗转相除法与更相减损术的区别是什么？(4)什么是秦九韶算法？(5)学习了十进制，知道十进制是使用09十个数字，那么二进制、五进制、七进制分别使用哪些数字？2例题导读通过对例1的学习，学会用更相减损术求最大公约数；通过对例2的学习，学会用秦九韶算法求多项式的值；通过对例3的学习，学会如何将二进制化为十进制；通过对例4的学习，学会如何将k进制化为十进制；通过对例5的学习，学会如何将十进制化为二进制；通过对例6的学习，学会十进制化为k进制的方法：即“除k取余法”(kn，2k9)1辗转相除法与更相减损术(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法(2)更相减损术：我国古代数学专著九章算术中介绍的一种求两个正整数的最大公约数的算法2秦九韶算法功能它是一种用于计算一元n次多项式的值的方法改写后的形式f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0计算方法从括号最内层开始，由内向外逐层计算v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值.3.进位制(1)进位制进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几(2)其他进位制与十进制间的转化其他进位制化成十进制其他进位制的数化成十进制时，表示成不同位上数字与基数的幂的乘积之和的形式十进制化成k进制的方法“除k取余法”1用更相减损术求294和84的最大公约数时，需做减法运算的次数是()a2b3c4 d5解析：选c.29484210，21084126，1268442，844242，共做4次减法运算2用秦九韶算法计算多项式f(x)3x64x55x46x37x28x1当x0.4时的值时，需要做乘法和加法的次数分别是()a6，6 b5，6c5，5 d6，5答案：a3完成下列进位制之间的转化(1)1 034(7)_(10)；(2)119(10)_(6)解析：(1)1 034(7)17307237470368.(2)119(10)315(6)答案：(1)368(2)3154当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？解：所缺的项写成系数为零的形式，即写成0xn的形式1对于任何一个数，我们可以用不同的进位制来表示2表示各种进位制数一般在数字右下角加注来表示，如111 001(2)表示二进制数，34(5)表示5进制数3电子计算机一般都使用二进制4利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用5通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的m进制数6利用秦九韶算法可以减少计算次数提高计算效率求最大公约数用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果(链接教材p36例1)解用辗转相除法：6124681144，468144336，144364，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117，15311736，1173681，813645，45369，36927，27918，1899，所以612和468的最大公约数为92236.方法归纳(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用2约简，也可以不除以2，直接求最大公约数，这样不影响最后结果1(1)1 624与899的最大公约数是_解析：1 6248991725，8997251174，725174429，174296，故1 624与899的最大公约数是29.答案：29(2)用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果解：辗转相除法：803628，36844，8420.故80和36的最大公约数是4.用更相减损术检验：803644，44368，36828，28820，20812，1284，844，80和36的最大公约数是4.秦九韶算法及其应用(2015福州高一检测)用秦九韶算法写出当x3时f(x)2x54x33x25x1的值解f(x)(2x0)x4)x3)x5)x1，v02，v12306，v263414，v3143345，v44535130，v513031391，所以f(3)391.方法归纳利用秦九韶算法将f(x)改写成如下形式f(x)(anxan1)xan2)xa1)xa0，其计算步骤为：先计算v1anxan1，再计算v2v1xan2，每次都是把上一次的结果乘以x再与下一个系数相加，其计算量为乘法n次，加法n次2利用秦九韶算法求多项式f(x)3x612x58x43.5x37.2x25x13当x6时的值，写出详细步骤解：f(x)(3x12)x8)x3.5)x7.2)x5)x13.v03，v1v061230，v2v168188，v3v263.51 124.5，v4v367.26 754.2，v5v46540 530.2，v6v5613243 168.2.所以f(6)243 168.2.进位制(1)把二进制数101 101(2)化为十进制数；(2)把十进制数458转化为四进制数(链接教材p41例3、例4)解(1)101 101(2)1250241231220211203284145，所以二进制数101 101(2)转化为十进制数为45.(2)45813 022(4)互动探究将本例(1)中的二进制数101 101(2)转化为三进制数解：101 101(2)12502412312202112045，451 200(3)，101 101(2)1 200(3)方法归纳(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余3(1)二进制数算式1 010(2)10(2)的值是()a1 011(2) b1 100(2)c1 101(2) d1 000(2)解析：选b.二进制数的加法是逢二进一，所以选b.(2)下列各组数中最小的数是()a1 111(2) b210(6)c1 000(4) d101(8)解析：选a.统一化为十进制数为1 111(2)15；210(6)78；1 000(4)64；101(8)65.易错警示因忽略零系数项而致误利用秦九韶算法求多项式f(x)x65x56x4x23x2当x2时的值为()a320 b160c320 d300解析将多项式变式为f(x)(x5)x6)x0)x1)x3)x2，v01，v12(5)7，v27(2)620，v320(2)040，v440(2)181，v581(2)3159，v6159(2)2320.答案a错因与防范(1)考虑x2而认为多项式的值为负值(2)易忽略多项式中系数为0的项，致使多项式改写不正确(3)解题时注意多项式变形后有几次乘法和几次加法(4)要注意所给多项式的项数，特别是系数为0的项4(1)用秦九韶算法计算多项式f(x)1235x8x26x45x53x6在x4时的值时，v3的值为()a144 b136c57 d34解析：选b.根据秦九韶算法多项式可化为f(x)(3x5)x6)x0)x8)x35)x12.由内向外计算v03；v13(4)57；v27(4)634；v334(4)0136.(2)已知多项式f(x)3x58x43x35x212x6，则f(2)_解析：根据秦九韶算法，把多项式改写成如下形式：f(x)(3x8)x3)x5)x12)x6.按照从内到外的顺序，依次计算一次多项式当x2时的值v03，v132814，v2142325，v3252555，v455212122，v512226238，所以当x2时，多项式的值为238.答案：2381下列关于利用更相减损术求156和72的最大公约数的说法中正确的是()a都是偶数必须约简b可以约简，也可以不约简c第一步作差为1567284；第二步作差为728412d以上都不对解析：选b.约简是为了使运算更加简捷，故不一定要约简，a错c中第二步应为847212，故选b.2用辗转相除法计算294与84的最大公约数时，需要做的除法次数是()a1 b2c3 d4解析：选b.29484342，84422，至此公约数已求出3二进制数1 101 111(2)化成十进制数是_解析：1 101 111(2)120121122123024125126111.答案：1114若k进制数123(k)与十进制数38相等，则k_解析：由k进制数123可知k4.下面可用验证法：若k4，则38(10)212(4)，不合题意；若k5，则38(10)123(5)成立，所以k5.答案：5a.基础达标1.45和150的最大公约数和最小公倍数分别是()a5，150b15，450c450，15 d15，150解析：选b.利用辗转相除法求45和150的最大公约数：15045315，45153，45和150的最大公约数为15.45和150的最小公倍数为15(4515)(15015)450，故选b.2把67化为二进制数为()a1 100 001(2) b1 000 011(2)c110 000(2) d1 000 111(2)解析：选b.把67化为二进制数为1 000 011(2)3(2015三明高一检测)计算机中常用十六进制，采用数字09和字母af共16个计算符号与十进制的对应关系如下表：十六进制0123456789abcdef十进制0123456789101112131415例如用十六进制表示de1b，则(2f1)4()a6e b7cc5f db0解析：选b.(2f1)4用十进制可以表示为(2151)4124，而12416712，所以用十六进制表示为7c，故选b.4.若用秦九韶算法求多项式f(x)4x5x22当x3时的值，则需要做乘法运算和加减法运算的次数分别为()a4，2 b5，3c5，2 d6，2解析：选c.f(x)4x5x22(4x)x)x1)x)x2，所以需要做5次乘法运算和2次加减运算5.(2015青海调研)已知一个k进制的数132与十进制的数30相等，那么k等于()a7或4 b7c4 d都不对解析：选c.132(k)1k23k2k23k2，k23k230，即k23k280，解得k4或k7(舍去)6.三个数72，120，168的最大公约数是_解析：由更相减损术，得16812048，1204872，724824，482424，故120和168的最大公约数是24.而722448，482424，故72和24的最大公约数也是24，所以72，120，168的最大公约数是24.答案：247.(2015莱芜质检)已知函数f(x)x32x25x6，用秦九韶算法，则f(10)_解析：f(x)x32x25x6(x22x5)x6(x2)x5)x6.当x10时，f(10)(102)105)106(8105)10675106756.答案：7568.(2015福州高一检测)三进制数2022(3)化为六进制数为abc(6)，则abc_解析：2 022(3)23303223123062.三进制数2022(3)化为六进制数为142(6)，abc7.答案：79.已知函数f(x)x33x24x5，试用秦九韶算法求f(2)的值解：根据秦九韶算法，把多项式改写成如下形式：f(x)x33x24x5(x23x4)x5(x3)x4)x5.把x2代入函数式得f(2)(23)24)257.10.古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向境内报告来犯敌人数，如图所示，烽火台上点火表示数字1，未点火表示数字0，约定二进制数对应的十进制数的单位是1 000，请你计算一下，这组烽火台表示有多少敌人入侵？解：由题图可知这组烽火台表示的二进制数为11 011(2)，它表示的十进制数为11 011(2)12412302212112027，由于约定二进制数对应的十进制数的单位是1 000，所以入侵的敌人的数目为271 00027 000(人)b.能力提升1将十进制数389 化成四进制数的末位是 ()a1 b2c3 d0解析：选a.3894971，即第一次用389除以4余1，而这就是最后一位数字2(2015盐城质检)m是一个正整数，对于两个正整数a，b，如果ab是m的倍数，则称a，b对模m同余，用符号ab(mod m)表示，则下列各式中不正确的为()a127(mod 5) b2110(mod 3)c3420(mod 2) d477(mod 40)解析：选b.逐一验证，对于a，1275是5的倍数；对于b，211011不是3的倍数；对于c，342014是2的倍数；对于d，47740是40的倍数，故选b.3324，243，135三个数的最大公约数是_解析：324243181，243813，所以243与324的最大公约数是81.又13581154，8154127，542720，所以135