13-算法案例-课件解读

1．3算法案例第一章算法初步1．3算法案例第一章算法初步学习导航学习导航新知初探思维启动1．辗转相除法所谓辗转相除法，就是对于任意给定的两个正整数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个数的最大公约数．新知初探思维启动1．辗转相除法想一想1.辗转相除法中的关键步骤可用哪种逻辑结构来实现？提示：辗转相除法中带余数除法是一个反复执行、直到余数等于0停止的步骤，可用循环结构来实现．想一想2．更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的任意一种求两个正整数最大公约数的方法．其基本过程是：对于给定的两个正整数,判断它们是否都是偶数．若是,用2约简；若不是，则用____________________

，接着把所得的____

与__________

比较，并以大数减小数．继续这个操作，直到所得的数______

为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．较大数减去较小的数差较小的数相等2．更相减损术较大数减去较小的数差较小的数相等想一想2.实际应用更相减损术时要做的第一步工作是什么？提示：先判断a，b是否全为偶数，若是，则先都除以2再进行．想一想3．秦九韶算法(1)算法原理它是通过一次式的反复计算，逐步得出高次多项式的值的一种求多项式函数值的算法．设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＝…3．秦九韶算法首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值．这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1想一想3.怎样设计秦九韶算法，程序框图及程序呢？提示：算法步骤如下：第一步，输入多项式次数n、最高次项的系数an和x的值．第二步，将v的值初始化为an，将i的值初始化为n－1.第三步，输入i次项的系数ai.第四步，v＝vx＋ai，i＝i－1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.想一想13-算法案例-课件解读4．进位制(1)进位制的概述进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制；等等．也就是说，“___________”就是几进制，几进制的基数(大于1的整数)就是几．一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注基数(k)，以示区别．例如，270(8)表示270是一个八进制数．十进制数一般不标注基数．满几进一4．进位制满几进一(2)常见的进位制①二进制：a：只使用0和1两个数字；b：满二进一，如1＋1＝10.②八进制：a：使用0,1,2,3,4,5,6,7八个不同的数字；b：满八进一，如7＋1＝10.③十六进制：a：使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个不同的数码，其中A，B，C，D，E，F分别代表十进制中的10,11,12,13,14,15；b：满十六进一，如F＋1＝2＋E＝10.(2)常见的进位制(3)不同进位制数之间的转化①k进制数转化为十进制数把k进制数转化为十进制数，写成不同位上数字与基数幂的乘积之和即可(简称幂积求和)，即anan－1…a1a0(k)＝an×kn＋an－1×kn－1＋…＋a1×k＋a0.例如，将二进制数11001(2)化为十进制数：11001(2)＝1×24＋1×23＋0×22＋0×21＋1×20＝16＋8＋1＝25.(3)不同进位制数之间的转化13-算法案例-课件解读典题例证技法归纳题型探究例1典题例证技法归纳题型探究例1【解】辗转相除法：80＝36×2＋8,36＝8×4＋4,8＝4×2＋0.故80和36的最大公约数是4.用更相减损术检验：80－36＝44，44－36＝8，36－8＝28，28－8＝20，20－8＝12，12－8＝4，8－4＝4，∴80和36的最大公约数是4.【名师点评】

解决此类问题要弄清它们的理论依据，根据理论依据一步一步计算出80和36的最大公约数．【解】辗转相除法：跟踪训练1．求108与45的最大公约数．解：法一：由辗转相除法，得108＝45×2＋18，45＝18×2＋9，18＝9×2，故108与45的最大公约数是9.跟踪训练法二：由更相减损术，得108－45＝63，63－45＝18，45－18＝27，27－18＝9，18－9＝9，故108与45的最大公约数是9.法二：由更相减损术，得例2题型二秦九韶算法及应用

(2013·福州高一检测)用秦九韶算法写出当x＝3时f(x)＝2x5－4x3＋3x2－5x＋1的值．例2题型二秦九韶算法及应用【解】

