1 3算法案例教教案Word文档格式.docx

1 3算法案例教教案Word文档格式.docx

《1 3算法案例教教案Word文档格式.docx》由会员分享，可在线阅读，更多相关《1 3算法案例教教案Word文档格式.docx（12页珍藏版）》请在冰点文库上搜索。

8251＝6105×

1＋2146

显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。

DXDiTa9E3d

6105＝2146×

2＋1813

2146＝1813×

1＋333

1813＝333×

5＋148

333＝148×

2＋37

148＝37×

4＋0

则37为8251与6105的最大公约数。

以上我们求最大公约数的方法就是辗转相除法。

也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。

利用辗转相除法求最大公约数的步骤如下：

RTCrpUDGiT

第一步：

用较大的数m除以较小的数n得到一个商q0和一个余数r0；

第二步：

若r0＝0，则n为m，n的最大公约数；

若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；

5PCzVD7HxA

第三步：

若r1＝0，则r1为m，n的最大公约数；

若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；

jLBHrnAILg

……

依次计算直至rn＝0，此时所得到的rn-1即为所求的最大公约数。

练习：

利用辗转相除法求两数4081与20723的最大公约数<

答案：

53）

2.更相减损术

我国早期也有解决求最大公约数问题的算法，就是更相减损术。

更相减损术求最大公约数的步骤如下：

可半者半之，不可半者，副置分母·

子之数，以少减多，更相减损，求其等也，以等数约之。

xHAQX74J0X

翻译出来为：

任意给出两个正数；

判断它们是否都是偶数。

若是，用2约简；

若不是，执行第二步。

以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。

继续这个操作，直到所得的数相等为止，则这个数<

等数）就是所求的最大公约数。

LDAYtRyKfE

例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。

用更相减损术求两个正数84与72的最大公约数。

12）

比较辗转相除法与更相减损术的区别：

1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

Zzz6ZB2Ltk

2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到dvzfvkwMI1

3.秦九韶算法

秦九韶计算多项式的方法

　　令

，则有

，

　　其中

.这样，我们便可由

依次求出

；

　　显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算

4.进位制

　　进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.rqyn14ZNXI

　　对于任何一个数，我们可以用不同的进位制来表示.比如：

十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.EmxvxOtOco

表示各种进位制数一般在数字右下脚加注来表示,如111001（2>

表示二进制数,34（5>

表示5进制数.SixE2yXPq5

1）.k进制转换为十进制的方法：

，

2）.十进制转化为k进制数b的步骤为：

　　第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最低位；

　　第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；

　　第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除k取余法.6ewMyirQFL

要点诠释：

　　1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.

　　2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.

　　3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.kavU42VRUs

【反馈测评】：

1．求324、243、135这三个数的最大公约数。

求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。

y6v3ALoS89

2．用更相减损术求98与63的最大公约数

由于63不是偶数，把98和63以大数减小数，并辗转相减

21－7＝21

所以，98和63的最大公约数等于7

3．已知一个五次多项式为

用秦九韶算法求这个多项式当x=5的值。

将多项式变形：

按由里到外的顺序，依此计算一次多项式当x=5时的值：

所以，当x=5时，多项式的值等于17255.2

4．将二进制数110011（2>

化成十进制数

根据进位制的定义可知

所以，110011<

2）=51。

【板书设计】：

课前预习学案

一、预习目标

1、理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。

2、理解秦九韶算法的思想。

二、预习内容

什么是进位制？

最常见的进位制是什么？

除此之外还有哪些常见的进位制？

请举例说明．

三、提出疑惑

思考：

辗转相除法中的关键步骤是哪种逻辑结构？

课内探究学案

一、学习目标

1.会用辗转相除法与更相减损术求最大公约数的方法。

2.会利用秦九韶算法求多项式的值。

3．各进位制之间能灵活转化。

二、学习重难点：

辗转相除法与更相减损术求最大公约数的方法和秦九韶算法求多项式的值。

三、学习过程

辗转相除法思路：

可以利用除法将大数化小,找两数的最大公约数.（适于两数较大时>

（1>

用较大的数m除以较小的数n得到一个商

和一个余数

（2>

若

＝0,则n为m,n的最大公约数；

≠0,则用除数n除以余数

得到一个

（3>

＝0,则

为m,n的最大公约数;

≠0,则用除数

除以余数

得到一个商

……依次计算直至

＝0，此时所得到的

即为所求的最大公约数.M2ub6vSTnP

例题1：

求两个正数1424和801的最大公约数.

①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.

②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.0YujCfmUCw

教案更相减损术：

我国早期也有求最大公约数问题的算法，就是更相减损术.在《九章算术》中有更相减损术求最大公约数的步骤：

可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.eUts8ZQVRd

翻译为：

任意给出两个正数；

判断它们是否都是偶数.若是，用2约简；

若不是，执行第二步.

以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小

数.继续这个操作，直到所得的数相等为止，则这个数<

等数）就是所求的最

大公约数.

例题2.用更相减损术求91和49的最大公约数.

秦九韶算法：

1）设计求多项式

当x=5时的值的算法，并写出程序。

2）有没有更高效的算法？

能否探求更好的算法，来解决任意多项式的求解问题？

引导学生把多项式变形为：

并提问：

从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？

x的系数依次是什么？

sQsAEJkW5T

用秦九韶算法求多项式的值，与多项式组成有直接关系吗？

用秦九韶算法计算上述多项式的值，需要多少次乘法运算和多少次加法运算？

秦九韶算法适用于一般的多项式

的求值问题吗？

GMsIasNXkA

怎样用程序框图表示秦九韶算法？

观察秦九韶算法的数学模型，计算

时要用到

的值，若令

，我们可以得到下面的递推公式：

TIrRGchYzg

这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。

请画出程序框图。

例题3．已知一个五次多项式为

进位制：

我们了解十进制吗？

所谓的十进制，它是如何构成的？

其它进位制的数又是如何的呢？

进位制是人们为了计数和运算方便而约定的记数系统。

进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。

可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。

7EqZcWLZNX

例题4．将二进制数110011（2>

精讲点拨：

1．求两个正数8251和2146;

228和1995;

5280和12155的最大公约数.

2．求两个正数8251和2146的最大公约数.

3.用秦九韶算法计算多项式

在x=-4时的值时,V3的值为：

反思总结：

比较辗转相除法与更相减损术的区别

都是求的方法，计算上辗转相除法以法为主，更相减损术以法为主，计算次数上法计算次数相对较少，特别当两个数字时计算次数的区别较明显．lzq7IGf02E

从结果体现形式来看，辗转相除法体现结果是以则得到，而更相减损术

则以而得到．

通过对秦九韶算法的学习，你对算法本身有哪些进一步认识？

（4>

秦九韶算法在计算一个n次多项式的值时，只要做____次乘法运算和____次加法运算。

课后练习与提高

1、用“辗转相除法”求得459和357的最大公约数是：

A．3B．9C．17D．51

2、将数

转化为十进制数为：

A.524B.774C.256D.260

3、用秦九韶算法计算多项式

当

时的值时,需要做乘法和加法的次数分别是：

A.6,6B.5,6

C.5,5D.6，5

参考答案:

1D2B3A

申明：

所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。