1、1.3 算法案例算法案例 学案学案 新知自解新知自解 1.掌握辗转相除法与更相减损术的原理及算法分析掌握辗转相除法与更相减损术的原理及算法分析， 并能熟练运用这两种算并能熟练运用这两种算 法求正整数的最大公约数法求正整数的最大公约数. 2.理解秦九韶算法的原理及算法分析理解秦九韶算法的原理及算法分析，并能熟练地用此法求多项式的值并能熟练地用此法求多项式的值. 3.了解进位制原理了解进位制原理. 辗转相除法辗转相除法 1.辗转相除法辗转相除法，又叫欧几里得算法又叫欧几里得算法，是一种求两个正整数的是一种求两个正整数的_ 的古老而有效的算法的古老而有效的算法. 2.辗转相除法的算法步骤辗转相除法的
2、算法步骤 第一步第一步，给定给定_. 第二步第二步，计算计算_. 第三步第三步，_. 第四步第四步，若若 r0，则则 m，n 的最大公约数等于的最大公约数等于_；否则返回；否则返回_. 最大公约数最大公约数 两个正整数两个正整数m、n m除以除以n所得余数所得余数r mn，nr m 第二步第二步 更相减损术更相减损术 1.更相减损术是我国古代数学专著九章算术中介绍的一种求更相减损术是我国古代数学专著九章算术中介绍的一种求 _的算法的算法. 2.其基本过程是：其基本过程是： 第一步第一步，任意给定两个正整数任意给定两个正整数，判断它们是否都是判断它们是否都是_.若是若是， _；若不是；若不是，执
3、行执行_. 第二步第二步， 以以_的数减去的数减去_的数的数， 接着把所得的差与接着把所得的差与_的数比较的数比较， 并以大数减去小并以大数减去小数，继续这个操作，直到所得的数数，继续这个操作，直到所得的数_为止为止，则这个数则这个数(等数等数) 或这个数与约简的数的乘积就是所求的最大公约数或这个数与约简的数的乘积就是所求的最大公约数. 两个正整数最大公约数两个正整数最大公约数 偶数偶数 用用2约简约简 第二步第二步 较大较大 较小较小 较小较小 相等相等 秦九秦九韶算法韶算法 功能功能 它是一种用于计算它是一种用于计算_的值的方法的值的方法 改写改写后的后的形式形式 f(x)anxnan 1
4、xn 1 a1xa0 _ (anxn 2 an 1xn 3 a2)xa1)xa0 _ 一元一元n次多项式次多项式 (anxn 1 an 1xn 2 a1)xa0 (anxan 1)x an 2)x a1)xa0 计算计算方法方法 从括号最内层开始从括号最内层开始，由内向外逐层计算由内向外逐层计算 v1anxan 1， v2v1xan 2， v3_， vn_， 这样这样，求求 n 次多项式次多项式 f(x)的值就转化为求的值就转化为求_ 的值的值 v2xan 3 vn 1x a0 n个一次多项式个一次多项式 进位制进位制 进位制是人们为了进位制是人们为了_和和_而约定的记数系统而约定的记数系统，
5、“满满 k 进一进一”就就 是是_，k 进制的基数是进制的基数是_. 把十进制数化为把十进制数化为 k 进制数时进制数时，通常用通常用_. 计数计数 运算方便运算方便 k进制进制 k 除除k取余法取余法 化解疑难化解疑难 (1)辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较 两种方法两种方法 辗转相除法辗转相除法 更相减损术更相减损术 计算法则计算法则 除法除法 减法减法 终止条件终止条件 余数为余数为 0 减数与差相等减数与差相等 最大公约最大公约 数的选取数的选取 最后一步中的除数最后一步中的除数 最后一步中的减数最后一步中的减数 计算次数计算次数 步骤较少步骤较少，运运算复杂算
6、复杂 步骤较多步骤较多，运算简单运算简单 相同点相同点 同为求两个正整数最大公约数的方法同为求两个正整数最大公约数的方法，都是递归过程都是递归过程 (2)秦九韶算法的步骤秦九韶算法的步骤 1.(2015 遵义高一期中遵义高一期中)用用“辗转相除法辗转相除法”求得求得 459 和和 357 的最大公约数是的最大公约数是 ( ) A.3 B.9 C.17 D.51 解析：解析： 利用辗转相除法利用辗转相除法，得得 4593571102， 357102351， 1025120， 所以所以 459 和和 357 的最大公约数是的最大公约数是 51. 答案：答案： D 2.用秦九韶算法求多项式用秦九韶算
7、法求多项式 f(x)12xx23x32x4在在 x1 时时的值的值，v2 的结果是的结果是( ) A.4 B.1 C.5 D.6 解析：解析： n4，a42，a33，a21，a12，a01，由秦九韶算法的递由秦九韶算法的递 推关系式得推关系式得 v02，v1v0xa35，v2v1xa26. 答案：答案： D 解析：解析： 先把先把 1 101(2)化成十进制数化成十进制数，1 101(2)123122021120 13，再把再把 13 化成五进制数化成五进制数. 1323(5)，即即 1 101(2)23(5). 3.二进制数二进制数1 101(2)化成五进制数为化成五进制数为 . 答案：答案
8、： 23(5) 教案教案 课堂探究课堂探究 最大公约数的求法最大公约数的求法多维探究型多维探究型 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求 261 和和 319 的最大公约数的最大公约数. 解析：解析： 解法一：解法一：(辗转相除法辗转相除法) 3192611(余余 58)， 261584(余余 29)， 58292(余余 0)，所以所以 319 与与 261 的最大公约数为的最大公约数为 29. 解法二：解法二：(更相减损术更相减损术) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以所以 3
9、19 与与 261 的最大公约数是的最大公约数是 29. 归纳升华归纳升华 (1)辗转相除法是当大数被小数除尽时辗转相除法是当大数被小数除尽时，结束除法运算结束除法运算，较小的数就是最大较小的数就是最大 公约数； 更相减损术是当大数减去小数的差等于小数时停止减法公约数； 更相减损术是当大数减去小数的差等于小数时停止减法， 较小的数就是较小的数就是 最大公约数最大公约数. (2)求三个数的最大公约数求三个数的最大公约数，可以先求两个数的最大公约数可以先求两个数的最大公约数，然后求第三然后求第三个个 数与前两个数的最大公约数的最大公约数数与前两个数的最大公约数的最大公约数. 1.1 443 与与
10、999 的最大公约数是的最大公约数是( ) A.99 B.11 C.111 D.999 解析：解析： 用更相减损术用更相减损术， 1 443999444， 999444555， 555444111， 444111333，333111222，222111111，所以所以 111 是最大是最大公约数公约数，故选，故选 C. 答案：答案： C 秦九韶算法及其应用秦九韶算法及其应用多维探究型多维探究型 用秦九韶算法求多项式用秦九韶算法求多项式 f(x)1x0.5x20.166 67x30.041 67x4 0.008 33x5在在 x0.2 时的值时的值. 解析：解析： f(x)1x0.5x20.16
11、6 67x30.041 67x40.008 33x5 (0.008 33x0.041 67)x0.166 67)x0.5)x1)x1， 而而 x0.2，所以有所以有 0a50.008 33，10xa40.04， 21xa30.158 67，32xa20.468 27， 43xa10.906 35，54xa00.818 73， 即即 f(0.2)0.818 73. 归纳升华归纳升华 利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写， 然后由然后由 内向外逐次计算内向外逐次计算，由于后项计算需用到前项的结果由于后项计算需用到前项的
12、结果，故应认真、细心故应认真、细心，确保中间确保中间 结果的准确性结果的准确性. 2.用秦九韶算法计算多项式用秦九韶算法计算多项式 f(x)6x55x44x33x22x1， 当当 x5 的值的值 时时，乘法运算和加法运算的次数分别为乘法运算和加法运算的次数分别为( ) A.10，5 B.5，5 C.5，6 D.15，6 解析：解析： f(x)6x55x44x33x22x1 (6x5)x4)x3)x2)x1， 故当故当 x5 时有时有 5 次乘法和次乘法和 5 次加法运算次加法运算，选选 B. 答案：答案： B 进位制之间的转化进位制之间的转化多维探究型多维探究型 (1)把十进制数把十进制数 8
13、9 化为三进制数化为三进制数. (2)把五进制数把五进制数 3241(5)转化为八进制数转化为八进制数. 解析：解析： (1)具体的计算方法如下：具体的计算方法如下： 893292；29392；9330；3310；1301. 所以所以 8910 022(3). 或用下面的除法算法表示或用下面的除法算法表示. 把上式中各步所得余数从下向上排列把上式中各步所得余数从下向上排列，得得 8910 022(3). (2)3241(5)353252451150446， 4468556，55867，6806. 446676(8)， 故故 3241(5)676(8). 归纳升华归纳升华 (1)将十进制数化成将
14、十进制数化成 k 进制数的方法是用进制数的方法是用“除除 k 取余法取余法”，用用 k 连续去除十连续去除十 进制数或所得的商进制数或所得的商，直到商为零直到商为零为止为止，然后将各步所得的余数倒序写出然后将各步所得的余数倒序写出，即为相即为相 应的应的 k 进制数进制数. (2)非十进制数直接利非十进制数直接利用公式用公式anan 1a1a0(k)anknan1kn 1 a1ka0就就 可以转化为十进制数；可以转化为十进制数； k 进制数和进制数和 m 进制数之间需要用十进制数来转化进制数之间需要用十进制数来转化， 即先把即先把 k 进制数转化为十进制数进制数转化为十进制数，再利用除再利用除 m 取余法转化为取余法转化为 m 进制数进制数. 3.把把 88 化为五进制数是化为五进制数是( ) A.323(5) B.324(5) C.233(5) D.332(5) 解析：解析： 885173，17532，3503，所以所以 88 化为五进制化为五进制 数是数是 323(5). 答案：答案： A 谢谢观看！谢谢观看！
