2020版高中数学 第一章 算法初步 1.3 算法案例课件 新人教A版必修3

【课标要求】1.理解辗转相除法与更相减损术的含义，了解其执行过程.2.体会秦九韶算法的计算过程，并了解它提高计算效率的实质.3.理解进位制的概念，能进行不同进位制间的转化.4.了解进位制的程序框图和程序.知识导图学法指导1.明确辗转相除法和更相减损术的区别与联系，并能灵活运用它们求最大公约数．2．运用秦九韶算法求解多项式的值的关键是将多项式进行改写，然后由内向外进行计算．3．在进行不同进制数的转换时，体会十进制的桥梁作用.知识点一辗转相除法1．辗转相除的算法思想(1)辗转相除法是用于求两个正整数的____________的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫________算法．(2)所谓辗转相除法，就是对于给定的两个数，用较____的数除以较____的数．若余数不为零，则将________________构成新的一对数，继续上面的除法，直到________________，这时________就是原来两个数的最大公约数．最大公约数欧几里得大小余数和较小的数大数被小数除尽较小的数2．辗转相除法的算法步骤第一步，给定两个正整数m、n.第二步，计算m除以n所得的________.第三步，________________.第四步，若r＝0，则m、n的最大公约数等于____，否则返回第二步．余数rm＝n，n＝rm3．程序框图和相应程序状元随笔辗转相除法没有对m，n的大小进行讨论的原因是若输入的mn，只要执行一次循环，程序就会将m和n的值交换过来，这就保证了mn.用辗转相除法求最大公约数时，首先判断两个正整数是否都是偶数．若是，用2约简，再求最大公约数，这样不影响最后结果．知识点二更相减损术1．更相减损术的算法思想(1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数____________的方法．(2)更相减损术的基本过程：第一步，任意给定两个正整数，判断它们是否都是____．若是，用2约简；若不是，执行第二步．第二步，以____的数减去____的数，接着把所得的差与____的数比较，并以____________，继续这个操作，直到所得的数____为止，则这个数(等数)或这个数与________的乘积就是所求的最大公约数．最大公约数偶数较大较小较小大数减小数相等约简的数2．更相减损术的步骤算法步骤：第一步，输入两个正整数a，b(假设a，b不同时为偶数，且ab)．第二步，________________.第三步，如果br，则把____赋予a，把____赋予b；否则把r赋予____.第四步，若a＝b，则a，b的最大公约数为____，否则，返回________．求a－b的差rbraa第二步3．程序框图及相应程序状元随笔辗转相除法与更相减损术的比较(1)辗转相除法中，上一次运算的除数和余数分别作为下一次运算的被除数和除数，其结果直至余数为零得出．更相减损术在上一次运算结束后，比较减数和差的大小，将大的作为下一次运算的被减数，小的作为减数，直至出现相等数时得到结果．(2)两者的主要区别在于，辗转相除法进行的是除法运算，即辗转相除；更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递推过程．(3)两者在算法设计上有一个重要的区别点，辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可．而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数．知识点三秦九韶算法1．秦九韶算法秦九韶算法是我国南宋时期的数学家秦九韶在他的著作《九章算术》中提出的一种计算________的方法．求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求________________的值，共进行n次____运算和n次____运算．多项式值n个一次多项式乘法加法2．秦九韶算法的原理把f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.求多项式的值时，首先计算________括号内____________的值，即v1＝____________，然后由内向外逐层计算一次多项式的值，即v2＝____________，v3＝____________，…，vn＝____________，这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．最内层一次多项式anx＋an－1v1x＋an－2v2x＋an－3vn－1x＋a03．程序框图与相应程序状元随笔秦九韶算法的特点(1)化高次多项式求值为一次多项式求值．(2)减少了运算次数，提高了效率．(3)步骤重复执行，容易用计算机实现．知识点四进位制1．进位制的概念进位制是人们为了计数和运算方便而约定的记数系统．“满k进一”就是k进制，k进制的基数是k(基数都是大于1的整数)．2．k进制的表示方法一般地，若k是—个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式：anan－1…a1a0(k)(an，an－1，…，a1，a0∈N,0ank,0≤an－1，…，a1，a0k)．3．进位制的转化(1)k进制转化为十进制的方法anan－1an－2…a1a0(k)＝____________________________________(an，an－1，…，a1，a0∈N,0ank,0≤an－1，…，a1，a0k)．(2)十进制化为k进制的方法——____________．an×kn＋an－1×kn－1＋…＋a1k＋a0除k取余法(3)k进制数a(共有n位)化为十进制数b的程序框图及相应程序如下：状元随笔(1)若一个数为十进制数，其基数可以省略不写．(2)若是其他进制的数，在没有特别说明的前提下，其基数必须写出，常在数的右下角标明基数．(3)在k进制中．具有k个数字符号，例如十进制，有0,1,2,3,4,5,6,7,8.9十个数字．十六进制有0～9和A，B，C，D，E，F共十六个计数符号．(4)在k进制中，由低位向高位按满k进一的规则进行记数．例如十进制，满十进一，二进制满二进一．[小试身手]1．判断下列各题．(对的打“√”，错的打“×”)(1)辗转相除法与更相减损术是求两个正数最小公倍数的方法．()(2)利用秦九韶算法多项式f(x)＝x6－5x5＋6x4＋x2＋3x＋2，当x＝－2时，f(－2)＝320()(3)不同进位制的数可以相互转化．()×√√2．用“辗转相除法”求得459和357的最大公约数是()A．3B．9C．17D．51解析：利用辗转相除法，得459＝357×1＋102，357＝102×3＋51，102＝51×2＋0，所以459和357的最大公约数是51.答案：D3．把189化为三进制数，则末位数字是()A．0B．1C．2D．3解析：采用“除k取余法”，得即189＝21000(3)．答案：A4．完成下列进位制之间的转化．(1)1034(7)＝________(10)；(2)119(10)＝________(6)．解析：(1)1034(7)＝1×73＋0×72＋3×7＋4×70＝368(10)．(2)所以119(10)＝315(6)．答案：(1)368(2)315类型一求最大公约数例1用辗转相除法或者更相减损术求三个数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.状元随笔先求两个数的最大公约数，所求得的最大公约数和第三个数的最大公约数即三个数的最大公约数．方法归纳三个数的最大公约数的求解方法：先从三个数中任取两个数，用辗转相除法或更相减损术求它们的最大公约数，然后再根据辗转相除法或更相减损术求所求得的最大公约数和第三个数的最大公约数，最后求得的最大公约数即为这三个数的最大公约数．跟踪训练1用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果．解析：用辗转相除法：612＝468×1＋144,468＝144×3＋36,144＝36×4，即612和468的最大公约数是36.用更相减损术检验：612和468为偶数，两次用2约简得153和117,153－117＝36,117－36＝81,81－36＝45,45－36＝9,36－9＝27,27－9＝18,18－9＝9，所以612和468的最大公约数为9×2×2＝36.类型二秦九韶算法的应用例2用秦九韶算法求当x＝3时多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值．【解析】f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x，所以有v0＝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＝2369；v6＝2369×3＋1＝7108；v7＝7108×3＝21324.故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21324.首先需要将原多项式化为f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x的形式，再弄清v0,v1,v2,…，v7分别是多少，再针对这些式子进行计算．方法归纳利用秦九韶算法求多项式的值的步骤“改写多项式，由内向外算，步步执行完”．其中“改写多项式”是指将n次多项式改写为若干个一次多项式的复合形式；“由内向外算”是指先由v0计算最内层的括号内的值v1，再向外层扩展计算v2，…；“步步执行完”是指要计算到vn.如果多项式有空项，一定要补上系数为0的相应项．跟踪训练2已知f(x)＝x5＋x3＋x2＋x＋1.用秦九韶算法求f(3)的值．解析：原多项式可化为f(x)＝((((x＋0)x＋1)x＋1)x＋1)x＋1，当x＝3时，v0＝1；v1＝1×3＋0＝3；v2＝3×3＋1＝10；v3＝10×3＋1＝31；v4＝31×3＋1＝94；v5＝94×3＋1＝283；所以f(3)的值为283.类型三不同进位制之间的转化例3(1)下列各数转化成十进制数后最小的是()A．111111(2)B．210(6)C．1000(4)D．81(9)(2)把389化为四进制数，则该数的末位是()A．1B．2C．3D．4【解析】(1)111111(2)＝1×25＋1×24＋1×23＋1×22＋1×21＋1×20＝63，210(6)＝2×62＋1×61＋0×60＝78，1000(4)＝1×43＝64，81(9)＝8×91＋1×90＝73.所以最小的数为111111(2)．(2)方法一由389＝4×97＋1,97＝4×24＋1,24＝4×6＋0,6＝4×1＋2,1＝4×0＋1，可知389化为四进制数为12011(4)，故该数的末位是1.方法二以4作为除数，相应的除法算式如图所示，所以389＝12011(4)．显然该数的末位是1.【答案】(1)A(2)A用除4取余法求解，还可以用除法算式表示．方法归纳1．把k进制数写成不同位上数字与基数的幂的乘积之和可转化为十进制数，即anan－1…a1a0(k)＝an·kn＋an－1·kn－1＋…＋a1·k＋a0.2．十进制数化为k进制数用除k取余法．3．把非十进制数转化为另一种非十进制数，通常先把这个非十进制数转化为十进制数，再利用除k取余法，把十进制数转化为另一种非十进制数．而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各