1.3算法案例(2)
- 格式:ppt
- 大小:1.61 MB
- 文档页数:15
1.3算法案例(1)教学目标(a)知识与技能1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。
2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
(b)过程与方法在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法,比较它们在算法上的区别,并从程序的学习中体会数学的严谨,领会数学算法计算机处理的结合方式,初步掌握把数学算法转化成计算机语言的一般步骤。
(c)情态与价值1.通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献。
2.在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力,在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。
(2)教学重难点重点:理解辗转相除法与更相减损术求最大公约数的方法。
难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
(3)学法与教学用具学法:在理解最大公约数的基础上去发现辗转相除法与更相减损术中的数学规律,并能模仿已经学过的程序框图与算法语句设计出辗转相除法与更相减损术的程序框图与算法程序。
教学用具:电脑,计算器,图形计算器(4)教学设想(一)创设情景,揭示课题1.教师首先提出问题:在初中,我们已经学过求最大公约数的知识,你能求出18与30的公约数吗?2.接着教师进一步提出问题,我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数?这就是我们这一堂课所要探讨的内容。
(二)研探新知1.辗转相除法例1 求两个正数8251和6105的最大公约数。
(分析:8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据已有的知识即可求出最大公约数)解:8251=6105×1+2146显然8251的最大公约数也必是2146的约数,同样6105与2146的公约数也必是8251的约数,所以8251与6105的最大公约数也是6105与2146的最大公约数。
1.3 算法案例整体设计教学分析在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序三种不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.三维目标1.理解算法案例的算法步骤和程序框图.2.引导学生得出自己设计的算法程序.3. 体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.重点难点教学重点:引导学生得出自己设计的算法步骤、程序框图和算法程序.教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 课时安排3课时教学过程第1课时案例1 辗转相除法与更相减损术导入新课思路1(情境导入)大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球,东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的.在小学,我们学过求两个正整数的最大公约数的方法:先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来. 当两个数公有的质因数较大时(如8 251与6 105),使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.思路2(直接导入)前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减损术来进一步体会算法的思想.推进新课新知探究提出问题(1)怎样用短除法求最大公约数?(2)怎样用穷举法(也叫枚举法)求最大公约数?(3)怎样用辗转相除法求最大公约数?(4)怎样用更相减损术求最大公约数?讨论结果:(1)短除法求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得的商是两个互质数为止,然后把所有的除数连乘起来.(2)穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.(3)辗转相除法辗转相除法求两个数的最大公约数,其算法步骤可以描述如下:第一步,给定两个正整数m,n.第二步,求余数r:计算m除以n,将所得余数存放到变量r中.第三步,更新被除数和余数:m=n,n=r.第四步,判断余数r是否为0.若余数为0,则输出结果;否则转向第二步继续循环执行.如此循环,直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.(4)更相减损术我国早期也有解决求最大公约数问题的算法,就是更相减损术. 《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现代语言如下:第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简;若不是,执行第二步.第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.应用示例例1 用辗转相除法求8 251与6 105的最大公约数,写出算法分析,画出程序框图,写出算法程序.解:用两数中较大的数除以较小的数,求得商和余数:8 251=6 105×1+2 146.由此可得,6 105与2 146的公约数也是8 251与6 105的公约数,反过来,8 251与6 105的公约数也是6 105与2 146的公约数,所以它们的最大公约数相等.对6 105与2 146重复上述步骤:6 105=2 146×2+1 813.同理,2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤:2 146=1 813×1+333,1 813=333×5+148,333=148×2+37,148=37×4.最后的除数37是148和37的最大公约数,也就是8 251与6 105的最大公约数.这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数.算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结构来构造算法.算法步骤如下:第一步,给定两个正整数m,n.第二步,计算m除以n所得的余数为r.第三步,m=n,n=r.第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.程序框图如下图:程序:INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND点评:从教学实践看,有些学生不能理解算法中的转化过程,例如:求8 251与6 105的最大公约数,为什么可以转化为求6 105与2 146的公约数.因为8 251=6 105×1+2 146,可以化为8 251-6 105×1=2 164,所以公约数能够整除等式两边的数,即6 105与2 146的公约数也是8 251与6 105的公约数.变式训练你能用当型循环结构构造算法,求两个正整数的最大公约数吗?试画出程序框图和程序.解:当型循环结构的程序框图如下图:程序:INPUT m,nr=1WHILE r>0r=m MOD nm=nn=rWENDPRINT mEND例2 用更相减损术求98与63的最大公约数.不是偶数,把98和63以大数减小数,并辗转相减,如下图所示.所以,98和63的最大公约数等于7.点评:更相减损术与辗转相除法的比较:尽管两种算法分别来源于东、西方古代数学名著,但是二者的算理却是相似的,有异曲同工之妙.主要区别在于辗转相除法进行的是除法运算,即辗转相除;而更相减损术进行的是减法运算,即辗转相减,但是实质都是一个不断的递归过程.变式训练用辗转相除法或者更相减损术求三个数324,243,135的最大公约数.解:324=243×1+81,243=81×3+0,则324与243的最大公约数为81.又135=81×1+54,81=54×1+27,54=27×2+0,则81 与135的最大公约数为27.所以,三个数324、243、135的最大公约数为27.另法:324-243=81,243-81=162,162-81=81,则324与243的最大公约数为81.135-81=54,81-54=27,54-27=27,则81与135的最大公约数为27.所以,三个数324、243.135的最大公约数为27.例3 (1)用辗转相除法求123和48的最大公约数.(2)用更相减损术求80和36的最大公约数.解:(1)辗转相除法求最大公约数的过程如下:123=2×48+27,48=1×27+21,27=1×21+6,21=3×6+3,6=2×3+0,最后6能被3整除,得123和48的最大公约数为3.(2)我们将80作为大数,36作为小数,因为80和36都是偶数,要除公因数2.80÷2=40,36÷2=18.40和18都是偶数,要除公因数2.40÷2=20,18÷2=9.下面来求20与9的最大公约数,20-9=11,11-9=2,9-2=7,7-2=5,5-2=3,3-2=1,2-1=1,可得80和36的最大公约数为22×1=4.点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为0,更相减损术是到达减数和差相等.变式训练分别用辗转相除法和更相减损术求1 734,816的最大公约数.解:辗转相除法:1 734=816×2+102,816=102×8(余0),∴1 734与816的最大公约数是102.更相减损术:因为两数皆为偶数,首先除以2得到867,408,再求867与408的最大公约数.867-408=459,459-408=51,408-51=357,357-51=306,306-51=255,255-51=204,204-51=153,153-51=102,102-51=51.∴1 734与816的最大公约数是51×2=102.利用更相减损术可另解:1 734-816=918,918-816=102,816-102=714,714-102=612,612-102=510,510-102=408,408-102=306,306-102=204,204-102=102.∴1 734与816的最大公约数是102.知能训练求319,377,116的最大公约数.解:377=319×1+58,319=58×5+29,58=29×2.∴377与319的最大公约数为29,再求29与116的最大公约数.116=29×4.∴29与116的最大公约数为29.∴377,319,116的最大公约数为29.拓展提升试写出利用更相减损术求两个正整数的最大公约数的程序.解:更相减损术程序:INPUT “m,n=”;m,nWHILE m<>nIF m>n THENm=m-nELSEm=n-mEND IFWENDPRINT mEND课堂小结(1)用辗转相除法求最大公约数.(2)用更相减损术求最大公约数.思想方法:递归思想.作业分别用辗转相除法和更相减损术求261,319的最大公约数.分析:本题主要考查辗转相除法和更相减损术及其应用.使用辗转相除法可依据m=nq+r,反复执行,直到r=0为止;用更相减损术就是根据m-n=r,反复执行,直到n=r为止.解:辗转相除法:319=261×1+58,261=58×4+29,58=29×2.∴319与261的最大公约数是29.更相减损术:319-261=58,261-58=203,203-58=145,145-58=87,87-58=29,58-29=29,∴319与261的最大公约数是29.第2课时案例2 秦九韶算法导入新课思路1(情境导入)大家都喜欢吃苹果吧,我们吃苹果都是从外到里一口一口的吃,而虫子却是先钻到苹果里面从里到外一口一口的吃,由此看来处理同一个问题的方法多种多样.怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?方法也是多种多样的,今天我们开始学习秦九韶算法.思路2(直接导入)前面我们学习了辗转相除法与更相减损术,今天我们开始学习秦九韶算法.推进新课新知探究提出问题(1)求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值有哪些方法?比较它们的特点.(2)什么是秦九韶算法?(3)怎样评价一个算法的好坏?讨论结果:(1)怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?一个自然的做法就是把5代入多项式f(x),计算各项的值,然后把它们加起来,这时,我们一共做了1+2+3+4=10次乘法运算,5次加法运算.另一种做法是先计算x2的值,然后依次计算x2·x,(x2·x)·x,((x2·x)·x)·x的值,这样每次都可以利用上一次计算的结果,这时,我们一共做了4次乘法运算,5次加法运算.第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法,计算机能更快地得到结果.(2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约1202~1261)在他的著作《数书九章》中提出了下面的算法:把一个n次多项式f(x)=a n x n+a n-1x n-1+…+a1x+a0改写成如下形式:f(x)=a n x n+a n-1x n-1+…+a1x+a0=(a n x n-1+a n-1x n-2+…+a1)x+ a0=((a n x n-2+a n-1x n-3+…+a2)x+a1)x+a0=…=(…((a n x+a n-1)x+a n-2)x+…+a1)x+a0.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=a n x+a n-1,然后由内向外逐层计算一次多项式的值,即v2=v1x+a n-2,v3=v2x+a n-3,…v n=v n-1x+a0,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.上述方法称为秦九韶算法.直到今天,这种算法仍是多项式求值比较先进的算法.(3)计算机的一个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论的算法.应用示例例1 已知一个5次多项式为f (x )=5x 5+2x 4+3.5x 3-2.6x 2+1.7x-0.8,用秦九韶算法求这个多项式当x=5时的值.解:根据秦九韶算法,把多项式改写成如下形式:f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8,按照从内到外的顺序,依次计算一次多项式当x=5时的值:v 0=5;v 1=5×5+2=27;v 2=27×5+3.5=138.5;v 3=138.5×5-2.6=689.9;v 4=689.9×5+1.7=3 451.2;v 5=3 415.2×5-0.8=17 255.2;所以,当x=5时,多项式的值等于17 255.2.算法分析:观察上述秦九韶算法中的n 个一次式,可见v k 的计算要用到v k-1的值,若令v 0=a n ,我们可以得到下面的公式:⎩⎨⎧=+==--).,,2,1(,10n k a x v v a v k n k k n 这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.算法步骤如下:第一步,输入多项式次数n 、最高次的系数a n 和x 的值.第二步,将v 的值初始化为a n ,将i 的值初始化为n-1.第三步,输入i 次项的系数a i .第四步,v=vx+a i ,i=i-1.第五步,判断i 是否大于或等于0.若是,则返回第三步;否则,输出多项式的值v. 程序框图如下图:程序:INPUT “n=”;nINPUT “an=”;aINPUT “x=”;xv=ai=n-1WHILE i>=0PRINT “i=”;iINPUT “ai=”;av=v*x+ai=i-1WENDPRINT vEND点评:本题是古老算法与现代计算机语言的完美结合,详尽介绍了思想方法、算法步骤、程序框图和算法语句,是一个典型的算法案例.变式训练请以5次多项式函数为例说明秦九韶算法,并画出程序框图.解:设f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0首先,让我们以5次多项式一步步地进行改写:f(x)=(a5x4+a4x3+a3x2+a2x+a1)x+a0=((a5x3+a4x2+ a3x+a2)x+a1)x+a0=(((a5x2+a4x+ a3)x+a2)x+a1)x+a0=((((a5x+a4)x+ a3)x+a2)x+a1)x+a0.上面的分层计算,只用了小括号,计算时,首先计算最内层的括号,然后由里向外逐层计算,直到最外层的括号,然后加上常数项即可.程序框图如下图:例2 已知n次多项式P n(x)=a0x n+a1x n-1+…+a n-1x+a n,如果在一种算法中,计算k x0(k=2,3,4,…,n)的值需要k-1次乘法,计算P3(x0)的值共需要9次运算(6次乘法,3次加法),那么计算P10(x0)的值共需要__________次运算.下面给出一种减少运算次数的算法:P0(x)=a0,P k+1(x)=xP k(x)+a k+1(k=0,1,2,…,n-1).利用该算法,计算P3(x0)的值共需要6次运算,计算P10(x0)的值共需要___________次运算.答案:65 20点评:秦九韶算法适用一般的多项式f(x)=a n x n+a n-1x n-1+…+a1x+a0的求值问题.直接法乘法运算的次数最多可到达2)1(nn,加法最多n次.秦九韶算法通过转化把乘法运算的次数减少到最多n次,加法最多n次.例3 已知多项式函数f(x)=2x5-5x4-4x3+3x2-6x+7,求当x=5时的函数的值.解析:把多项式变形为:f(x)=2x5-5x4-4x3+3x2-6x+7=((((2x-5)x-4)x+3)x-6)x+7.计算的过程可以列表表示为:最后的系数2 677即为所求的值.算法过程:v0=2;v1=2×5-5=5;v2=5×5-4=21;v3=21×5+3=108;v4=108×5-6=534;v5=534×5+7=2 677.点评:如果多项式函数中有缺项的话,要以系数为0的项补齐后再计算.知能训练当x=2时,用秦九韶算法求多项式f(x)=3x5+8x4-3x3+5x2+12x-6的值.解法一:根据秦九韶算法,把多项式改写成如下形式:f(x)=((((3x+8)x-3)x+5)x+12)x-6.按照从内到外的顺序,依次计算一次多项式当x=2时的值.v0=3;v1=v0×2+8=3×2+8=14;v2=v1×2-3=14×2-3=25;v3=v2×2+5=25×2+5=55;v4=v3×2+12=55×2+12=122;v5=v4×2-6=122×2-6=238.∴当x=2时,多项式的值为238.解法二:f(x)=((((3x+8)x-3)x+5)x+12)x-6,则f(2)=((((3×2+8)×2-3)×2+5)×2+12)×2-6=238.拓展提升用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x当x=3时的值.解:f(x)=((((((7x+6)+5)x+4)x+3)x+2)x+1)xv0=7;v1=7×3+6=27;v2=27×3+5=86;v3=86×3+4=262;v4=262×3+3=789;v5=789×3+2=2 369;v6=2 369×3+1=7 108;v7=7 108×3+0=21 324.∴f(3)=21 324.课堂小结1.秦九韶算法的方法和步骤.2.秦九韶算法的计算机程序框图.作业已知函数f(x)=x3-2x2-5x+8,求f(9)的值.解:f(x)=x3-2x2-5x+8=(x2-2x-5)x+8=((x-2)x-5)x+8∴f(9)=((9-2)×9-5)×9+8=530.第3课时案例3 进位制导入新课情境导入在日常生活中,我们最熟悉、最常用的是十进制,据说这与古人曾以手指计数有关,爱好天文学的古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.今天我们来学习一下进位制.推进新课新知探究提出问题(1)你都了解哪些进位制?(2)举出常见的进位制.(3)思考非十进制数转换为十进制数的转化方法.(4)思考十进制数转换成非十进制数及非十进制之间的转换方法.活动:先让学生思考或讨论后再回答,经教师提示、点拨,对回答正确的学生及时表扬,对回答不准确的学生提示引导考虑问题的思路.讨论结果:(1)进位制是人们为了计数和运算方便而约定的计数系统,约定满二进一,就是二进制;满十进一,就是十进制;满十二进一,就是十二进制;满六十进一,就是六十进制等等.也就是说:“满几进一”就是几进制,几进制的基数(都是大于1的整数)就是几.(2)在日常生活中,我们最熟悉、最常用的是十进制,据说这与古人曾以手指计数有关,爱好天文学的古人也曾经采用七进制、十二进制、六十进制,至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.(3)十进制使用0~9十个数字.计数时,几个数字排成一行,从右起,第一位是个位,个位上的数字是几,就表示几个一;第二位是十位,十位上的数字是几,就表示几个十;接着依次是百位、千位、万位……例如:十进制数3 721中的3表示3个千,7表示7个百,2表示2个十,1表示1个一.于是,我们得到下面的式子:3 721=3×103+7×102+2×101+1×100.与十进制类似,其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同,所用的数字个数也不同.如二进制用0和1两个数字,七进制用0~6七个数字.一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式a n a n-1…a1a0(k)(0<a n<k,0≤a n-1,…,a1,a0<k).其他进位制的数也可以表示成不同位上数字与基数的幂的乘积之和的形式,如110 011(2)=1×25+1×24+0×23+0×22+1×21+1×20,7 342(8)=7×83+3×82+4×81+2×80.非十进制数转换为十进制数比较简单,只要计算下面的式子值即可:a n a n-1…a1a0(k)=a n×k n+a n-1×k n-1+…+a1×k+a0.第一步:从左到右依次取出k进制数a n a n-1…a1a0(k)各位上的数字,乘以相应的k的幂,k的幂从n开始取值,每次递减1,递减到0,即a n×k n,a n-1×k n-1,…,a1×k,a0×k0;第二步:把所得到的乘积加起来,所得的结果就是相应的十进制数.(4)关于进位制的转换,教科书上以十进制和二进制之间的转换为例讲解,并推广到十进制和其他进制之间的转换.这样做的原因是,计算机是以二进制的形式进行存储和计算数据的,而一般我们传输给计算机的数据是十进制数据,因此计算机必须先将十进制数转换为二进制数,再处理,显然运算后首次得到的结果为二进制数,同时计算机又把运算结果由二进制数转换成十进制数输出.1°十进制数转换成非十进制数把十进制数转换为二进制数,教科书上提供了“除2取余法”,我们可以类比得到十进制数转换成k进制数的算法“除k取余法”.2°非十进制之间的转换一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与16进制数据之间的互化的方法,也就是先由二进制数转化为十进制数,再由十进制数转化成为16进制数. 应用示例思路1例1 把二进制数110 011(2)化为十进制数.解:110 011(2)=1×25+1×24+0×23+0×22+1×21+1×20=1×32+1×16+1×2+1=51.点评:先把二进制数写成不同位上数字与2的幂的乘积之和的形式,再按照十进制的运算规则计算出结果.变式训练设计一个算法,把k进制数a(共有n位)化为十进制数b.算法分析:从例1的计算过程可以看出,计算k进制数a的右数第i位数字a i与k i-1的乘积a i·k i-1,再将其累加,这是一个重复操作的步骤.所以,可以用循环结构来构造算法.算法步骤如下:第一步,输入a,k和n的值.第二步,将b的值初始化为0,i的值初始化为1.第三步,b=b+a i·k i-1,i=i+1.第四步,判断i>n是否成立.若是,则执行第五步;否则,返回第三步.第五步,输出b的值.程序框图如下图:INPUT “a,k,n=”;a,k,nb=0i=1t=a MOD 10DOb=b+t*k^(i-1)a=a\\10t=a MOD 10i=i+1LOOP UNTIL i>nPRINT bEND例2 把89化为二进制数.解:根据二进制数“满二进一”的原则,可以用2连续去除89或所得商,然后取余数.具体计算方法如下:因为89=2×44+1,44=2×22+0,22=2×11+0,11=2×5+1,5=2×2+1,2=2×1+0,1=2×0+1,所以89=2×(2×(2×(2×(2×2+1)+1)+0)+0)+1=2×(2×(2×(2×(22+1)+1)+0)+0)+1=…=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1 011 001(2).这种算法叫做除2取余法,还可以用下面的除法算式表示:把上式中各步所得的余数从下到上排列,得到89=1 011 001(2).上述方法也可以推广为把十进制数化为k进制数的算法,称为除k取余法.变式训练设计一个程序,实现“除k取余法”.算法分析:从例2的计算过程可以看出如下的规律:若十制数a除以k所得商是q0,余数是r0,即a=k·q0+r0,则r0是a的k进制数的右数第1位数.若q0除以k所得的商是q1,余数是r1,即q0=k·q1+r1,则r1是a的k进制数的左数第2……若q n-1除以k所得的商是0,余数是r n,即q n-1=r n,则r n是a的k进制数的左数第1位数.这样,我们可以得到算法步骤如下:第一步,给定十进制正整数a和转化后的数的基数k.第二步,求出a除以k所得的商q,余数r.第三步,把得到的余数依次从右到左排列.第四步,若q≠0,则a=q,返回第二步;否则,输出全部余数r排列得到的k进制数.程序框图如下图:程序:INPUT “a,k=”;a,kb=0i=0DOq=a\\kr=a MOD kb=b+r*10^ii=i+1a=qLOOP UNTIL q=0PRINT bEND思路2例1 将8进制数314 706(8)化为十进制数,并编写出一个实现算法的程序.解:314 706(8)=3×85+1×84+4×83+7×82+0×81+6×80=104 902.所以,化为十进制数是104 902.点评:利用把k进制数转化为十进制数的一般方法就可以把8进制数314 706(8)化为十进制数.例2 把十进制数89化为三进制数,并写出程序语句.解:具体的计算方法如下:89=3×29+2,29=3×9+2,9=3×3+0,3=3×1+0,1=3×0+1,所以:89(10)=10 022(3).点评:根据三进制数满三进一的原则,可以用3连续去除89及其所得的商,然后按倒序的顺序取出余数组成数据即可.知能训练将十进制数34转化为二进制数.分析:把一个十进制数转换成二进制数,用2反复去除这个十进制数,直到商为0,所得余数(从下往上读)就是所求.解:即34(10)=100 010(2)拓展提升把1 234(5)分别转化为十进制数和八进制数.解:1 234(5)=1×53+2×52+3×5+4=194.则1 234(5)=302(8)所以,1 234(5)=194=302(8)点评:本题主要考查进位制以及不同进位制数的互化.五进制数直接利用公式就可以转化为十进制数;五进制数和八进制数之间需要借助于十进制数来转化.课堂小结(1)理解算法与进位制的关系.(2)熟练掌握各种进位制之间转化.作业习题1.3A组3、4.。
第一章 算法初步1.3 算法案例1.求两个正整数的最大公约数的算法 (1)辗转相除法①定义:辗转相除法是用于求_____________的最大公约数的一种算法,这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,则这时较小的数就是原来两个数的最大公约数. ②算法步骤用辗转相除法求两个正整数的最大公约数,其算法步骤如下: 第一步,给定两个正整数,m n . 第二步,计算m 除以n 所得的余数r . 第三步,,m n n r ==.第四步,若0r =,则,m n 的最大公约数等于m ;否则,返回第二步. ③程序框图如图所示:④程序如下:INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND 或INPUT m,nr=1While r>0r=m MOD nm=nn=rWENDPRINT mEND(2)更相减损术①定义:中国古代的数学专著《九章算术》中记载着“更相减损术”,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”②算法步骤第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.③程序框图④程序如下:INPUT “a ,b=”;a ,b WHILE a≠b r=a−bIF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END2.秦九韶算法(1)定义及原理:把一个n 次多项式1110()n n n n f a x a x x a x a --=++⋅⋅⋅++改写成如下形式:2110()((()))n n n f a x a x x a x a x a --=⋅⋅⋅+++⋅⋅+⋅+.求多项式的值时,首先计算最内层括号内一次多项式的值,即11n n v a x a -=+,然后由内向外逐层计算一次多项式的值,即212323,n n v v x a v v x a --=+=+,…,10n n v v x a -=+,这种求n 次多项式()f x 的值的方法叫做秦九韶算法.(2)秦九韶算法程序化的可行性探讨:观察秦九韶算法中的n 个一次式,可见计算k v 时要用到1k v -的值,若令0n v a =,我们可以得到下面的递推公式:0____________(1,2,,)n kv a v k n =⎧⎨==⋅⋅⋅⎩.这是一个在秦九韶算法中反复执行的步骤,可以用循环结构来实现. (3)算法步骤第一步,输入多项式次数n 、最高次项的系数n a 和x 的值. 第二步,将v 的值初始化为n a ,将i 的值初始化为n -1. 第三步,输入i 次项的系数i a . 第四步,,1i v vx a i i =+=-.第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多项式的值v.(4)程序框图如图所示:(5)程序如下:INPUT “n=”;nINPUT “an=”;aINPUT “x=”;xv=ai=n−1WHILE i>=0PRINT “i=”;iINPUT “ai=”;av=v*x+ai=i−1WENDPRINT vEND3.进位制(1)定义:进位制是人们为了计数和运算方便而约定的记数系统,约定满二进一,就是二进制;满十进一,就是十进制;满六十进一,就是六十进制;等等.也就是说,“满几进一”就是几进制,几进制的基数就是几.一般地,若k 是一个大于1的整数,那么以k 为基数的k 进制数可以表示为一串数字连写在一起的形式:1210()110110(,,,,,0<,0,,,)n n n k n n n n a a a a a a a a a a k a a a k ----⋅⋅⋅⋅⋅⋅∈<≤⋅⋅⋅<N .说明:①若一个数为十进制数,其基数可以省略不写.②若是其他进位制的数,在没有特别说明的前提下,其基数必须写出,常在数的右下角标明基数. (2)将k 进制数转化为十进制数 ①算法步骤:计算k 进制数a 的右数第i 位数字i a 与1i k -的乘积1i i a k -⋅,再将其累加,这是一个重复操作的步骤.所以,可以用循环结构来构造算法,算法步骤如下: 第一步,输入,a k 和n 的值.第二步,将b 的值初始化为0,i 的值初始化为1. 第三步,1,1i i b b a k i i -=+⋅=+.第四步,判断i n >是否成立.若是,则执行第五步;否则,返回第三步. 第五步,输出b 的值. ②程序框图如图所示:③程序如下:INPUT “a ,k ,n=”;a ,k ,n b=0 i=1 t=a MOD 10 DOb=b+t*k^(i−1) a=a\10 t=a MOD 10 i=i+1LOOP UNTIL i>n PRINT b END(3)将十进制数转化为k 进制数 ①转化方法:十进制数化为k 进制数用____________,即先把十进制数a 除以k ,商为0q ,余数为0r ,再把0q 除以k ,商为1q ,余数为1r ,…,反复进行这种除法,直到商1n q -除以k 所得的商为0,余数是n r ,即1n n q r -=为止,此时将所有余数按从右到左排列就得到所要求的k 进制数10()n n k r r r -⋅⋅⋅. ②算法步骤:第一步,给定十进制正整数a 和转化后的数的基数k . 第二步,求出a 除以k 所得的商q ,余数r . 第三步,把得到的余数依次从右到左排列.第四步,若0q ≠,则a q =,返回第二步;否则,输出全部余数r 排列得到的k 进制数. ③程序框图如图所示:④程序如下:INPUT “a,k=”;a,kb=0i=0DOq=a\kr=a MOD kb=b+r*10^ii=i+1a=qLOOP UNTIL q=0PRINT bEND1.(1)两个正整数 2.(2)1k n k v x a --+ 3.(3)①除k 取余法帮—重点 辗转相除法、更相减损术、秦九韶算法、进位制 帮—难点 用秦九韶算法求多项式的值,进位制间的转换 帮—易错 易对秦九韶算法中的运算次数理解错误1.辗转相除法与更相减损术辗转相除法与更相减损术有着相同的算法依据,但要注意运算过程的差别. 两者的区别是:(1)辗转相除法进行的是除法运算,即辗转相除,更相减损术进行的是减法运算,即辗转相减,但其实质都是一个不断的递推过程.(2)辗转相除法,下一次进行相除时,由上一次的除数和余数直接相除即可.而更相减损术下一次相减前必须有一个判断大小的过程,以区别谁做被减数.注意:用更相减损术求两正整数的最大公约数时,若两数为偶数,可先约去2,这时莫忘记求得的相等两数乘以约简的数才是所求的最大公约数.用辗转相除法和更相减损术求840与1764的最大公约数.【答案】840与1764的最大公约数是84. 【解析】辗转相除法: 1764=840×2+84, 840=84×10+0,∴840与1764的最大公约数是84. 更相减损术:1764–840=924, 924–840=84, 840–84=756, 756–84=672, 672–84=588, 588–84=504, 504–84=420, 420–84=336, 336–84=252, 252–84=168, 168–84=84,∴840与1764的最大公约数是84.利用辗转相除法求3869与6497的最大公约数.【答案】3869与6497的最大公约数为73. 【解析】6497=1×3869+2628, 3869=1×2628+1241, 2628=2×1241+146, 1241=8×146+73, 146=2×73,∴3869与6497的最大公约数为73.【名师点睛】辗转相除法计算次数少,而更相减损术计算次数多,但是更相减损术每一步的计算都是减法,比做除法运算要简单一些,所以一般当数较小时考虑用更相减损术,当数较大时考虑用辗转相除法. 2.秦九韶算法秦九韶算法的实质是:求多项式1110()n n n n f a x a x x a x a --=++⋅⋅⋅++的值时,转化为求n 个一次多项式的值,共进行n 次乘法运算和n 次加法运算.这种算法的运算次数较少,是多项式求值比较先进的算法.用秦九韶算法计算多项式f (x )=12+35x –8x 2+79x 3+6x 4+5x 5+3x 6在x =–4时的值时,V 3的值为( ) A .–845B .220C.–57 D.34【答案】C【解析】∵多项式f(x)=12+35x–8x2+79x3+6x4+5x5+3x6=(((((3x+5)x+6)x+79)x–8)x+35)x+12,当x=–4时,∴v0=3,v1=3×(–4)+5=–7,v2=–7×(–4)+6=34,v3=34×(–4)+79=–57.故选C.用秦九韶算法计算函数f(x)=2x4+3x3+5x–4在x=2时的函数值.【答案】62【解析】∵f(x)=2x4+3x3+5x–4=(((2x+3)x+0)x+5)x–4,∴v1=2×2+3=7,∴v2=7×2+0=14,v3=14×2+5=33,v4=33×2–4=62,∴f(2)=62.【名师点睛】利用秦九韶算法计算多项式的值的策略:(1)正确地将多项式改写,若在多项式中有几项不存在,可将这些项的系数看成0,即把这些项看做 .0n x(2)由内向外逐次计算.(3)每一步计算结果准确,由于下一次计算用到上一次计算的结果,应认真、细致地计算每一步.3.进位制把一个非十进制数转化为另一种非十进制数,通常是把这个数先转化为十进制数,然后再利用除k取余法,把十进制数转化为k进制数.1)十进制数89化为二进制的数为( )A.1001101(2)B.1011001(2)C.0011001(2)D.1001001(2)【答案】B【解析】89÷2=44…1,44÷2=22…0,22÷2=11…0,11÷2=5…1,5÷2=2…1,2÷2=1…0,1÷2=0…1,故89(10)=1 011 001(2).2)将八进制数127(8)化为十进制数. 【答案】87【解析】()21081271828786416787=⨯+⨯+⨯=++=.已知一个k 进制的数123(k )与十进制的数38相等,求k 的值.【答案】5【解析】将转化为十进制,()210212312323k k k k k k =⨯+⨯+⨯=++,由题意,得k 2+2k +3=38,所以k 2+2k –35=0,所以k =5或k =–7(舍)所以k =5.【名师点睛】除k 取余法的两个关注点:①要连续除:用k 连续去除十进制数或所得的商,直到商为零为止.②若是其他进位制的数,在没有特别说明的前提下,其基数必须写出,常在数的右下角标明基数.1.关于进位制的说法错误的是( )A .进位制是人们为了计数和运算方便而约定的记数系统B .二进制就是满二进一,十进制就是满十进一C .满几进一,就是几进制,几进制的基数就是几D .为了区分不同的进位制,必须在数的右下角标注基数【答案】D【解析】一般情况下,不同的进位制需在数的右下角标注基数,但十进制可以不用标注,故D 错误. 故选D.2.下列说法中正确的个数为( )①辗转相除法也叫欧几里得算法②辗转相除法的基本步骤是用较大的数除以较小的数③求最大公约数的方法除辗转相除法之外,没有其他方法④编写辗转相除法的程序时,要用到循环语句A .1B .2C .3D .4【答案】C【解析】依据辗转相除法可知,①②④正确,③错误,如更相减损术也是求最大公约数的方法. 故选C.3.72和168的最大公约数是( )A .24B .36C .42D .72 【答案】A【解析】由辗转相除法可知,16872224=⨯+,72243=⨯,所以,72和168的最大公约数是24. 故答案为A.【名师点睛】本题考查了辗转相除法求最大公约数的应用,属于基础题.根据辗转相除法得到结果即可.4.把十进制的23化成二进制数是 ( )A.00 110(2)B.10 111(2)C.10 111(2)D.11 101(2) 【答案】B【解析】23÷2=11…1,11÷2=5…1,5÷2=2…1,2÷2=1…0,1÷2=0…1,故23=10 111(2).5.把77化成四进制数的末位数字为 ( )A .4B .3C .2D .1 【解析】.因为77÷4=19……1,19÷4=4……3,4÷4=1……0,1÷4=0……1,故77(10)=1 031(4), 末位数字为1.【答案】D6.()2101化为十进制数是( )A .4B .5C .6D .7【答案】B【解析】01221011202125()=⨯+⨯+⨯=, 故选B .【名师点睛】本题考查的知识点是算法的概念,进制之间的转化方法,属于基础题.由二进制转化为十进制的方法,依次累加各位数字上的数×该数位的权重,即可得到结果.7.十进制数2015等值于八进制数为( )A .3737(8)B .737(8)C .03737(8)D .7373(8) 【答案】A【解析】因为3210201538783878=⨯+⨯+⨯+⨯,所以十进制数2015等值于八进制数为:3737. 故选A.【名师点睛】本题主要考查了十进制数与八进制数的换算,属于基础题.8.用更相减损术求48和132的最大公约数时,需做减法的次数是( )A .2B .3C .4D .5 【答案】D【解析】由更相减损术得:132-48=84,84-48=36,48-36=12,36-12=24,24-12=12. 故选D.9.用辗转相除法计算60和48的最大公约数时,需要做的除法次数是( )A .1B .2C .3D .4 【答案】B 【解析】∵60=1×48+12,48=4×12,∴60和48的最大公约数是12 .所以需要做的除法次数是2 . 故选B.【名师点睛】本题主要考查辗转相除法,意在考查学生对该知识的理解掌握水平和分析推理能力.直接利用辗转相除法的原理求需要做的除法次数.10.已知多项式()4335f x x x x =-+,用秦九韶算法求()5f 的值等于 ( ) A .275B .257C .55D .10【答案】A 【解析】因为()()()()432305305f x x x x x x x x x =-+⋅+=-++,代值即可. 用秦九韶算法可得: 01v =,10532v v =⨯-=,225010v =⨯+=,3105555v =⨯+=,4555275v =⨯=.所以()5f 的值为275.11.用秦九韶算法求多项式()325616f x x x x =-+-的值时,应把()f x 变形为( ) A .3)6(561x x x ---B .2(56)16()x x x -+-C .()26()31x x x ---D .5(66))1(x x x -+-【答案】D【解析】根据秦九韶算法,知f (x )=x 3–5x 2+6x –16=((x –5)x +6)x –16故选D .【名师点睛】本小题主要考查秦九韶算法,考查中国古代数学文化,属于基础题.利用秦九韶算法对原函数进行变形.12.用秦九韶算法计算多项式f (x )=2x 7+2x 6+3x 5+5x 4+6x 3–x 2–5x +21当x=2的值时,其中v 3的值为( ) A .15B .35C .40D .77 【答案】B 【解析】由公式0717kk k v a v v x a --=⎧⎨=+⎩,其中1,2,,7k =⋅⋅⋅,得02v =,12226v =⨯+=,262315v =⨯+=,3152535v =⨯+=,本题正确选项为B.【名师点睛】本题考查秦九韶算法公式的应用,属于基础题.根据秦九韶算法公式,直接代入求解即可. 13.“结绳计数”是远古时期人类智慧的结晶,即人们通过在绳子上打结来记录数量.如图所示的是一位农民记录自己采摘果实的个数.在从右向左依次排列的不同绳子上打结,满四进一.根据图示可知,农民采摘的果实的个数是( )A .493B .383C .183D .123【答案】C 【解析】根据题干知满四进一,则表示四进制数,将四进制数转化为十进制数,得到3224+34+14+3=183.⨯⨯⨯ 故答案为C.【名师点睛】本题以数学文化为载体,考查了进位制等基础知识,注意运用四进制转化为十进制数,考查运算能力,属于基础题.根据题意将四进制数转化为十进制数即可.14.若用秦九韶算法求多项式5432()3451f x x x x x x =+++++在12x =处的值,需要做乘法和加法的次数分别是( )A .5,5B .5,4C .4,5D .4,4 【答案】A【解析】多项式f (x )=3x 5+4x 4+5x 3+x 2+x +1=((((3x +4)x +5)x +1)x +1)x +1,发现要经过5次乘法、5次加法运算.故需要做乘法和加法的次数分别为:5、5.故选A .【名师点睛】本题考查秦九韶算法,考查在用秦九韶算法解题时一共会进行多少次加法和乘法运算,是一道基础题,解题时注意最后加还是不加常数项,可以直接看出结果.由秦九韶算法的原理,可以把多项式f (x )=3x 5+4x 4+5x 3+x 2+x +1变形计算出乘法与加法的运算次数.15.秦九韶算法是南宋时期数学家秦九韶提出的一种多项式简化算法,即使在现代,它依然是利用计算机解决多项式问题的最优算法,如图所示的程序框图给出了利用秦九韶算法求多项式值的一个实例,若输入n ,x 的值分別为4,5,则输出v 的值为( )A .211B .1055C .1048D .100【答案】B 【解析】由题,4n =,5x =,1v =,3i =,第一次循环:1538v =⨯+=,2i =;第二次循环:85242v =⨯+=,1i =;第三次循环:4251211v =⨯+=,0i =;第四次循环:211501055v =⨯+=,1i =-,所以输出1055,故选择B.【名师点睛】对算法初步的考查主要是对程序框图含义的理解与运用,重点放在条件结构与循环结构,对于循环结构要搞清楚进入或退出循环的条件、循环的次数,是解题的关键.将4n =,5x =代入框图,由框图循环结构得到输出值.16.把1234化为七进制数为___________.【答案】3412(7)【解析】利用除7取余法:3210123437471727=⨯+⨯+⨯+⨯,所以(7)12343412=.【名师点睛】本题考查十进制化为七进制,属于基础题.根据除k 取余法可得.17.用秦九韶算法求多项式()23456235879653f x x x x x x x =+-++++当4x =-的值时,其中1v 的值为________.【答案】−7【解析】()23456235879653f x x x x x x x =+-++++,063v a ∴==,()1053457=v v x a =+⨯-+=-.故答案为:−7.【名师点睛】本题考查秦九韶算法的原理及应用,属于基础题.根据秦九韶算法的原理得到结果. 18.(1)用辗转相除法求840与1764的最大公约数;(2)用秦九韶算法计算函数43()23542f x x x x x 当=++-=时的函数值.【答案】(1)84;(2)62.【解析】(1)∵1764÷840=2余84,840÷84=10余0,∴840与1764的最大公约数是84.(2)f (x )=2x 4+3x 3+5x −4=[(2x +3)x ·x +5]x −4,当x =2时,v 0=2;v 1=2•v 0+3=7;v 2=2•v 1=14;v 3=2•v 2+5=33;v 4=2•v 3−4=62.故x =2时的函数值为62.【名师点睛】本题考查算法的应用,考查辗转相除法和秦九韶算法,解题时按照各自算法计算即可. 19.(1)将235(7)转化为十进制的数;(2)将137化为六进制的数;(3)将53(8)转化为三进制的数.【答案】(1)(10)124;(2)(6)137345=;(3)(8)(3)531121=.【解析】(1)235(7)=2×72+3×71+5×70=124(10).(2)利用除6取余数:所以137=345(6).(3)先转为十进制的数:53(8)=5×81+3×80=43.再转为三进制的数,利用除3取余数:所以53(8)=1121(3).【名师点睛】本题考查的知识点是不同进制之间的转换,其中其他进制转为十进制的方法均为累加数字×权重,例如111111(2)= 1×25+1×24+1×23+1×22+1×2+1,十进制转换为其他进制均采用除k 求余法,例如将十进制转化为六进制,则将十进制数除以6,直到余数为0,将所有余数倒序排列即可.20.在k 进制中,数()8167记为()315k ,则k =( )A .2B .4C .6D .7 【答案】C【解析】∵167(8)=1×82+6×81+7×80=119,∴由题意可得:315(k )=3×k 2+1×k 1+5×k 0=3k 2+k +5=119,∴可得:3k 2+k −114=0,∴解得:k =6或k =193-(舍), ∴k =6.故选C .【名师点睛】本题考查的知识点是十进制与其他进制之间的转化,属于基本知识的考查.把2个数字转化成十进制数字,解方程即可得解k 的值.21.下列四个数中,数值最小的是( )A .()1025B .()454C .()210110D .()210111【答案】C【解析】由题意,对于A 中,()102525=;对于B 中,()()1041054544424=⨯+⨯=;对于C 中,()()432021010110120212120222=⨯+⨯+⨯+⨯+⨯=;对于D 中,()()432021010111120212121223=⨯+⨯+⨯+⨯+⨯=,故选C .【名师点睛】本题主要考查了其他进制与十进制的转化,其中解答中熟练掌握其他进制与十进制的之间的转化解答的关键,着重考查了运算与求解能力,属于基础题.将四个选项中的数均转化为十进制的数,比较即可得到答案.22.用秦九韶算法求多项式5432()531f x x x x x x =-++-+当2x =时的值时,3v =( )A .−5B .−7C .−9D .−11 【答案】C【解析】由秦九韶的算法思想可得01v =,1025253v v =-=-=-,()21212315v v =+=⨯-+=-, ()32212519v v =+=⨯-+=-,故选C.【名师点睛】本题考查秦九韶算法的基本思想,计算时根据秦九韶算法思想逐个计算可得出所要的结果,考查计算能力,属于中等题.利用秦九韶算法思想()011,2,,n k k n k v a v v x a k n --=⎧⎨=+=⎩的基本步骤逐步计算,可得出3v 的值. 23.计算机中常用的十六进制是逢16进1的计数制,采用数字0~9和字母A F ~共16个计数符号,这些符号与十进制的数的对应关系如下表: 十六进制 0 1 2 3 4 5 6 7 8 9 A B C D E F十进制 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15例如用十六进制表示:1B+F =A ,则用十六进制表示B D ⨯=( )A .3EB .3EC .8FD .8F【答案】D【解析】B D ⨯用十进制表示为1113143⨯=,而14381615=⨯+,所以用十六进制表示为8F . 故选D.【名师点睛】本题考查了进制之间的转化,考查了数学运算能力.先计算出B D ⨯的十进制结果,然后再把这个十进制数化为十六进制表示.24.一个k 进制的三位数与某六进制的二位数等值,则k 不可能是( )A .3B .4C .5D .7 【答案】D【解析】3进制最小的三位数:()()3610013=;4进制最小的三位数:()()4610024=; 5进制最小的三位数:()()5610041=;7进制最小的三位数:()()76100121=,∴一个7进制的三位数不可能与某6进制的二位数等值.本题正确选项为D.【名师点睛】本题考查各进制数字之间的转化问题,属于基础题.把选项各个进制最小的三位数转换为六进制的二位数,可知7进制无法实现.25.如图程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”.执行该程序框图,若输入的,a b 分别为12,18,则输出的a 的值为( )A .1B .2C .3D .6【答案】D 【解析】12<18,b =18−12=6,12>6,a =12−6=6,a =b ,输出a =6.故选D.【名师点睛】本题主要考查程序框图和更相减损术,意在考查学生对这些知识的理解掌握水平和分析推理能力.直接按照程序框图运行程序即可.26.利用秦九韶算法求f (x )=x 5+x 3+x 2+x +1当x =3时的值为( )A .121B .283C .321D .239 【答案】B【解析】函数()()()()()532101111f x x x x x x x x x x =++++=+++++,当3x =时,分别算出01v =,13+039v ()=⨯=,29+13=30v =⨯(),330+13=93v =⨯(),493+13+1283v =⨯=(),即当3x =时的函数值f (3)283=.故选B.【名师点睛】本题考查了秦九韶算法计算函数值,考查了计算能力,属于基础题.27.远古时期,人们通过在绳子上打结来记录数量,即“结绳计数”,如图所示的是一位母亲记录的孩子自出生后的天数,在从右向左依次排列的不同绳子上打结,满六进一,根据图示可知,孩子已经出生的天数是_________.【答案】341【解析】由题意满六进一,可知该图示为六进制数,化为十进制数为1×63+3×62+2×6+5=341.故答案为341.【名师点睛】本题考查了六进制数化为十进制数应用问题,是基础题.由题意知该数为六进制,转化为十进制数即可.28.用秦九韶算法求多项式5432()42 3.5 2.6 1.70.8f x x x x x x =++-+-当3x =时的值为_________.【答案】1209.4【解析】多项式()543242 3.5 2.6 1.70.8f x x x x x x =++-+-=((((42) 3.5) 2.6) 1.7)0.8x x x x x ++-+- 04v =,103214v v =+=,213 3.545.5v v =+=,323 2.6133.9v v =-=,433 1.7403.4v v =+=,5430.81209.4v v =-=,故答案为1209.4【名师点睛】本题是一道考查秦九韶算法的题目,把普通多项式化成秦九韶算法多项式是解题的关键,属于较为基础题.先用秦九韶算法将多项式化简为()f x =((((42) 3.5) 2.6) 1.7)0.8x x x x x ++-+-,再计算即可.29.古时候,当边境有敌人来犯时,守边的官兵通过在烽火台上点火向国内报告,如图,烽火台点火表示数字1,不点火表示数字0,约定二进制数对应的十进制数的单位是1000.请你计算一下,这组烽火台表示有多少敌人入侵?【答案】27000.【解析】由图可知这组烽火台表示的二进制数为11011(2),它表示的十进制数为1×24+1×23+0×22+1×21+1×20=27,由于对应的十进制单位是1000,所以入侵敌人的数目为27×1000=27000.30.分别用辗转相除法和更相减损术求261,319的最大公约数.【解析】辗转相除法:319=261×1+58,261=58×4+29,58=29×2.所以319与261的最大公约数是29.更相减损术:319-261=58,261-58=203,203-58=145,145-58=87,87-58=29,58-29=29,所以319与261的最大公约数是29.31.利用辗转相除法求3869与6497的最大公约数.【答案】73【解析】6497=1×3869+2628,3869=1×2628+1241,2628=2×1241+146,1241=8×146+73,146=2×73,所以3869与6497的最大公约数为73.【名师点睛】本题考查辗转相除法,解题的关键是熟练掌握辗转相除的方法和步骤,属于基础题.将所求两数中较大的数除以较小的数,求得商和余数;然后把除数作为被除数,余数作为除数,继续求得商和余数,直到余数为0为止,则最后一步中的除数即为最大公约数.32.用秦九韶算法计算多项式542()3257f x x x x x =-++-当2x =时的值.【答案】71【解析】根据秦九韶算法把多项式改写成()=((((3 2) 0) 1) 5) 7f x x x+x+x+x --.由题意知03v =,1043224,v v x a =+=⨯-=2134208v v x a =+=⨯+=,32282117v v x a =+=⨯+=,431172539v v x a =+=⨯+=,540392771v v x a =+=⨯-=.所以当2x =时,多项式()f x 的值为(2)71f =.【名师点睛】本题主要考查了秦九韶算法计算多项式的值,考查了数学运算能力.求解时,先根据秦九韶算法把多项式改写成()=((((3 2) 0) 1) 5) 7f x x x+x+x+x --,从而知03v =,2x =,再依次求出12345v v v v v 、、、、.33.【2016年高考四川理数】秦九韶是我国南宋时期的数学家,普州(现四川省安岳县)人,他在所著的《数书九章》中提出的多项式求值的秦九韶算法,至今仍是比较先进的算法.如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例,若输入n ,x 的值分别为3,2,则输出v 的值为(A )9 (B )18 (C )20 (D )35【答案】B考点:1.程序与框图;2.秦九韶算法;3.中国古代数学史.【名师点睛】程序框图是高考的热点之一,几乎是每年必考内容,多半是考循环结构,基本方法是将每次循环的结果一一列举出来,与判断条件比较即可.34.【2015高考新课标2】右边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”.执行该程序框图,若输入,a b 分别为14,18,则输出的a =( )A .0B .2C .4D .14【答案】B【解析】程序在执行过程中,a ,b 的值依次为14a =,18b =;4b =;10a =;6a =;2a =;2b =,此时2a b ==程序结束,输出a 的值为2,故选B .【名师点睛】本题考查程序框图,要注意依序进行,认真判断条件来决定程序的执行方向,属于中档题.。