∵f(x)＝((((2x－0)x－4)x＋3)x－5)x＋1，v0＝2，v1＝2×3＋0＝6，v2＝6×3－4＝14，v3＝14×3＋3＝45，v4＝45×3－5＝130，v5＝130×3＋1＝391，所以f(3)＝391.【名师点评】利用秦九韶算法计算多项式值的关键是能准确地将多项式改写,然后由内向外逐次计算.由于后项计算用到前项的结果,故应认真、细心，确保每项计算结果的准确性．【解】∵f(x)＝((((2x－0)x－4)x＋3)x－5跟踪训练2．利用秦九韶算法求多项式f(x)＝3x6＋12x5＋8x4－3.5x3＋7.2x2＋5x－13当x＝6时的值，写出详细步骤．解：f(x)＝(((((3x＋12)x＋8)x－3.5)x＋7.2)x＋5)x－13.v0＝3，v1＝v0×6＋12＝30，v2＝v1×6＋8＝188，v3＝v2×6－3.5＝1124.5，v4＝v3×6＋7.2＝6754.2，v5＝v4×6＋5＝40530.2，v6＝v5×6－13＝243168.2.f(6)＝243168.2.跟踪训练题型三进位制

(1)把二进制数101101(2)化为十进制数．(2)把十进制数458转化为四进制数．例3题型三进位制例3【解】

(1)101101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝32＋8＋4＋1＝45，所以二进制数101101(2)转化为十进制数为45.(2)

458＝13022(4)．【解】(1)101101(2)＝1×25＋0×24＋1×【名师点评】

(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式,再按照十进制的运算规则计算出结果．(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余．【名师点评】(1)将k进制转化为十进制的方法是：先将这个k互动探究3．将本例(1)中的二进制数101101(2)转化为三进制数．解：101101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝45，∴45＝1200(3)．互动探究1．求两个正数的最大公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快．2．两种非十进制的不同进制之间相互转化时，可以把十进制作为转化的中间桥梁．方法感悟1．求两个正数的最大公约数，当两数差别较大时，用辗转相除法，利用秦九韶算法求多项式f(x)＝x6－5x5＋6x4＋x2＋3x＋2，当x＝－2时的值为(

)A．320

B．－160C．－320

D．300【常见错误】

(1)考虑x＝－2而认为多项式的值为负值．(2)易忽略多项式中系数为0的项，致使多项式改写不正确．精彩推荐典例展示易错警示利用秦九韶算法求值的易错点例4利用秦九韶算法求多项式f(x)【解析】将多项式变式为f(x)＝(((((x－5)x＋6)x＋0)x＋1)x＋3)x＋2，v0＝1，v1＝－2＋(－5)＝－7，v2＝－7×(－2)＋6＝20，v3＝20×(－2)＋0＝－40，v4＝－40×(－2)＋1＝81，v5＝81×(－2)＋3＝－159，v6＝－159×(－2)＋2＝320.【答案】

A【失误防范】

(1)解题时注意多项式变形后有几次乘法和几次加法．(2)要注意所给多项式的项数，特别是系数为0的项．【解析】将多项式变式为f(x)＝(((((x－5)x＋6)跟踪训练4．已知多项式f(x)＝3x5＋8x4－3x3＋5x2＋12x－6，则f(2)＝________.解析：根据秦九韶算法，把多项式改写成如下形式：f(x)＝((((3x＋8)x－3)x＋5)x＋12)x－6.按照从内到外的顺序，依次计算一次多项式当x＝2时的值．跟踪训练v0＝3，v1＝3×2＋8＝14，v2＝14×2－3＝25，v3＝25×2＋5＝55，v4＝55×2＋12＝122，v5＝122×2－6＝238，所以当x＝2时，多项式的值为238.答案：238v0＝3，知能演练轻松闯关知能演练轻松闯关本部分内容讲解结束按ESC键退出全屏播放本部分内容讲解结束按ESC键退出全屏播放1．3算法案例第一章算法初步1．3算法案例第一章算法初步学习导航学习导航新知初探思维启动1．辗转相除法所谓辗转相除法，就是对于任意给定的两个正整数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个数的最大公约数．新知初探思维启动1．辗转相除法想一想1.辗转相除法中的关键步骤可用哪种逻辑结构来实现？提示：辗转相除法中带余数除法是一个反复执行、直到余数等于0停止的步骤，可用循环结构来实现．想一想2．更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的任意一种求两个正整数最大公约数的方法．其基本过程是：对于给定的两个正整数,判断它们是否都是偶数．若是,用2约简；若不是，则用____________________

，接着把所得的____

与__________

比较，并以大数减小数．继续这个操作，直到所得的数______

为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．较大数减去较小的数差较小的数相等2．更相减损术较大数减去较小的数差较小的数相等想一想2.实际应用更相减损术时要做的第一步工作是什么？提示：先判断a，b是否全为偶数，若是，则先都除以2再进行．想一想3．秦九韶算法(1)算法原理它是通过一次式的反复计算，逐步得出高次多项式的值的一种求多项式函数值的算法．设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＝…3．秦九韶算法首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1，然后由内向外逐层计算一次多项式的值．这样，求n次多项式f(x)的值就转化为求n个一次多项式的值．首先计算最内层括号内一次多项式的值，即v1＝anx＋an－1想一想3.怎样设计秦九韶算法，程序框图及程序呢？提示：算法步骤如下：第一步，输入多项式次数n、最高次项的系数an和x的值．第二步，将v的值初始化为an，将i的值初始化为n－1.第三步，输入i次项的系数ai.第四步，v＝vx＋ai，i＝i－1.第五步，判断i是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v.想一想13-算法案例-课件解读4．进位制(1)进位制的概述进位制是人们为了计数和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制；等等．也就是说，“___________”就是几进制，几进制的基数(大于1的整数)就是几．一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注基数(k)，以示区别．例如，270(8)表示270是一个八进制数．十进制数一般不标注基数．满几进一4．进位制满几进一(2)常见的进位制①二进制：a：只使用0和1两个数字；b：满二进一，如1＋1＝10.②八进制：a：使用0,1,2,3,4,5,6,7八个不同的数字；b：满八进一，如7＋1＝10.③十六进制：a：使用0,1,2,3,4,5,6,7,8,9，A，B，C，D，E，F这十六个不同的数码，其中A，B，C，D，E，F分别代表十进制中的10,11,12,13,14,15；b：满十六进一，如F＋1＝2＋E＝10.(2)常见的进位制(3)不同进位制数之间的转化①k进制数转化为十进制数把k进制数转化为十进制数，写成不同位上数字与基数幂的乘积之和即可(简称幂积求和)，即anan－1…a1a0(k)＝an×kn＋an－1×kn－1＋…＋a1×k＋a0.例如，将二进制数11001(2)化为十进制数：11001(2)＝1×24＋1×23＋0×22＋0×21＋1×20＝16＋8＋1＝25.(3)不同进位制数之间的转化13-算法案例-课件解读典题例证技法归纳题型探究例1典题例证技法归纳题型探究例1【解】辗转相除法：80＝36×2＋8,36＝8×4＋4,8＝4×2＋0.故80和36的最大公约数是4.用更相减损术检验：80－36＝44，44－36＝8，36－8＝28，28－8＝20，20－8＝12，12－8＝4，8－4＝4，∴80和36的最大公约数是4.【名师点评】

解决此类问题要弄清它们的理论依据，根据理论依据一步一步计算出80和36的最大公约数．【解】辗转相除法：跟踪训练1．求108与45的最大公约数．解：法一：由辗转相除法，得108＝45×2＋18，45＝18×2＋9，18＝9×2，故108与45的最大公约数是9.跟踪训练法二：由更相减损术，得108－45＝63，63－45＝18，45－18＝27，27－18＝9，18－9＝9，故108与45的最大公约数是9.法二：由更相减损术，得例2题型二秦九韶算法及应用

(2013·福州高一检测)用秦九韶算法写出当x＝3时f(x)＝2x5－4x3＋3x2－5x＋1的值．例2题型二秦九韶算法及应用【解】

∵f(x)＝((((2x－0)x－4)x＋3)x－5)x＋1，v0＝2，v1＝2×3＋0＝6，v2＝6×3－4＝14，v3＝14×3＋3＝45，v4＝45×3－5＝130，v5＝130×3＋1＝391，所以f(3)＝391.【名师点评】利用秦九韶算法计算多项式值的关键是能准确地将多项式改写,然后由内向外逐次计算.由于后项计算用到前项的结果,故应认真、细心，确保每项计算结果的准确性．【解】∵f(x)＝((((2x－0)x－4)x＋3)x－5跟踪训练2．利用秦九韶算法求多项式f(x)＝3x6＋12x5＋8x4－3.5x3＋7.2x2＋5x－13当x＝6时的值，写出详细步骤．解：f(x)＝(((((3x＋12)x＋8)x－3.5)x＋7.2)x＋5)x－13.v0＝3，v1＝v0×6＋12＝30，v2＝v1×6＋8＝188，v3＝v2×6－3.5＝1124.5，v4＝v3×6＋7.2＝6754.2，v5＝v4×6＋5＝40530.2，v6＝v5×6－13＝243168.2.f(6)＝243168.2.跟踪训练题型三进位制

(1)把二进制数101101(2)化为十进制数．(2)把十进制数458转化为四进制数．例3题型三进位制例3【解】

(1)101101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝32＋8＋4＋1＝45，所以二进制数101101(2)转化为十进制数为45.(2)

458＝13022(4)．【解】(1)101101(2)＝1×25＋0×24＋1×【名师点评】

(1)将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式,再按照十进制的运算规则计算出结果．(2)十进制转化为k进制，采用除k取余法，也就是除基数，倒取余．【名师点评】(1)将k进制转化为十进制的方法是：先将这个k互动探究3．将本例(1)中的二进制数101101(2)转化为三进制数．解：101101(2)＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＝45，∴45＝1200(3)．互动探究1．求两个正数的最大公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快．2．两种非十进制的不同进制之间相互转化时，可以把十进制作为转化的中间桥梁．方法感悟1．求两个正数的最大公约数，当两数差别较大时，用辗转相除法，利用秦九韶算法求多项式f(x)＝x6－5x5＋6