课题:§1.3算法案例 第1课时辗转相除法与更相减损术、秦九韶算法 教学目标: 根据课标要求:在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框 图和程序三种不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过 程,体验算法在解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展 有条理地思考与数学表达能力。制定以下三维目标 1、知识与技能 理解算法案例的算法步骤和程序框图. 2、过程与方法: 引导学生得出自己设计的算法程序 、情感态度与价值观: 体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 二、重点与难点: 重点:引导学生得出自己设计的算法步骤、程序框图和算法程序. 解决策略:通过分析解决具体问题的算法步骤来引导学生写出算法,根据算法画出程序框 图,再根据框图用规范的语言写出程序 难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力 解决策略:让学生能严谨地按照自己是程序框图写出程序。 、学法与教学用具: 1、学法:直观感知、操作确认 2、教学用具:多媒体 四、教学过程 (一)引入课题 大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球 东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的在小 学,我们学过求两个正整数的最大公约数的方法:先用两个数公有的质因数连续去除, 直除到所得的商是互质数为止,然后把所有的除数连乘起来.当两个数公有的质因数较大
课题：§1．3 算法案例 第 1 课时 辗转相除法与更相减损术、秦九韶算法 一、教学目标： 根据课标要求：在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框 图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过 程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展 有条理地思考与数学表达能力。制定以下三维目标： 1、知识与技能 理解算法案例的算法步骤和程序框图. 2、过程与方法： 引导学生得出自己设计的算法程序. 3、情感态度与价值观： 体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力. 二、重点与难点： 重点：引导学生得出自己设计的算法步骤、程序框图和算法程序. 解决策略：通过分析解决具体问题的算法步骤来引导学生写出算法，根据算法画出程序框 图，再根据框图用规范的语言写出程序。 难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力. 解决策略：让学生能严谨地按照自己是程序框图写出程序。 三、学法与教学用具： 1、学法：直观感知、操作确认。 2、教学用具：多媒体。 四、教学过程 （一）引入课题 大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球， 东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小 学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一 直除到所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大
时(如8251与6105),使用上述方法求最大公约数就比较困难.下面我们介绍两种不 同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异 (二)研探新知 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大公约数? (3)怎样用辗转相除法求最大公约数? (4)怎样用更相减损术求最大公约数? 讨论结果 (1)短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得的 商是两个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直 到找到公约数立即中断列举,得到的公约数便是最大公约数 (3)辗转相除法 辗转相除法求两个数的最大公约数,其算法步骤可以描述如下: 第一步,给定两个正整数m,n 第二步,求余数r:计算m除以n,将所得余数存放到变量r中 第三步,更新被除数和余数:m=n,n=r. 第四步,判断余数r是否为0.若余数为0,则输出结果:否则转向第二步继续循环执行. 如此循环,直到得到结果为止.这种算法是由欧几里得在公元前300年左右首先提出的, 因而又叫欧几里得算法 (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术.《九章算术》是中国古代 的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之, 不可半者,副置分母、子之数,以少减多,更相减损,求其等也以等数约之.”翻译为现 代语言如下: 第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简:若不是,执行 第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数, 继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就 是所求的最大公约数
时（如 8 251 与 6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不 同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异. （二）研探新知 （1）怎样用短除法求最大公约数？ （2）怎样用穷举法（也叫枚举法）求最大公约数？ （3）怎样用辗转相除法求最大公约数？ （4）怎样用更相减损术求最大公约数？ 讨论结果： （1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的 商是两个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直 到找到公约数立即中断列举，得到的公约数便是最大公约数. （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数 m，n. 第二步，求余数 r：计算 m 除以 n，将所得余数存放到变量 r 中. 第三步，更新被除数和余数：m=n，n=r. 第四步，判断余数 r 是否为 0.若余数为 0，则输出结果；否则转向第二步继续循环执行. 如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前 300 年左右首先提出的， 因而又叫欧几里得算法. （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 《九章算术》是中国古代 的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之， 不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现 代语言如下： 第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用 2 约简；若不是，执行 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数， 继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就 是所求的最大公约数
(三)范例分析 例1用辗转相除法求8251与6105的最大公约数,写出算法分析,画出程序框图,写出 算法程序 解:用两数中较大的数除以较小的数,求得商和余数:8251=6105×1+2146 由此可得,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105 的公约数也是6105与2146的公约数,所以它们的最大公约数相等 对6105与2146重复上述步骤:6105=2146×2+1813 同理,2146与1813的最大公约数也是6105与2146的最大公约数.继续重复上述步骤 2146=1813×1+333, 1813=333×5+148 148=37×4. 最后的除数37是148和37的最大公约数,也就是8251与6105的最大公约数 这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可以 在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数 算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环 结构来构造算法 算法步骤如下: 第一步,给定两个正整数m,n 第二步,计算m除以n所得的余数为r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步. 程序框图如右图 程序 输入mn INPUT m n m除以的余数厂 r=m mod n n=r LOOP UNTIL r=o
（三）范例分析 例 1 用辗转相除法求 8 251 与 6 105 的最大公约数,写出算法分析，画出程序框图，写出 算法程序. 解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146. 由此可得，6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数，反过来，8 251 与 6 105 的公约数也是 6 105 与 2 146 的公约数，所以它们的最大公约数相等. 对 6 105 与 2 146 重复上述步骤：6 105=2 146×2+1 813. 同理，2 146 与 1 813 的最大公约数也是 6 105 与 2 146 的最大公约数.继续重复上述步骤： 2 146=1 813×1+333， 1 813=333×5+148， 333=148×2+37， 148=37×4. 最后的除数 37 是 148 和 37 的最大公约数，也就是 8 251 与 6 105 的最大公约数. 这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以 在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数. 算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环 结构来构造算法. 算法步骤如下： 第一步，给定两个正整数 m，n. 第二步，计算 m 除以 n 所得的余数为 r. 第三步，m=n，n=r. 第四步，若 r=0，则 m，n 的最大公约数等于 m；否则，返回第二步. 程序框图如右图： 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m
例2用更相减损术求98与63的最大公约数 解:由于63不是偶数,把98和63以大数减小数,并辗转相减,如下图所示 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98和63的最大公约数等于7. 前面我们学习了辗转相除法与更相减损术,现在我们来学习一种新的算法:秦九韶算法 (1)怎样求多项式f(x)=x°+x+x2+x2+x+1当x=5时的值呢? 一个自然的做法就是把5代入多项式f(x),计算各项的值,然后把它们加起来,这时,我 们一共做了1+2+3+4=10次乘法运算,5次加法运算 另一种做法是先计算x2的值,然后依次计算x2·x,(x2·x)·x,((x2·x)·x)·x的 值,这样每次都可以利用上一次计算的结果,这时,我们一共做了4次乘法运算,5次加 法运算 第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率,对于计 算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法 计算机能更快地得到结果. (2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约12021261)在 他的著作《数书九章》中提出了下面的算法 把一个n次多项式f(x)=anx”+a1-1x+…+a1x+a改写成如下形式: X+…+a1X+ao (anx+anx2+…+a1)x+ao ((anx"+an-ix"+.+a2) x+au x+ao (…((ax+an-1)x+an-2)x+…+a)x+ao 求多项式的值时,首先计算最内层括号内一次多项式的值,即v=anx+a-1, 然后由内向外逐层计算一次多项式的值,即 V2=vixtan-2
END 例 2 用更相减损术求 98 与 63 的最大公约数. 解：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减，如下图所示. 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98 和 63 的最大公约数等于 7. 前面我们学习了辗转相除法与更相减损术，现在我们来学习一种新的算法：秦九韶算法. （1）怎样求多项式 f(x)=x5 +x4 +x3 +x2 +x+1 当 x=5 时的值呢？ 一个自然的做法就是把 5 代入多项式 f(x)，计算各项的值，然后把它们加起来，这时，我 们一共做了 1+2+3+4=10 次乘法运算，5 次加法运算. 另一种做法是先计算 x 2 的值，然后依次计算 x 2·x，（x 2·x）·x，（（x 2·x）·x）·x 的 值，这样每次都可以利用上一次计算的结果，这时，我们一共做了 4 次乘法运算，5 次加 法运算. 第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计 算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法， 计算机能更快地得到结果. （2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约 1202~1261）在 他的著作《数书九章》中提出了下面的算法： 把一个 n 次多项式 f(x)=anx n +an-1x n-1 +…+a1x+a0改写成如下形式： f(x)=anx n +an-1x n-1 +…+a1x+a0 =（anx n-1 +an-1x n-2 +…+a1）x+ a0 =（（anx n-2 +an-1x n-3 +…+a2）x+a1)x+a0 =… =（…（（anx+an-1）x+an-2）x+…+a1）x+a0. 求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1=anx+an-1， 然后由内向外逐层计算一次多项式的值，即 v2=v1x+an-2
V3=V2xtan-3 v=v-x+a 这样,求n次多项式f(x)的值就转化为求n个一次多项式的值 上述方法称为秦九韶算法.直到今天,这种算法仍是多项式求值比较先进的算法. (3)计算机的一个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标 志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数,那 么这样的算法就只能是一个理论的算法 例3已知一个5次多项式为f(x)=5x+2x+3.5x2-2.6x2+1.7x-0.8, 用秦九韶算法求这个多项式当x=5时的值. 解:根据秦九韶算法,把多项式改写成如下形式 f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8, 按照从内到外的顺序,依次计算一次多项式当x=5时的值: V1=5×5+2=27 V2=27×5+3.5=138.5; V3=138.5×5-2.6=689.9; V4=689.9×5+1.7=3451.2 Vs=3415.2×5-0.8=17255.2 所以,当x=5时,多项式的值等于17255.2 算法分析:观察上述秦九韶算法中的n个一次式,可见v的计算要用到v-的值,若令V=an 我们可以得到下面的公式: v=vk1x+an-(k=1,2,…,n) 这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现. 算法步骤如下: 开始〕 第一步,输入多项式次数n、最高次的系数an和x的值. /输人anx的值 第二步,将ⅴ的值初始化为an,将i的值初始化为n-1 第三步,输入i次项的系数a i=n-1 第四步,v=Vx+a;,i=i-1 第五步,判断i是否大于或等于0.若是,则返回第三步; /输出/
v3=v2x+an-3， … vn=vn-1x+a0， 这样，求 n 次多项式 f（x）的值就转化为求 n 个一次多项式的值. 上述方法称为秦九韶算法.直到今天，这种算法仍是多项式求值比较先进的算法. （3）计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标 志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数，那 么这样的算法就只能是一个理论的算法. 例 3 已知一个 5 次多项式为 f（x）=5x5 +2x4 +3.5x3 -2.6x2 +1.7x-0.8， 用秦九韶算法求这个多项式当 x=5 时的值. 解：根据秦九韶算法，把多项式改写成如下形式： f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8， 按照从内到外的顺序，依次计算一次多项式当 x=5 时的值： v0=5； v1=5×5+2=27; v2=27×5+3.5=138.5; v3=138.5×5-2.6=689.9; v4=689.9×5+1.7=3 451.2; v5=3 415.2×5-0.8=17 255.2; 所以，当 x=5 时，多项式的值等于 17 255.2. 算法分析：观察上述秦九韶算法中的 n 个一次式，可见 vk 的计算要用到 vk-1 的值，若令 v0=an， 我们可以得到下面的公式： = + = = − − ( 1,2, , ). , 1 0 v v x a k n v a k k n k n 这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现. 算法步骤如下： 第一步，输入多项式次数 n、最高次的系数 an 和 x 的值. 第二步，将 v 的值初始化为 an，将 i 的值初始化为 n-1. 第三步，输入 i 次项的系数 ai. 第四步，v=vx+ai,i=i-1. 第五步，判断 i 是否大于或等于 0.若是，则返回第三步；