高中数学算法初步1.3算法案例

第一章算法初步1.3

算法案例第1页学习目标1.了解辗转相除法与更相减损术含义，了解其执行过程.2.了解秦九韶算法计算过程，并了解它提升计算效率实质.3.了解进位制概念，能进行不一样进位制间转化.4.了解进位制程序框图和程序.第2页知识梳理自主学习题型探究重点突破当堂检测自查自纠栏目索引第3页知识梳理自主学习知识点一辗转相除法与更相减损术1.辗转相除法(1)辗转相除法，又叫欧几里得算法，是一个求两个正整数

古老而有效算法.(2)辗转相除法算法步骤第一步，给定

.第二步，计算

.第三步，

.第四步，若r＝0，则m，n最大条约数等于

；不然，返回

.最大条约数两个正整数m，nm除以n所得余数rm＝n，n＝rm第二步答案第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)＝anxn＋an－1xn－1＋…＋a1x＋a0改写为：f(x)＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…先计算最内层括号内一次多项式值，即v1＝anx＋an－1，再由内向外逐层计算一次多项式vk值.第9页2.秦九韶算法操作方法(1)算法步骤以下：第一步，输入多项式次数n、最高次项系数an和x值.第二步，将v值初始化为an，将i值初始化为n－1.第三步，输入i次项系数ai.第四步，v＝vx＋ai，i＝i－1.第五步，判断i是否大于或等于0.若是，则返回第三步；不然，输出多项式值v.第10页(2)程序框图如图所表示.第11页(3)程序以下：INPUT

“n＝”；nINPUT

“an＝”；aINPUT

“x＝”；xv＝ai＝n－1WHILE

i＞＝0

PRINT

“i＝”；i

INPUT

“ai＝”；a

v＝v*x＋a

i＝i－1WENDPRINT

vEND第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最大条约数.解方法一(辗转相除法)319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝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.验证：80÷2＝40,36÷2＝18；40÷2＝20,18÷2＝9；20—9＝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)＝x5＋5x4＋10x3＋10x2＋5x＋1当x＝－2时值.解f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1＝((((x＋5)x＋10)x＋10)x＋5)x＋1.当x＝－2时，有v0＝1；v1＝v0x＋a4＝1×(－2)＋5＝3；v2＝v1x＋a3＝3×(－2)＋10＝4；v3＝v2x＋a2＝4×(－2)＋10＝2；v4＝v3x＋a1＝2×(－2)＋5＝1；v5＝v4x＋a0＝1×(－2)＋1＝－1.故f(－2)＝－1.解析答案反思与感悟第19页反思与感悟(1)先将多项式写成一次多项式形式，然后运算时从里到外，一步一步地做乘法和加法即可.这么比直接将x＝－2代入原式大大降低了计算量.若用计算机计算，则可提升运算效率.(2)注意：当多项式中n次项不存在时，可将第n次项看作0·xn.第20页跟踪训练2

用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时值.解依据秦九韶算法，把多项式改写成以下形式：f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64.由内向外依次计算一次多项式当x＝2时值；v0＝1；

v1＝1×2－12＝－10；v2＝－10×2＋60＝40；

v3＝40×2－160＝－80；v4＝－80×2＋240＝80；

v5＝80×2－192＝－32；v6＝－32×2＋64＝0.所以当x＝2时，多项式值为0.解析答案第21页题型三进位制之间互化例3

(1)把二进制数1110011(2)化为十进制数.解1110011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋1×21＋1＝115.(2)将8进制数314706(8)化为十进制数.解314706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80＝104902.所以，化为十进制数是104902.解析答案反思与感悟第22页反思与感悟(1)将k进制转化为十进制方法是：先将这个k进制数写成各个数位上数字与k幂乘积之和形式，再按照十进制运算规则计算出结果.(2)十进制转化为k进制，采取除k取余法，也就是除基数，倒取余.第23页跟踪训练3

将53(8)转化为二进制数.解先将八进制数53(8)转化为十进制数：53(8)＝5×81＋3×80＝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×62＋1×6＋0＝78,1000(4)＝1×43＝64,111111(2)＝1×25＋1×24＋1×23＋1×22＋1×2＋1＝63.故最小是63.D解析答案解后反思分析第25页解后反思合理转化是解题关键.对于进位制之间转化问题，普通要先把k进制数转化为十进制数，再转化为其它进制数.第26页

数制转化方法掌握不牢致错易错点例5

把十字进制数49化为二进制数.分析对进位制间换算，要搞清解题方法，将十进制数转化为k进制数用“除k取余法”.解所以49＝110001(2).解后反思本例常出现错误是把上式中各步所得余数从上到下排列，这是基本方法掌握不牢造成，应加以注意.分析解析答案解后反思返回第27页当堂检测123451.1337与382最大条约数是(

)A.3 B.382 C.191 D.201解析利用辗转相除法，1337＝382×3＋191,382＝191×2，故两数最大条约数为191.C解析答案第28页123452.把189化为三进制数，则末位数字是(

)A.0 B.1 C.2 D.3解析采取“除k取余法”，得即189＝21000(3)A解析答案第29页123453.用秦九韶算法求n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时值，求f(x0)需要乘方、乘法、加法次数分别为(

)A.，n，n B.n,2n，nC.0,2n，n D.0，n，n解析因为f(x)＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，所以乘方、乘法、加法次数分别为0，n，n.D解析答案第30页12345解析答案4．秦九韶是我国南宋时期数学家，普州(现四川省安岳县)人，他在所著《数书九章》中提出多项式求值秦九韶算法，至今仍是比较先进算法．如图所表示程序框图给出了利用秦九韶算法求某多项式值一个实例，若输入n，x值分别为3,2，则输出v值为(

)A．9 B．18C．20 D．35第31页1234