nbhkdz.com冰点文库

1.3算法案例 课件(人教A必修3)


1.3

算法案例

【课标要求】 1.理解辗转相除法与更相减损术的含义,了解其执行过程. 2.理解秦九韶算法的计算过程,并了解它提高计算效率的实质. 3.理解进位制的概念,能进行不同进位制间的转化. 4.了解进位制的程序框图和程序. 【核心扫描】 1.三种算法的原理及应用.(重难点) 2.三种算法的框图表示及程序.(难点) 3.不同进位制

之间的相互转化.(重点) 4.秦九韶算法中多项式的改写.(易错点)

自学导引
辗转相除法 1. (1)辗转相除法,又叫欧几里得算法,是一种求两个正整数 最大公约数 的___________的古老而有效的算法. (2)辗转相除法的算法步骤 两个正整数m,n 第一步,给定________________. 第二步,计算___________________. m除以n所得的余数r m=n,n=r 第三步, ____________. 第四步,若r=0,则m、n的最大公约数等于___;否则, m 第二步 返回________.

更相减损术 2. 第一步,任意给定两个正整数,判断它们是否都是_____.若 偶数 是,用_______;若不是,执行_______ . 2约简 第二步 较大 较小 第二步,以_____的数减去_____的数,接着把所得的差与 _____的数比较,并以大数减小数,继续这个操作,直到所得 较小 相等 的数_____为止,则这个数(等数)或这个数与约简的数的乘积 就是所求的最大公约数. 任意给定两个正整数,用辗转相除法和更相减损术是否 都可以求它们的最大公约数? 提示 是.更相减损术与辗转相除法都能在有限步内结束, 故均可以用来求两个正整数的最大公约数.

秦九韶算法 3. 把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0改写成如 下形式: (…((anx+an-1)x+an-2)x+…+a1)x+a0, 最内层括号内 求多项式的值时,首先计算_____________一次多项式的值, anx+an-1 即v1=__________,然后由内向外逐层计算一次多项式的值, 即 v1x+an-2 v2=__________, v2x+an-3 v3=__________, … vn-1x+a0 vn=__________. n个一次多项式 这样,求n次多项式f(x)的值就转化为求________________的 值.

进位制 4. 计数 运算方便 进位制是人们为了_____和_________而约定的记数系统,
“满k进一”就是k进制,k进制的基数是k. 把十进制转化为k进制数时,通常用除k取余法. 不同进制间的数不能比较大小,对吗? 提示 不对.不同的进位制是人们为了计数和运算方便而 约定的记数系统,不同进位制的数照样可比较大小,不过 一般要转化到十进制下比较大小更方便一些.

名师点睛
1.辗转相除法与更相减损术的区别和联系 名称 辗转相除法 更相减损术

区别

①以减法为主. ①以除法为主. ②两个整数的差值较大 ②两个整数差值较大 时,运算次数较多. 时运算次数较少. ③相减,两数相等得结 ③相除余数为零时得 果. 结果 ④相减前要做是否都是 偶数的判断 ①都是求两个正整数的最大公约数的方法. ②二者的实质都是递推的过程. ③二者都要用循环结构来实现

联系

2. 秦九韶算法 (1)特点:通过一次式的反复计算,逐步得出高次多项式的 值,对于一个n次多项式,只需做n次乘法和n次加法即 可. (2)算法步骤: 设Pn(x)=anxn+an-1xn-1+…+a1x+a0,将其改写为 Pn(x)=(anxn-1+an-1xn-2+…+a1)x+a0 =((anxn-2+an-1xn-3+…+a2)x+a1)x+a0 =(…((anx+an-1)x+an-2)x+…+a1)x+a0. 第一步:计算最内层anx+an-1的值,将anx+an-1的值赋 给一个变量v1(为方便将an赋予变量v0); 第二步:计算(anx+an-1)x+an-2的值,可以改写为v1x+ an-2,将v1x+an-2的值赋给一个变量v2;

