当前位置:首页 >> 数学 >>

高中数学 1.3 算法案例配套课件 新人教A版必修3_图文

此ppt下载后可自行编辑 高中数学课件 1.3 算法案例 【学习目标】 1.理解辗转相除法与更相减损术求最大公约数的方法. 2.理解秦九韶算法中求多项式的值的步骤原理. 3.能利用除 k 取余法把十进制数化为 k 进制数. 1.辗转相除法的算法步骤 第一步,给定两个正整数 m,n(m>n). m 除以________ n 所得的______数 余 r. 第二步,计算________ 第三步,m=n,n=r. n 第四步,若 r=0,则 m,n 的最大公约数等于______;否 则,返回第二步. 2.更相减损术的算法步骤 第一步,任意给定两个正整数,判断它们是否都是偶数.若 是用 2 约简;若不是,执行第二步. 第二步,以较大的数减去较小的数,接着把所得的差与 较小的数 ________比较,并以大数减小数.继续这个操作,直到所得的数 相等 为止,则这个数(等数)或这个数与约简的数的乘积就 ________ 是所求的最大公约数. 3.秦九韶算法 把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0改写 成如下形式: f(x)=anxn+an-1xn-1+…+a1x+a0 (anxn-1+an-1xn-2+…+a1)x+a0 =_____________________________ =((anxn-2+an-1xn-3+…+a2)x+a1)x+a0 =… =_____________________________________. (…((a x+a )x+a )x+…+a )x+a n n-1 n-2 1 0 求多项式的值时,首先计算最内层括号内的一次多项式的 值,即v1=anx+an-1,然后由内向外逐层计算一次多项式的值, 即: v1=anx+an-1, v1x+an-2 , v2=____________ v3=v2x+an-3, … vn=____________ v x+ a , n-1 0 n 个一次多项 这样,求 n 次多项式 f(x)的值就转化为求______ 式的值. 4.进位制 (1)k进制数anan-1…a1a0(k)转化为十进制数为 n+a n-1+…+a k+a a k k n n - 1 1 0 _____________________________________. 除 k 取余法 (2)把十进制数化为 k 进制数用“____________”,即把所给 k ,得到商数和余数,再用商数除以 k, 的十进制数除以________ 得到商数和余数,直到商数为________ 0 ,把上面各步所得的 余数 从右到左排列,即得到 k 进制数. ________ 【问题探究】 用秦九韶算法求多项式的值有什么优点? 答案:减少了做乘法运算的次数,优化了求多项式的值的 算法. 题型 1 最大公约数的求法 【例 1】 用辗转相除法求下面两数的最大公约数,并用更 相减损术检验你的结果: (1)80,36; (2)294,84. 思维突破:辗转相除法的结束条件是余数为 0,更相减损 术的结束条件是差与减数相等. 解:(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. (2)294=84×3+42,84=42×2, 即 294 与 84 的最大公约数是 42. 验证:∵294 与 84 都是偶数可同时除以2,即取147 与42 的最大公约数后再乘 2. 147-42=105,105-42=63, 63-42=21,42-21=21, ∴294 与 84 的最大公约数为 21×2=42. 辗转相除法求最大公约数的步骤较少,而更相减 损术运算简易,因此解题时要灵活运用. 【变式与拓展】 1.试用算法程序表示用辗转相除法求 144 与 60 的最大公约 数的算法. 解:程序如下: m=144 n=60 DO r=m MOD n m= n n= r LOOP UNTIL PRINT m END r= 0 题型 2 秦九韶算法的应用 【例 2】 当 x=3 时,求多项式 f(x)=x5+x3+x2+x+1 的 值. 解:根据秦九韶算法,把多项式改写成如下形式: f(x)=x5+0·x4+x3+x2+x+1 =(((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. 所以当 x=3 时,多项式的值为 283. 当多项式函数的中间出现空项时,应先补上系 数为 0 的相应项.解题时关键是能正确地改写多项式,然后由内 向外逐项计算.由于后项计算用到前项的结果,故要认真确保每 一项计算的准确性. 【变式与拓展】 2.利用秦九韶算法计算多项式 f(x)=11-5x+3x2+7x3 在 x =23 的值时,不会用到下列哪个值( D ) A.161 B.3772 C.86 641 D.85 169 解析:f(x)=11-5x+3x2+7x3=[(7x+3)x-5]x+11. 所以当x=23时,v0=7; v1=7×23+3=161+3=164; v2=164×23-5=3772-5=3767; v3=3767×23+11=86 641+11=86 652. 题型 3 进制数之间的转化 【例 3】 (1)将 101 111 011(2)转化为十进制数; (2)将 1231(5)转化为七进制数. 思维突破:k 进制数 anan-1…a2a1a0(k)(0≤ai<k)转化为