资源描述
第一章算法初步,1.3,算法案例,第1页,学习目标,1.,了解辗转相除法与更相减损术含义，了解其执行过程,.,2.,了解秦九韶算法计算过程，并了解它提升计算效率实质,.,3.,了解进位制概念，能进行不一样进位制间转化,.,4.,了解进位制程序框图和程序,.,第2页,知识梳理,自主学习,题型探究,重点突破,当堂检测,自查自纠,栏目索引,第3页,知识梳理,自主学习,知识点一辗转相除法与更相减损术,1.,辗转相除法,(1),辗转相除法，又叫欧几里得算法，是一个求两个正整数,古老而有效算法,.,(2),辗转相除法算法步骤,第一步，给定,.,第二步，计算,.,第三步，,.,第四步，若,r,0,，则,m,，,n,最大条约数等于,；不然，返回,.,最大条约数,两个正整数,m,，,n,m,除以,n,所得余数,r,m,n,，,n,r,m,第二步,答案,第4页,2.,更相减损术,第一步，任意给定两个正整数，判断它们是否都是,.,若是，用,约简；若不是，执行,.,第二步，以,数减去,数，接着把所得差与,数比较，并以大数减小数,.,继续这个操作，直到所得数,为止，则这个数,(,等数,),或这个数与约简数乘积就是所求最大条约数,.,偶数,2,第二步,较大,较小,较小,相等,答案,第5页,3.,辗转相除法和更相减损术区分与联络：,名称,辗转相除法,更相减损术,区分,(1)以除法为主；,(2)两个整数差值较大时，运算次数较少；,(3)相除，余数为0时得结果,(1)以减法为主；,(2)两个整数差值较大时，运算次数较多；,(3)相减，减数与差相等时得结果；,(4)相减前要进行是否都是偶数判断,联络,(1)都是求两个正整数最大条约数方法；,(2)二者实质都是递推过程；,(3)二者都要用循环结构来实现,第6页,思索,实际应用更相减损术时要做第一步工作是什么？,答,先判断,a,，,b,是否为偶数，若是，都除以,2,再进行,.,答案,第7页,知识点二秦九韶算法,1.,秦九韶算法介绍,(1),秦九韶算法要处理问题是求多项式值,.,(2),秦九韶算法特点：,经过一次式重复计算，逐步得到高次多项式值，即将一个,n,次多项式求值问题归结为重复计算,n,个一次多项式值问题,.,第8页,(3),秦九韶算法原理：,将,f,(,x,),a,n,x,n,a,n,1,x,n,1,a,1,x,a,0,改写为：,f,(,x,),(,a,n,x,n,1,a,n,1,x,n,2,a,1,),x,a,0,(,a,n,x,n,2,a,n,1,x,n,3,a,2,),x,a,1,),x,a,0,先计算最内层括号内一次多项式值，即,v,1,a,n,x,a,n,1,，再由内向外逐层计算一次多项式,v,k,值,.,第9页,2.,秦九韶算法操作方法,(1),算法步骤以下：,第一步，输入多项式次数,n,、最高次项系数,a,n,和,x,值,.,第二步，将,v,值初始化为,a,n,，将,i,值初始化为,n,1.,第三步，输入,i,次项系数,a,i,.,第四步，,v,v,x,a,i,，,i,i,1.,第五步，判断,i,是否大于或等于,0.,若是，则返回第三步；不然，输出多项式值,v,.,第10页,(2),程序框图如图所表示,.,第11页,(3),程序以下：,INPUT,“,n,”,；,n,INPUT,“,an,”,；,a,INPUT,“,x,”,；,x,v,a,i,n,1,WHILE,i,0,PRINT,“,i,”,；,i,INPUT,“,ai,”,；,a,v,v*x,a,i,i,1,WEND,PRINT,v,END,第12页,知识点三进位制,1.,进位制概念,进位制是为了计数和运算方便而约定记数系统，约定,“,满几进一,”,就是几进制，几进制基数,(,大于,1,整数,),就是几,.,2.,常见进位制,(1),二进制：,只使用,0,和,1,两个数学；,满二进一，即,1,1,10,(2).,第13页,(2),八进制,：,使用,0,1,2,3,4,5,6,7,这八个不一样数学,；,满八进一,，,即,7,1,10,(8),(3),十六进制,：,使用,0,9,十个数字和,A,F,表示,10,15,；,F,1,10,(16),第14页,思索,任何进位制中都要用到数字是什么？,答,0,和,1.,返回,答案,第15页,题型探究,重点突破,题型一求两个正整数最大条约数,例,1,分别用辗转相除法和更相减损术求,261,和,319,最大条约数,.,解,方法一,(,辗转相除法,),319261,1(,余,58),，,26158,4(,余,29),，,5829,2(,余,0),，,所以,319,与,261,最大条约数为,29.,方法二,(,更相减损术,),319,261,58,，,261,58,203,，,203,58,145,，,145,58,87,，,87,58,29,，,58,29,29,，,29,29,0,，,所以,319,与,261,最大条约数是,29.,解析答案,反思与感悟,第16页,反思与感悟,(1),利用辗转相除法求给定两个数最大条约数，即利用带余除法，用数对中较大数除以较小数，若余数不为零，则将余数和较小数组成新数对，再利用带余除法，直到大数被小数除尽，则这时较小数就是原来两个数最大条约数,.,(2),利用更相减损术求两个正整数最大条约数普通步骤是：首先判断两个正整数是否都是偶数,.,若是，用,2,约简,.,也能够不除以,2,，直接求最大条约数，这么不影响最终结果,.,第17页,跟踪训练,1,用辗转相除法求,80,与,36,最大条约数，并用更相减损术检验你结果,.,解,80,36,2,8,，,36,8,4,4,8,4,2,0,，,即,80,与,36,最大条约数是,4.,验证：,802,40,362,18,；,402,20,182,9,；,209,11,11,9,2,；,9,2,7,7,2,5,；,5,2,3,3,2,1,；,2,1,1,1,2,2,4,；,所以,80,与,36,最大条约数为,4.,解析答案,第18页,题型二秦九韶算法应用,例,2,用秦九韶算法求多项式,f,(,x,),x,5,5,x,4,10,x,3,10,x,2,5,x,1,当,x,2,时值,.,解,f,(,x,),x,5,5,x,4,10,x,3,10,x,2,5,x,1,(,x,5),x,10),x,10),x,5),x,1.,当,x,2,时，有,v,0,1,；,v,1,v,0,x,a,4,1,(,2),5,3,；,v,2,v,1,x,a,3,3,(,2),10,4,；,v,3,v,2,x,a,2,4,(,2),10,2,；,v,4,v,3,x,a,1,2,(,2),5,1,；,v,5,v,4,x,a,0,1,(,2),1,1.,故,f,(,2),1.,解析答案,反思与感悟,第19页,反思与感悟,(1),先将多项式写成一次多项式形式，然后运算时从里到外，一步一步地做乘法和加法即可,.,这么比直接将,x,2,代入原式大大降低了计算量,.,若用计算机计算，则可提升运算效率,.,(2),注意：当多项式中,n,次项不存在时，可将第,n,次项看作,0,x,n,.,第20页,跟踪训练,2,用秦九韶算法计算多项式,f,(,x,),x,6,12,x,5,60,x,4,160,x,3,240,x,2,192,x,64,当,x,2,时值,.,解,依据秦九韶算法，把多项式改写成以下形式：,f,(,x,),(,x,12),x,60),x,160),x,240),x,192),x,64.,由内向外依次计算一次多项式当,x,2,时值；,v,0,1,；,v,1,1,2,12,10,；,v,2,10,2,60,40,；,v,3,40,2,160,80,；,v,4,80,2,240,80,；,v,5,80,2,192,32,；,v,6,32,2,64,0.,所以当,x,2,时，多项式值为,0.,解析答案,第21页,题型三进位制之间互化,例,3,(1),把二进制数,1110011,(2),化为十进制数,.,解,1110011,(2),1,2,6,1,2,5,1,2,4,0,2,3,0,2,2,1,2,1,1,115.,(2),将,8,进制数,314706,(8),化为十进制数,.,解,314706,(8),3,8,5,1,8,4,4,8,3,7,8,2,0,8,1,6,8,0,104 902.,所以，化为十进制数是,104 902.,解析答案,反思与感悟,第22页,反思与感悟,(1),将,k,进制转化为十进制方法是：先将这个,k,进制数写成各个数位上数字与,k,幂乘积之和形式，再按照十进制运算规则计算出结果,.,(2),十进制转化为,k,进制，采取除,k,取余法，也就是除基数，倒取余,.,第23页,跟踪训练,3,将,53,(8),转化为二进制数,.,解,先将八进制数,53,(8),转化为十进制数：,53,(8),5,8,1,3,8,0,43,；,再将十进制数,43,转化为二进制数：,所以,53,(8),101011,(2).,解析答案,第24页,转化与化归思想,思想方法,例,4,以下各数中，最小数是,(,),A.85,(9),B.210,(6),C.1000,(4),D.111111,(2),分析,先将它们转化为十进制数，再进行比较,.,解析,85,(9),8,9,5,77,210,(6),2,6,2,1,6,0,78,1000,(4),1,4,3,64,111111,(2),1,2,5,1,2,4,1,2,3,1,2,2,1,2,1,63.,故最小是,63.,D,解析答案,解后反思,分析,第25页,解后反思,合理转化是解题关键,.,对于进位制之间转化问题，普通要先把,k,进制数转化为十进制数，再转化为其它进制数,.,第26页,数制转化方法掌握不牢致错,易错点,例,5,把十字进制数,49,化为二进制数,.,分析,对进位制间换算，要搞清解题方法，将十进制数转化为,k,进制数用,“,除,k,取余法,”.,解,所以,49,110 001,(2).,解后反思,本例常出现错误是把上式中各步所得余数从上到下排列，这是基本方法掌握不牢造成，应加以注意,.,分析,解析答案,解后反思,返回,第27页,当堂检测,1,2,3,4,5,1.1 337,与,382,最大条约数是,(,),A.3 B.382 C.191 D.201,解析,利用辗转相除法，,1 337,382,3,191,382,191,2,，,故两数最大条约数为,191.,C,解析答案,第28页,1,2,3,4,5,2.,把,189,化为三进制数，则末位数字是,(,),A.0 B.1 C.2 D.3,解析,采取,“,除,k,取余法,”,，得,即,189,21 000,(3),A,解析答案,第29页,1,2,3,4,5,3.,用秦九韶算法求,n,次多项式,f,(,x,),a,n,x,n,a,n,1,x,n,1,a,1,x,a,0,当,x,x,0,时值，求,f,(,x,0,),需要乘方、乘法、加法次数分别为,(,),A.,，,n,，,n,B.,n,2,n,，,n,C.0,2,n,，,n,D.0,，,n,，,n,解析,因为,f,(,x,),(,(,a,n,x,a,n,1,),x,a,n,2,),x,a,1,),x,a,0,，,所以乘方、乘法、加法次数分别为,0,，,n,，,n,.,D,解析答案,第30页,1,2,3,4,5,解析答案,4,秦九韶是我国南宋时期数学家，普州,(,现四川省安岳县,),人，他在所著,数书九章,中提出多项式求值秦九韶算法，至今仍是比较先进算法如图所表示程序框图给出了利用秦九韶算法求某多项式值一个实例，若输入,n,，,x,值分别为,3,2,，,则输出,v,值为,(,),A,9 B,18,C,20 D,35,第31页,1,2,3,4,5,解析,初始值,n,3,，,x,2,，,程序运行过程以下,v,1,i,2,v,1,2,2,4,i,1,v,4,2,1,9,i,0,v,9,2,0,18,i,1,跳出循环,，,输出,v,18,，,选,B.,答案,B,解析答案,第32页,1,2,3,4,5,5.,用更相减损术求,36,与,134,最大条约数，第一步应为,_,_.,解析,36,与,134,都是偶数，,第一步应为：先除以,2,，得到,18,与,67.,先除以,2,，得到,18,与,67,解析答案,第33页,课堂小结,返回,1.,求两个正整数最大条约数问题，能够用辗转相除法，也能够用更相减损术,.,用辗转相除法，即依据,a,nb,r,这个式子，重复相除，直到,r,0,为止；用更相减损术，即依据,r,|,a,b,|,这个式子，重复相减，直到,r,0,为止,.,2.,秦九韶算法关键在于把,n,次多项式转化为一次多项式，注意体会递推实现过程，实施运算时要由内向外，一步一步执行,.,3.,把一个非十进制数转化为另一个非十进制数，通常是把这个数先转化为十进制数，然后再利用除,k,取余法，把十进制数转化为,k,进制数,.,而在使用除,k,取余法时要注意以下几点：,(1),必须除到所得商是,0,为止；,(2),各步所得余数必须从下到上排列；,(3),切记在所求数右下角标明基数,.,第34页,本课结束,第35页,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
