(完整版)算法案例教案
课题：§1．3算法案例
第1课时 辗转相除法与更相减损术、秦九韶算法
一、教学目标：
根据课标要求：在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力。制定以下三维目标：
1、知识与技能
理解算法案例的算法步骤和程序框图.
2、过程与方法：
引导学生得出自己设计的算法程序.
3、情感态度与价值观：
体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.
二、重点与难点：
重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.
解决策略：通过分析解决具体问题的算法步骤来引导学生写出算法，根据算法画出程序框图，再根据框图用规范的语言写出程序。
难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.
解决策略：让学生能严谨地按照自己是程序框图写出程序。
三、学法与教学用具：
1、学法：直观感知、操作确认。
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  用辗转相除法求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
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次加法运算.
另一种做法是先计算x2的值，然后依次计算x2·x，（x2·x）·x，（（x2·x）·x）·x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算.
第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果.
（2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约1202~1261）在他的著作《数书九章》中提出了下面的算法：
把一个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
=…
=（…（（anx+an-1）x+an-2）x+…+a1）x+a0.
求多项式的值时，首先计算最内层括号内一次多项式的值，即v1=anx+an-1，
然后由内向外逐层计算一次多项式的值，即
v2=v1x+an-2，
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，我们可以得到下面的公式：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。