依次类推,即每一步的计算之后都赋予一个新值vk,即从 最内层的括号到最外层. 括号的值依次赋予变量v1,v2,…,vk,…,vn,第n步所 求值vn=vn-1x+a0即为所求多项式的值. (3)秦九韶算法有以下几个优点: ①大大减少了乘法的次数,使计算量减小.在计算机上做 一次乘法所需要的时间是做加法、减法的几倍到十几倍, 减少做乘法的次数也就加快了计算的速度; ②规律性强,便于利用循环语句来实现算法; ③避免了对自变量x单独做幂的计算,每次都是计算一个 一次多项式的值,从而可以提高计算的精度.

关于进位制应注意的问题 3. (1)十进制的原理是满十进一.一个十进制正整数N可以写 成an×10n+an-1×10n-1+…+a1×101+a0×100的形式, 其中an,an-1,…,a1,a0都是0至9中的数字,且an≠0.例 如365=3×102+6×10+5. (2)一般地,k进制数的原理是满k进一,k进制数一般在右 下角处标注(k),以示区别.例如270(8)表示270是一个8进 制数.但十进制一般省略不写. (3)在k进制中,有: ①有k个不同的数字符号,即0,1,2,3,…,(k-1); ②“逢k进一”,即每位数计满k后向高位进一. 一个k进位制的正整数就是各位数码与k的方幂的乘积的 和,其中幂指数等于相应数码所在位数(从右往左数)减1. 例如230 451(k)=2×k5+3×k4+0×k3+4×k2+5×k+1.

题型一

求两个正整数的最大公约数

【例1】分别用辗转相除法和更相减损术求261和319的最大公 约数. [思路探索] 使用辗转相除法可依据m=nq+r,反复执行直 到余数为0;更相减损术则是根据m-n=r,反复执行, 直到n=r为止. 解 法一 (辗转相除法) 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.

规律方法 (1)利用辗转相除法求给定的两个数的最大公 约数,即利用带余除法,用数对中较大的数除以较小的 数,若余数不为零,则将余数和较小的数构成新的数对, 再利用带余除法,直到大数被小数除尽,则这时的较小数 就是原来两个数的最大公约数. (2)利用更相减损术求两个正整数的最大公约数的一般步 骤是:首先判断两个正整数是否都是偶数.若是,用2约 简.也可以不除以2,直接求最大公约数,这样不影响最 后结果.

【变式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.

题型二

进位制之间的转化

【例2】将七进制数235(7)转化为八进制. [思路探索] 七进制 ―→ 十进制 ―→ 八进制 解 235(7)=2×72+3×71+5=124,利用除8 取余法(如图所示),所以124=174(8). 所以235(7)转化为八进制数为174(8).
规律方法 对于非十进制数之间的互化,通常是把这个数 先转化为十进制数,然后再利用除k取余法,把十进制数 转化为k进制数.而在使用除k取余法时要注意以下几点: (1)必须除到所得的商是0为止;(2)各步所得的余数必须从 下到上排列;(3)切记在所求数的右下角标明基数.

【变式2】把下列各数转换成十进制数. (1)101 101(2);(2)2 102(3);(3)4 301(6). 解 (1)101 101(2)=1×25+0×24+1×23+1×22+0×2+1 =45. (2)2 102(3)=2×33+1×32+2=65. (3)4 301(6)=4×63+3×62+1=973.

题型三

秦九韶算法在多项式中的应用

【例3】用秦九韶算法求f(x)=3x5+8x4-3x3+5x2+12x-6,当 x=2的值. 改写成一次 审题指导 多项式求值 ―——―→ 秦九韶算法 多项式的形式
由内 ――→ 结果 向外

[规范解答] 根据秦九韶算法,把多项式改写成如下形式: f(x)=((((3x+8)x-3)x+5)x+12)x-6,按照从内到外的顺 序,依次计算一次多项式当x=2时的值. (2分) v0=3, v1=v0×2+8=3×2+8=14, (4分) v2=v1×2-3=14×2-3=25, (6分) v3=v2×2+5=25×2+5=55, (8分) v4=v3×2+12=55×2+12=122, v5=v4×2-6=122×2-6=238, (10分) 所以当x=2时,多项式的值为238. (12分)

【题后反思】 (1)先将多项式写成一次多项式的形式,然 后运算时从里到外,一步一步地做乘法和加法即可.这样 比直接将x=2代入原式大大减少了计算量.若用计算机计 算,则可提高运算效率. (2)注意:当多项式中n次项不存在时,可将第n次项看作 0·n. x

【变式3】用秦九韶算法计算f(x)=6x5-4x4+x3-2x2-9x,需 要加法(或减法)与乘法运算的次数分别为 ( ). A.5,4 B.5,5 C.4,4 D.4,5 解析 n次多项式需进行n次乘法;若各项均不为零,则需 进行n次加法,缺一项就减少一次加法运算.f(x)中无常数 项,故加法次数要减少一次,为5-1=4.故选D. 答案 D

误区警示

对秦九韶算法中的运算次数理解错误

【示例】已知f(x)=x5+2x4+3x3+4x2+5x+6,用秦九韶算法 求这个多项式当x=2时的值时,做了几次乘法?几次加 法? [错解] 根据秦九韶算法,把多项式改写成如下形式f(x)= ((((x+2)x+3)x+4)x+5)x+6. 按照从内到外的顺序,依次计算一次多项式当x=2时的 值:v1=2+2=4;v2=2v1+3=11;v3=2v2+4=26;v4= 2v3+5=57;v5=2v4+6=120. 显然,在v1中未做乘法,只做了1次加法;在v2,v3,v4, v5中各做了1次加法,1次乘法.因此,共做了4次乘法,5 次加法.

在v1中虽然“v1=2+2=4”,而计算机还是做了1次 乘法“v1=2×1+2=4”.因为用秦九韶算法计算多项式f(x)= anxn+an-1xn-1+…+a1x+a0当x=x0时的值时,首先将多项 式改写成f(x)=(…(anx+an-1)x+…+a1)x+a0,然后再计算v1 =anx+an-1,v2=v1x+an-2,v3=v2x+an-3,…,vn=vn-1x +a0.无论an是不是1,这次的乘法都是要进行的. [正解] 由上分析可知,共做了5次乘法,5次加法.

?n+1?n 直接法乘法运算的次数最多可达 , 2 加法最多 n 次,秦九韶算法通过转化把乘法运算的次 数减少到最多 n 次,加法最多 n 次.


高中数学必修三1.3算法案例

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...高中数学必修三1.3算法案例_高一数学_数学_高中教育...4、写出从键盘任意输入两个正整数 a,b,输出这两...

人教版高中数学必修三《1.3算法案例(教、学案)

人教版数学必修三课件:高... 20页 2财富值 数学:1[1].3.1《算法案例......a n ? (k ? 1,2,? ? ?n) ? ?vk ? vk ?1 x ? an?k 构来实现...

高中数学必修三1.3算法案例练习

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...高中数学必修三1.3算法案例练习_数学_高中教育_教育...( A. 1 B. 2 C. 3 D. 4 4.运行下面的...

2015高中数学 1.3算法案例讲解 新人教A版必修3

2015高中数学 1.3算法案例讲解 新人教A必修3_数学_高中教育_教育专区。2015 高中数学 1.3 算法案例讲解 新人教 A必修 3 在初中,我们已经学过求最大公约...

《1.3算法案例(1)》教学案-公开课-优质课(人教A版必修三精品)

1.3算法案例(1)》教学案-公开课-优质课(人教A必修三精品)_高一数学_数学_高中教育_教育专区。《1.3算法案例(1) 》教学案 (1)教学目标 (a)知识与...

2015高中数学 1.3算法案例练习 新人教A版必修3

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 高中...2015高中数学 1.3算法案例练习 新人教A必修3_数学_高中教育_教育专区。1. ...

人教A版必修3 1.3 算法案例训练题及答案

人教A必修3 1.3 算法案例训练题及答案_高一数学_数学_高中教育_教育专区。人教 A必修 3 1.3 算法案例训练题及答案一、选择题(共 10 小题;共 40 分...

必修三1.3.2算法案例

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...必修 3 §1.3.1 算法案例--辗转相除法、更相...( A.3 B.4 C.5 D .6 2. 三个数 175,100...

新人教A版必修3 高中数学1.3.1-1.3.2算法案例教案

人教A必修3 高中数学1.3.1-1.3.2算法案例教案_数学_高中教育_教育专区。高中数学 1.3.1-1.3.2 算法案例教案 文 新人教 A必修 3 (1)教学目标...