算法案例 辗转相除法与更相减损术秦九韶算法与进位制第一课时教案-数学高一必修3第一章算法初步1.3人教A版

第一章算法初步

1.3算法案例

（辗转相除法与更相减损术，秦九韶算法与进位制）

一、学习目标

1、知识与技能

（1）理解辗转相除法与更相减损术求最大公约数的方法.

（2）理解秦九韶算法中求多项式的值的步骤原理.

（3）能利用除k取余法把十进制数化为k进制数.

2、过程与方法

（1）在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。

（2）模仿秦九韶计算方法，体会古人计算构思的巧妙。能根据排序法中的直接插入排序法与冒泡排序法的步骤，了解数学计算转换为计算机计算的途径，从而探究计算机算法与数学算法的区别，体会计算机对数学学习的辅助作用。

（3）学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律。

3、情态与价值观

（1）通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。

（2）在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。

（3）通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认识到我国文化历史的悠久。通过对排序法的学习，领会数学计算与计算机计算的区别，充分认识信息技术对数学的促进。

（4）领悟十进制，二进制的特点，了解计算机的电路与二进制的联系，进一步认识到计算机与数学的联系。

二、重点难点

教学重点：（1）引导学生得出自己设计的算法步骤、程序框图和算法程序.

（2）秦九韶算法的特点

（3）两种排序法的排序步骤及计算机程序设计

（4）各进位制表示数的方法及各进位制之间的转换

教学难点：（1）体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.

（2）秦九韶算法的先进性理解

（3）排序法的计算机程序设计

（4）除k去余法的理解以及各进位制之间转换的程序框图的设计

三、专家建议

在理解最大公约数的基础上去发现辗转相除法与更相减损之术中的数学规律，并能模仿已经学过的程序框图与算法语句设计出辗转相除法与更相减损之术的程序框图与算法程序．通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认识到我国文化历史的悠久。通过对排序法的学习，领会数学计算与计算机计算的区别，充分认识信息技术对数学的促进。

四、教学方法

自学-训练-点拨-练习-总结

五、教学过程

1.辗转相除法的算法步骤

第一步，给定两个正整数m，n(m>n).

第二步，计算m除以n所得的余数r.

第三步，m＝n，n＝r.

第四步，若r＝0，则m，n 的最大公约数等于n；否则，返回第二步.

2.更相减损术的算法步骤

第一步，任意给定两个正整数，判断它们是否都是偶数.若是用2 约简；若不是，执行第二步.

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

3.秦九韶算法

把一个n次多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0改写成如下形式：

f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0

＝(a n x n－1＋a n－1x n－2＋…＋a1)x＋a0

＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0

＝…＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0.

求多项式的值时，首先计算最内层括号内的一次多项式的值，即v1＝a n x＋a n－1，然后由内向外逐层计算一次多项式的值即：v1＝a n x＋a n－1，

v2＝v1x＋a n－2，

v3＝v2x＋a n－3，

…

v n＝v n－1x＋a0，这样，求n 次多项式f(x)的值就转化为求n个一次多项式的值.

4.进位制

(1)k进制数a n a n－1…a1a0(k)转化为十进制数为

a n k n＋a n－1k n－1＋…＋a1k＋a0.

(2)把十进制数化为k 进制数用“除k 取余法”，即把所给的十进制数除以k，得到商数和余数，再用商数除以k，

得到商数和余数，直到商数为0，把上面各步所得的余数从右到左排列，即得到k 进制数.

新课探究

知识1.求两个正整数最大公约数的算法

【问题导思】

1．如何求18与54的最大公约数？

【提示】短除法．

2．要求6 750与3 492的最大公约数，上述法还好用吗？

【提示】数值太大，短除法不方便用．

(1)更相减损之术(等值算法)

用两个数中较大的数减去较小的数，再用差数和较小的数构成新的一对数，对这一对数再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，这个数就是最大公约数．

(2)辗转相除法(欧几里得算法)

用较大的数除以较小的数所得的余数和较小的数构成新的一对数，继续做上面的除法，直到大数被小数除尽，这个较小的数就是最大公约数.

知识2.秦九韶算法

【问题导思】

1．怎样计算多项式f(x)＝x5＋x4＋x3＋x2＋x＋1当x＝5时的值呢？统计所做的计算的种类及计算次数分别是什么？

【提示】f(5)＝55＋54＋53＋52＋5＋1＝3 906.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算．

2．我们把多项式变形为f(x)＝x2(1＋x(1＋x(1＋x)))＋x＋1，再统计一下计算当x＝5时的计算的种类及计算次数分别是什么？

【提示】从里往外计算仅需4次乘法和5次加法运算即可得出结果．

(1)把一元n 次多项式P(x)＝a n x n ＋a n －1x n －

1＋…＋a 1x ＋a 0改写为 P(x)＝a n x n ＋a n －1x n －

1＋…＋a 1x ＋a 0

＝(a n x n －

1＋a n －1x n －

2＋…＋a 1)x ＋a 0

＝((a n x n －

2＋a n －1x n －

3＋…＋a 2)x ＋a 1)x ＋a 0

＝(…((a n x ＋a n －1)x ＋a n －2)x ＋…＋a 1)x ＋a 0， 令v k ＝(…(a n x ＋a n －1)x ＋…＋a n －(k －1))x ＋a n －k ，

则递推公式为?

????v 0＝a n

v k ＝v k －1x ＋a n －k 其中k ＝1，2，…，n.

(2)计算P(x 0)的方法

先计算最内层括号，然后由内向外逐层计算，直到最外层括号，然后加上常数项． 知识3 进位制

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

典例精讲

类型1 求两个正整数的最大公约数

例1.分别用辗转相除法和等值算法求319和261的最大公约数．

【分析】 使用辗转相除法可依据m ＝nq ＋r ，反复执行，直到r ＝0为止；用等值算法是根据m －n ＝r ，直到n ＝1为止．

【解析】 辗转相除法：319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)． 所以319与261的最大公约数是29.

等值算法：319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29. 即(319，261)→(261，58)→(203，58)→(145，58)→(87，58)→(58，29)→(29，29)． 所以319与261的最大公约数是29.

【归纳提升】

1．利用“等值算法”求给定的两个数的最大公约数，即多次利用减法，用数对中较大的数减去较小的数，直到相减的差与数对中较小的数相等为止．

2．更相减损之术的步骤：

(1)判断两数是否都为偶数，若是，则都除以2直到所得两数不全为偶数．

(2)用较大的数减去较小的数，将差和较小的数构成一对新数，继续用较大数减去较小数，重复执行． (3)当差和较小数相等时，结束执行，此时差(或较小数)为不全为偶数的两数的最大公约数． 【变式训练】用“等值算法”(更相减损之术)求下列两数的最大公约数． (1)98，280；(2)72，168.

【解】(1)(98，280)→(98，182)→(98，84)→(14，84)→(14，70)→(14，56)→(14，42)→(14，28)→(14，14)．

∴最大公约数为14.

(2)(72，168)→(72，96)→(72，24)→(48，24)→(24，24)．

∴最大公约数为24.

类型2 秦九韶算法

例2.用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值．【分析】改写多项式确定v0依次计算v i求f（2）

【解析】将f(x)改写为

f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64，

由内向外依次计算一次多项式当x＝2时的值．

v0＝1，

v1＝1×2－12＝－10，

v2＝－10×2＋60＝40，

v3＝40×2－160＝－80，

v4＝－80×2＋240＝80，

v5＝80×2－192＝－32，

v6＝－32×2＋64＝0.

∵f(2)＝0，即x＝2时，原多项式的值为0.

【归纳提升】

1．用秦九韶算法计算多项式的值时，要正确将多项式的形式进行改写，然后由内向外依次计算．当多项式函数中间出现空项式，要以系数为零的齐次项补充．

2．秦九韶算法的步骤：

【变式训练】利用秦九韶算法计算多项式f(x)＝11－5x＋3x2＋7x3 在x＝23 的值时，不会用到下列哪个值( )

A.161

B.3772

C.86 641

D.85 169

解析：f(x)＝11－5x＋3x2＋7x3＝[(7x＋3)x－5]x＋11.

所以当x ＝23时，v 0＝7； v 1＝7×23＋3＝161＋3＝164； v 2＝164×23－5＝3772－5＝3767；

v 3＝3767×23＋11＝86 641＋11＝86 652.选D

类型3 求三个数的最大公约数

例3. 求324，243，270三数的最大公约数．

【分析】 先求324和243的最大公约数，再求这个数与270的最大公约数． 【解析】 ∵(324，243)→(243，81)→(162，81)→(81，81)． 则324与243的最大公约数为81.

又(270，81)→(189，81)→(108，81)→(81，27)→(54，27)→(27，27)． 则270与81的最大公约数为27， 故324，243，270三数的最大公约数为27. 【归纳提升】

求三个数的最大公约数，可先求两个数的最大公约数a ，再求a 与第三个数的最大公约数b ，则b 为所求的三个数的最大公约数．该题的解法可推广到求n 个数的最大公约数．

【变式训练】 用更相减损之术求27 090，21 672，8 127的最大公约数．

【解】 先求27 090与21 672的最大公约数．(27 090，21 672)→(21 672，5 418)→(16 254，5 418)→(10 836，5 418)→(5 418，5 418)．

∴27 090与21 672的最大公约数是5 418.

再求5 418与8 127的最大公约数．(8 127，5 418)→(2 709，5 418)→(2 709，2 709)． ∴5 418与8 127的最大公约数为2 709. ∴27 090，21 672，8 172的最大公约数为2 709. 类型4 进制数之间的转化

【例 4】 (1)将 101 111 011(2)转化为十进制数； (2)将 1231(5)转化为七进制数.

分析：k 进制数a n a n －1…a 2a 1a 0(k )(0≤a i

解析：(1)101 111 011(2)＝1×28＋0×27＋1×26＋1×25＋1×24＋1×23＋0×22＋1×21＋1×20＝379(10). (2)1231(5)＝1×53＋2×52＋3×5＋1＝191(10)，

∴1231(5)＝362(7).

【变式训练】(1)11 111 000(2)＝248 (10)；

(2)154(6)＝130 (7).

●课堂小结

1.辗转相除法与更相减损术求最大公约数的区别与联系

2.秦九韶算法的优点.

(1)减少乘法运算的次数.

(2)规律性强，便于利用循环语句实现.

(3)不用对x 做幂的运算，每次都是计算一个一次多项式的值，提高了计算精度.

3.进位制

对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111 001，也可以用八进制表示为71，用十六进制表示为39，它们所代表的数值都是一样的.

表示各种进制数时，一般要在数字右下角加注来表示.如111 001(2)表示二进制数，34(5)表示五进制数.电子计算机一般都使用二进制.

六、板书设计

七．当堂检测

1．用更相减损之术可求得78与36的最大公约数是()

A．24B．18C．12D．6

【解析】78－36＝42，42－36＝6，36－6＝30，30－6＝24，24－6＝18，18－6＝12，12－6＝6，∴6为78与36的最大公约数．

【答案】 D

2．用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为()

A．5，4B．5，5C．4，4D．4，5

【解析】n次多项式当最高次项的系数不为1时，需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，故加法次数要减少一次，为5－1＝4.

【答案】 D

3．用更相减损之术求81与135的最大公约数时，要进行________次减法运算．

【解析】135－81＝54，81－54＝27，54－27＝27，共进行了3次减法运算．

【答案】 3

4．将二进制数101 101(2)化为八进制数，结果为________．

【解析】101 101(2)＝1×25＋0×24＋1×23＋1×22＋0×2＋1

＝32＋8＋4＋1＝45.

101 101(2)＝55(8)．

【答案】55(8)

5．求当x＝2时，f(x)＝x5－5x4＋x3－1的函数值．

【解】f(x)＝x5－5x4＋x3－1＝((((x－5)x＋1)x＋0)x＋0)x－1，利用公式有v0＝1，

v1＝1×2－5＝－3，

v2＝(－3)×2＋1＝－5，

v3＝(－5)×2＋0＝－10，

v4＝(－10)×2＋0＝－20，

v5＝(－20)×2－1＝－41，

∴f(2)＝－41.

秦九韶算法教案

秦九韶算法教案-CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN

第7课时秦九韶算法 班级姓名 学习目标 1、掌握秦九韶算法的步骤，原理 2、秦九韶算法的运用 ※学习重点、难点： 重点：秦九韶算法求多项式的值 难点：秦九韶算法的运用 学习过程 一、知识链接 复习：分别用辗转相除法和更相减损术求288与123的最大公约数． （预习教材P37~ P38，找出疑惑之处） 二、自主学习（首先独立思考探究，然后合作交流展示） 探究1：已知多项式f(x)＝x5＋x4+x3－x2+x+1 问题(1)：求f(1) 问题(2)：若求f(39)，再代入运算出现什么情况？ 问题(3)：当x的值较大时，有没有更好的方法求函数值呢？ 探究2：利用秦九韶算法多项式f(x)＝x5＋x4+x3－x2+x+1当x＝2时的值

知识归纳： (1)秦九韶算法的步骤： (2)秦九韶算法的原理是? ???? v 0＝a n ， v k ＝v k －1x ＋a n －k ， 三、合作探究 ※ 知识检测 1.用秦九韶算法求多项式f (x )＝6x 6＋5x 5＋4x 4＋3x 3＋2x 2＋x 当x ＝2时的值． ※ 能力达标 2. 用秦九韶算法计算多项式f (x )＝3x 6＋4x 5＋5x 4＋6x 3＋7x 2＋8x ＋1当x ＝0.4时的值时，需要做乘法和加法分别是多少次？

小结： ※拓展提高 3.已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算当x＝3时，求v3的值 四、课堂小结 1．秦九韶算法的步骤，原理 2．秦九韶算法的运用 达标练习 1.利用秦九韶算法求f(x)＝x5＋x3＋x2＋x＋1当x＝3时的值

算法案例(教教案)

1.3算法案例 【教学目标】： 1.理解辗转相除法与更相减损术中蕴含地数学原理，并能根据这些原理进行算法分析. 2.基本能根据算法语句与程序框图地知识设计完整地程序框图并写出算法程序. 【教学重难点】： 重点：理解辗转相除法与更相减损术求最大公约数地方法. 难点：把辗转相除法与更相减损术地方法转换成程序框图与程序语言. 【教学过程】： 情境导入： 1.教师首先提出问题：在初中，我们已经学过求最大公约数地知识，你能求出18与30地公约数吗？ 2.接着教师进一步提出问题，我们都是利用找公约数地方法来求最大公约数，如果公约数比较大而且根据我们地观察又不能得到一些公约数，我们又应该怎样求它们地最大公约数？比如求8251与6105地最大公约数？这就是我们这一堂课所要探讨地内容. 新知探究： 1.辗转相除法 例1 求两个正数8251和6105地最大公约数. （分析：8251与6105两数都比较大，而且没有明显地公约数，如能把它们都变小一点，根据已有地知识即可求出最大公约数） 解：8251＝6105×1＋2146 显然8251地最大公约数也必是2146地约数，同样6105与2146地公约数也必是8251地约数，所以8251与6105地最大公约数也是6105与2146地最大公约数. 6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8251与6105地最大公约数. 以上我们求最大公约数地方法就是辗转相除法.也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出地.利用辗转相除法求最大公约数地步骤如下： 第一步：用较大地数m除以较小地数n得到一个商q0和一个余数r0； 第二步：若r0＝0，则n为m，n地最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1； 第三步：若r1＝0，则r1为m，n地最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2； …… 依次计算直至r n＝0，此时所得到地r n-1即为所求地最大公约数. 练习：利用辗转相除法求两数4081与20723地最大公约数（答案：53） 2.更相减损术 我国早期也有解决求最大公约数问题地算法，就是更相减损术. 更相减损术求最大公约数地步骤如下：可半者半之，不可半者，副置分母·子之数，以

高一数学重点知识点：算法初步

高一数学重点知识点：算法初步【】高中如何复习一直都是学生们关注的话题，下面是的编辑为大家准备的高一数学重点知识点：算法初步 第一章算法初步 1.1.1 算法的概念 1、算法概念： 在数学上，现代意义上的算法通常是指可以用计算机来解决的某一类问题是程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成. 2. 算法的特点: (1)有限性：一个算法的步骤序列是有限的，必须在有限操作之后停止，不能是无限的. (2)确定性：算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可. (3)顺序性与正确性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能完成问题. (4)不唯一性：求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法. (5)普遍性：很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限、事先设计好的步骤

加以解决. 1.1.2 程序框图 1、程序框图基本概念： (一)程序构图的概念：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形。一个程序框图包括以下几部分：表示相应操作的程序框;带箭头的流程线;程序框外必要文字说明。 (二)构成程序框的图形符号及其作用 程序框名称功能 起止框表示一个算法的起始和结束，是任何流程图不可少的。 输入、输出框表示一个算法输入和输出的信息，可用在算法中任何需要输入、输出的位置。 处理框赋值、计算，算法中处理数据需要的算式、公式等分别写在不同的用以处理数据的处理框内。 判断框判断某一条件是否成立，成立时在出口处标明是或Y 不成立时标明否或N。 学习这部分知识的时候，要掌握各个图形的形状、作用及使用规则，画程序框图的规则如下： 1、使用标准的图形符号。 2、框图一般按从上到下、从左到右的方向画。 3、除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符

算法初步比较经典的教案

算法初步与框图 一、知识网络 二、考纲要求 1.算法的含义、程序框图 （1）了解算法的含义，了解算法的思想. （2）理解程序框图的三种基本逻辑结构：顺序、条件分支、循环. 2.基本算法语句 理解几种基本算法语句――输入语句、输出语句、赋值语句、条件语句、循环语句的含义. 三、复习指南 本章是新增内容，多以选择题或填空题形式考查，常与数列、函数等知识联系密切.考查的重点是算法语句与程序框图,以基础知识为主,如给出程序框图或算法语句,求输出结果或说明算法的功能;或写出程序框图的算法语句,判断框内的填空等考查题型.难度层次属中偏低. 第一节 算法与程序框图 ※知识回顾 1 2..

3. 4. 5.算法的基本特征：①明确性：算法的每一步执行什么是明确的；②顺序性：算法的“前一步”是“后一步”的前提，“后一步”是“前一步”的继续；③有限性：算法必须在有限步内完成任务，不能无限制的持续进行；④通用性：算法应能解决某一类问题. ※典例精析 例1.如图所示是一个算法的程序框图，则该程序框图所表示的功能是 解析：首先要理解各程序框的含义,输入a,b,c三个数之后,接着判断a,b的大小,若b小，则把b赋给a,否则执行下一步，即判断a与c的大小，若c小，则把c赋给a, 否则执行下一步，这样输出的a是a,b,c三个数中的最小值.所以该程序框图所表示的功能是求a,b,c三个数中的最小值. 评注: 求a,b,c三个数中的最小值的算法设计也可以用下面程序框图来表示. 例2.下列程序框图表示的算法功能是（） （1）计算小于100的奇数的连乘积 （2）计算从1开始的连续奇数的连乘积 （3）计算从1开始的连续奇数的连乘积， 当乘积大于100时，计算奇数的个数 （4）计算L≥ 1×3×5××n100成立时n的最小值 解析：为了正确地理解程序框图表示的算法，可以将执行过程分解，分析每一步执行的结果.可以看出程序框图中含有当型的循环结构,故分析每一次循环的情况,列表如下: 第一次:13,5 =?=； S i 第二次:135,7 =??=； S i 第三次:1357,9 S<不成立,输出结果是7,程序框图表示的算法功能是求使=???=,此时100 S i

B1.3.4 生活中的算法实例 教案

1.3.4 生活中的算法实例 教学要求：通过生活实例进一步了解算法思想. 教学重点：生活实例的算法分析. 教学难点：算法思想的理解. 教学过程： 一、复习准备： 1. 前面学习了哪几种算法案例？每种算法的作用及操作方法是怎样的？ 2. 算法思想在我们的生活中无处不在，如何利用我们所学习的知识解决生活中的实际问题？ 二、讲授新课： 1. 霍奇森算法： 提问：同学们经常会面对一个共同的问题，就是有时有太多的事情要做. 例如，你可能要面临好几门课的作业的最后期限，你如何合理安排以确保每门课的作业都能如期完成？如果根本不可能全部按期完成，你该怎么办？（霍奇森算法可以使得迟交作业的数目减到最小. 这一算法已经广泛应用于工业生产安排的实践中.） 例如：当你拿到下面这组数据后，你会如何安排你的时间，以确保每门课的作业都能如期完 法可用自然语言描述为：①把这些作业按到期日的顺序从左到右排列，从最早到期的到最晚到期的；②假设从左到右一项一项做这些作业的话，计算出从开始到完成某一项作业时所花的时间. 依次做此计算直到完成了所列表中的全部作业而没有一项作业会超期，停止；或你算出某项作业将会超期，继续第三步；③考虑第一项将会超期的作业以及它左边的所有作业，从中取出花费时间最长的那项作业，并把它从表中去掉；④回到第二步，并重复第二到四步，直到做完. 2. 孙子问题： 韩信是秦末汉初的著名军事家. 据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数. 韩信先令士兵排成了3列纵队进行操练，结果有2人多余；接着他立刻下令将队形改为5列纵 队，这一改又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行. 由此得出共有士兵2333人. 如何用现在的算法思想分析这一过程？ 《孙子算经》中给出了它的具体解法，其步骤是：选定57?的倍数，被3除余1，即70；选定37?的一个倍数，被5除余1，即21；选定35?的一个倍数，被7除余1，即15. 然后按下式计算702213152105m p =?+?+?-，式中105为3,5,7的最小公倍数，p 为适当的整数，使得0105m <≤，这里取2p =. 求解“孙子问题”的一种普通算法： 第一步：2m =. 第二步：若m 除以3余2，则执行第三步；否则1m m =+，执行第二步. 第三步：若m 除以5余3，则执行第四步；否则1m m =+，执行第二步. 第四步：若m 除以7余2，则执行第五步；否则1m m =+，执行第二步. 第五步：输出m . 3. 小结：算法的基本思想. 三、巩固练习： 略 四、作业：教材P38第3题

数学：算法案例教案新人教A版必修

１．３算法案例 （１）教学目标 （a）知识与技能 １．理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。 ２．基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 （b）过程与方法 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。 （c）情态与价值 １．通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。 ２．在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。 （２）教学重难点 重点：理解辗转相除法与更相减损术求最大公约数的方法。 难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。 （３）学法与教学用具 学法：在理解最大公约数的基础上去发现辗转相除法与更相减损术中的数学规律，并能模仿已经学过的程序框图与算法语句设计出辗转相除法与更相减损术的程序框图与算法程序。 教学用具：电脑，计算器，图形计算器 （４）教学设想 （一）创设情景，揭示课题

１．教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出１8与３0的公约数吗？ ２．接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8２５１与6１0５的最大公约数？这就是我们这一堂课所要探讨的内容。 （二）研探新知 １．辗转相除法 例１求两个正数8２５１和6１0５的最大公约数。 （分析：8２５１与6１0５两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数） 解：8２５１＝6１0５×１＋２１４6 显然8２５１的最大公约数也必是２１４6的约数，同样6１0５与２１４6的公约数也必是8２５１的约数，所以8２５１与6１0５的最大公约数也是6１0５与２１４6的最大公约数。 6１0５＝２１４6×２＋１8１３ ２１４6＝１8１３×１＋３３３ １8１３＝３３３×５＋１４8 ３３３＝１４8×２＋３7 １４8＝３7×４＋0 则３7为8２５１与6１0５的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前３00年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：

高一数学必修三算法初步知识点

高一数学必修三算法初步知识点 【一】 (1)算法概念：在数学上，现代意义上的“算法”通常是指能够 用计算机来解决的某一类问题是程序或步骤，这些程序或步骤必须是 明确和有效的，而且能够在有限步之内完成. (2)算法的特点： ①有限性：一个算法的步骤序列是有限的，必须在有限操作之后 停止，不能是无限的. ②确定性：算法中的每一步应该是确定的并且能有效地执行且得 到确定的结果，而不理应是模棱两可. ③顺序性与准确性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只 有执行完前一步才能实行下一步，并且每一步都准确无误，才能完成 问题. ④不性：求解某一个问题的解法不一定是的，对于一个问题能够 有不同的算法. ⑤普遍性：很多具体的问题，都能够设计合理的算法去解决，如 心算、计算器计算都要经过有限、事先设计好的步骤加以解决。 【二】 (1)顺序结构：顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序实行的，它是由若干个依次执行的处 理步骤组成的，它是任何一个算法都离不开的一种基本算法结构。 顺序结构在程序框图中的体现就是用流程线将程序框自上而下地 连接起来，按顺序执行算法步骤。如在示意图中，A框和B框是依次执行的，只有在执行完A框指定的操作后，才能接着执行B框所

指定的操作。 (2)条件结构：条件结构是指在算法中通过对条件的判断根据条 件是否成立而选择不同流向的 算法结构。 条件P是否成立而选择执行A框或B框。无论P条件是否成立， 只能执行A框或B框之一，不可能同时执行 A框和B框，也不可能A框、B框都不执行。一个判断结构能够 有多个判断框。 (3)循环结构：在一些算法中，经常会出现从某处开始，按照一 定条件，反复执行某一处理步骤的情况，这就是循环结构，反复执行 的处理步骤为循环体，显然，循环结构中一定包含条件结构。循环结 构又称重复结构，循环结构可细分为两类： ①一类是当型循环结构，如下左图所示，它的功能是当给定的条 件P成立时，执行A框，A框执行完毕后，再判断条件P是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次条件P不 成立为止，此时不再执行A框，离开循环结构。 ②另一类是直到型循环结构，如下右图所示，它的功能是先执行，然后判断给定的条件P是否成立，如果P仍然不成立，则继续执行A 框，直到某一次给定的条件P成立为止，此时不再执行A框，离开循 环结构。 注意：1循环结构要在某个条件下终止循环，这就需要条件结构 来判断。所以，循环结构中一定包含条件结构，但不允许“死循环”。 2在循环结构中都有一个计数变量和累加变量。计数变量用于记 录循环次数，累加变量用于输出结果。计数变量和累加变量一般是同 步执行的，累加一次，计数一次。 【三】

算法初步章节复习课教案

算法初步一.本章的知识结构 二.知识梳理 (1)四种基本的程序框 输入. 终端框（起止框） 输入.输出框 终端框（起止框） 输入.输出框 处理框 判断框终端框（起止框）输入、输出框处理框 判断框 (2)三种基本逻辑结构 顺序结构条件结构循环结构 (3)基本算法语句 （一）输入语句 单个变量 多个变量 （二） （三）赋值语句 （四）条件语句 IF-THEN-ELSE格式

当计算机执行上述语句时，首先对IF 后的条件进行判断，如果条件符合，就执行THEN 后的语句1，否则执行ELSE 后的语句2。其对应的程序框图为：（如上右图） IF -THEN 格式 计算机执行这种形式的条件语句时，也是首先对IF 后的条件进行判断，如果条件符合，就执行THEN 后的语句，如果条件不符合，则直接结束该条件语句，转而执行其他语句。其对应的程序框图为：（如上右图） （五）循环语句 （1）WHILE 语句 其中循环体是由计算机反复执行的一组语句构成的。WHLIE 后面的“条件”是用于控制计算机执行循环体或跳出循环体的。 当计算机遇到WHILE 语句时，先判断条件的真假，如果条件符合，就执行WHILE 与WEND 之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直到某一次条件不符合为止。这时，计算机将不执行循环体，直接跳到WEND 语句后，接着执行WEND 之后的语句。因此，当型循环有时也称为“前测试型”循环。其对应的程序结构框图为：（如上右图） （2）UNTIL 语句 当计算机遇到UNIT 语句时，先执行一次DO 和LOOP UNIT 之间的循环体，然后判断UNIT 后的条件是否成立，如果 IF 条件 THEN 语句 END IF WHILE 条件 循环体 WEND DO 循环体 LOOP UNTIL 条件

2019-2020年高中数学 1.3 《算法案例》 教案 新人教版必修3

2019-2020年高中数学 1.3 《算法案例》教案新人教版必修3 （1）教学目标 （a）知识与技能 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。 2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 （b）过程与方法 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。 （c）情态与价值 1.通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。 2.在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。 （2）教学重难点 重点：理解辗转相除法与更相减损术求最大公约数的方法。 难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。 （3）学法与教学用具 学法：在理解最大公约数的基础上去发现辗转相除法与更相减损术中的数学规律，并能模仿已经学过的程序框图与算法语句设计出辗转相除法与更相减损术的程序框图与算法程序。 教学用具：电脑，计算器，图形计算器 （4）教学设想 （一）创设情景，揭示课题 1.教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？ 2.接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。 （二）研探新知 1.辗转相除法 例1 求两个正数8251和6105的最大公约数。 （分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数） 解：8251＝6105×1＋2146 显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。 6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德

秦九韶算法及K进制练习题(含详细解答)

. . . . 秦九韶与k进制练习题 一．选择题（共16小题） 1．把77化成四进制数的末位数字为（） A．4 B．3 C．2 D．1 2．用秦九韶算法求多项式f（x）=x4+2x3+x2﹣3x﹣1，当x=2时的值，则v3=（） A．4 B．9 C．15 D．29 3．把67化为二进制数为（） A．110000 B．1011110 C．1100001 D．1000011 4．用秦九韶算法计算多项式f（x）=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时，需要做乘法和加法的次数分别是（） A．6，6 B．5，6 C．5，5 D．6，5 5．使用秦九韶算法计算x=2时f（x）=6x6+4x5﹣2x4+5x3﹣7x2﹣2x+5的值，所要进行的乘法和加法的次数分别为（） A．6，3 B．6，6 C．21，3 D．21，6 6．把27化为二进制数为（） A．1011（2）B．11011（2）C．10110（2）D．10111（2） 7．用秦九韶算法计算多项式f（x）=5x5+4x4+3x3﹣2x2﹣x﹣1在x=﹣4时的值时，需要进行的乘法、加法的次数分别是（） A．14，5 B．5，5 C．6，5 D．7，5 8．二进制数11001001（2）对应的十进制数是（） A．401 B．385 C．201 D．258 9．小明中午放学回家自己煮面条吃，有下面几道工序：①洗锅盛水2分钟；②洗菜6分钟；③准备面条及佐料2分钟；④用锅把水烧开10分钟；⑤煮面条和菜共3分钟．以上各道工序，除了④之外，一次只能进行一道工序．小明要将面条煮好，最少要用（）分钟． A．13 B．14 C．15 D．23 10．用秦九韶算法在计算f（x）=2x4+3x3﹣2x2+4x﹣6时，要用到的乘法和加法的次数分别为（）

算法教案

一、知识点剖析 1．算法的定义和特点 掌握要点： 算法定义：在数学中指按照一定规则解决某一类问题的明确和有限的步骤。 算法特点：①有穷性：一个算法的步骤是有限的，它应在有限步操作之后停止。②确定性，算法的每一步操作必须是明确的，不能有歧义或模糊且算法执行后一定产生确定的结果，不能模棱两可。③可行性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个明确的后继步骤，前一步是后一步的前提,只有执行完前一步才能进行下一步，并且每一步都要准确无误才能解决问题。④不惟一性：求解某一类问题的算法是不惟一的，对于一个问题可以有不同的算法。⑤普遍性，很多具体的问题都可以设计合理的算法解决。 易混易错：（1）算法一般是机械的，有时要进行大量重复的运算，只要按部就班的做总能算出结果，通常把算法过程称为“数学机械化”，“数学机械化”的最大优点是它可以让计算机来完成。（2）实际上，处理任何问题都需要算法。如，邮购物品有其相应的手续。购买飞机票也有一定的手续等。（3）求解某个问题的算法不惟一。 2．（1）程序框图表示算法步骤的一些常用的图形和符号 点的符号。 （2）三种基本逻辑结构 ①顺序结构 ②条件结构 ③循环结构

顺序结构：顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的。这是任何一个算法都离不开的基本结构。 条件结构：在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立会有不同的流向，条件结构就是处理这种过程的结构。 易混易错：在条件结构中无论条件是否成立，都只能执行两框之一，两框不可能同时执行，也不可能两框都不执行。 循环结构：算法结构中经常会遇到从某处开始，按照一定条件反复执行某些步骤的情况，这就是循环结构，反复执行的步骤成为循环体。循环结构分为两种：当性循环结构和直到性循环结构。 当性循环结构：在每次执行循环体前，对条件进行判断，当条件满足时，执行循环体，否则终止循环。“先判断” 直到性循环结构：在执行了一次循环体后，对条件进行判断，如果条件不满足就继续执行循环体，直到条件满足时终止循环。“先循环” 注意：循环结构中一定包含着条件结构。 3．基本算法语句 （1）输入语句 ①输入语句的一般形式是：INPUT “提示内容”；变量 ②输入语句的作用是实现算法的输入信息功能 ③“提示内容”提示用户输入什么样的信息 ④输入语句可以给变量提供初值 ⑤提示内容与变量之间用分号隔开，若输入多个变量，变量之间用逗号隔开。 例如：INPUT “提示内容1，提示内容2，提示内容3，…”；变量1，变量2，变量 （2）输出语句 ①输出语句的一般形式是：PRINT “提示内容”；表达式 ②输出语句的作用是实现算法的输出结果功能。 ③“提示内容”提示用户输入什么样的信息，如PRINT “S=；S 是提示输出的结果是S的值 ④PRINT语句可以在屏幕上出现常量、变量以及系统信息。 注意：任何求解问题的算法，都要把求解问题的结果输出。 （3）赋值语句 ①赋值语句是最基本的语句 ②赋值语句的一般格式为：变量=表达式 ③“=”叫做赋值号。 易混易错:①赋值号做变只能是变量而不能使表达式。 ②赋值号的左右两边不能调换。 ③不能利用赋值语句进行代数式的演算（如化简、因式分解、解方程等）。 ④赋值号与数学中的符号意义不同。 注意:输入语句、输出语句、赋值语句基本上对应程序框图中的顺序结构；一个算法有0个或者多个输入，有一个或多个输出；输出语句和赋值语句具有运算功能而输入语句不具有运算功能。 （4）条件语句 共分为两种形式 IF-THEN-ELSE格式 (1)

数学：秦九韶算法教案新人教版A必修

舜耕中学高一数学必修３导学案（教师版） 编号 教学过程： 一、〖创设情境〗 我们已经学过了多项式的计算，下面我们计算一下多项式 1)(2345+++++=x x x x x x f 当5=x 时的值，并统计所做的计算的种类及计算次数. 根据我们的计算统计可以得出我们共需要１0次乘法运算，５次加法运算. 如果我们先计算2x 的值，然后依次计算x x ?2，x x ?3，x x ?4 的值，这样每次都可以 利用上一次计算的结果.再统计一下计算次数，可以得出仅需４次乘法和５次加法运算，显 然少了6次乘法运算，这种算法就叫秦九韶算法. 二、〖新知探究〗 我国南宋时期的数学家秦九韶（约１２0２—１２6１）在他的著作《数书九章》中提出了下面的算法: 把一个n 次多项式012211)(a x a x a x a x a x f n n n n n n +++++=---- 改写成如下形式：

1210 123120 1322110 12211)))((())(()()(a a x a x a x a a x a x a x a x a a x a x a x a x a a x a x a x a x a x f n n n n n n n n n n n n n n n n n n n +++++==+++++=+++++=+++++=-------------- 求多项式的值时，可以令n a v =0，然后计算最内层括号内一次多项式的值，即 n a v =0， 101-+=n a x v v ， 212-+=n a x v v ， 323-+=n a x v v ， …… 01a x v v n n +=-， 这样，求n 次多项式)(x f 的值就转化为求n 个一次多项式的值.上述方法称为秦九韶算法. 例１ 已知一个５次多项式为8.07.16.25.324)(2 345-+-++=x x x x x x f 用秦九韶算法 求这个多项式当5=x 时的值.（参考课本P ３8） 〖思考〗：（１）例１计算时需要多少次乘法计算？多少次加法计算？（１５，５） （２）用秦九韶算法求n 次多项式012211)(a x a x a x a x a x f n n n n n n +++++=---- 当 0x x =（0x 是任意实数）时的值，需要多少次乘法运算和多少次加法运算？（2 )1(+n n ，n ） 随堂练习：利用秦九韶算法计算15.033.016.041.083.0)(2 345+++++=x x x x x x f 当5=x 时的值. 秦九韶算法的算法步骤、程序框图、程序语言参考课本P ３9． 三、〖归纳小结〗 秦九韶算法的计算过程. 四、〖书面作业〗 课本P ４8习题１．３ A 组２. 五、〖板书设计〗

1.3.3算法案例 优秀教案

1．3 算法案例 案例3 进位制 【教学目标】 1．知识与技能：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换。 2．过程与方法：学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律。 3．情感、态度与价值观：领悟十进制，二进制的特点，了解计算机的电路与二进制的联系，进一步认识到计算机与数学的联系。 【教学重点】各进位制表示数的方法及各进位制之间的转换 【教学难点】除k去余法的理解以及各进位制之间转换的程序框图的设计 【学法】在学习各种进位制特点的同时探讨进位制表示数与十进制表示数的区别与联系，熟悉各种进位制表示数的方法，从而理解十进制转换为各种进位制的除k去余法。 【课前准备】电脑，计算器，图形计算器

练习与测试： 1、4511.完成下列进位制之间的转化： 101101（2）＝____________（10）____________（7） 解答：45（10），63（7） 2、把“五进制”数)5(1234转化为“十进制”数，再把它转化为“八进制”数。 解答：3210123415253545194=?+?+?+?=（5） 8194824830余 203 194302∴=（8） 3、将389化成四进位制数的末位是____________。 解答：末位是1， 438949742446410 余 11 021 ，末位是第一个余数，38912011=（4） 注意：余数自下而上排列 4、下列各数)9(85 、 )6(210 、 )4(1000 、 )2(111111中最小的数是____________。 解答：最小的数是)2(111111，因为(9)8589577=?+=、 2 (6)2102616078=?+?+=、 3(4)10001464=?= 、 5432 (2)1111111212121212163=?+?+?+?+?+= 5、二进制数111.11转换成十进制数是_________________. 解答：是7.75 因为2 1 1 2 11 111.11121212121242124 --=?+?+?+?+?=++++ 6、二进制数111011001001 (2)对应的十进制数是( ) A.3901 B.3902 C.3785 D.3904 解答：C 7、将二进制数1010 101(2) 化为十进制结果为 ； 再将该数化为八进制数，结果为 . 解答：85 、 125(8) 8、计算11011（2）-101（2）= （用二进制表示） 解答： 10110

1.3 算法案例

[学习目标] 1.理解辗转相除法与更相减损术的含义，了解其执行过程.2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质.3.理解进位制的概念，能进行不同进位制间的转化.4.了解进位制的程序框图和程序． 知识点一辗转相除法与更相减损术 1．辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法． (2)辗转相除法的算法步骤 第一步，给定两个正整数m，n. 第二步，计算m除以n所得的余数r. 第三步，m＝n，n＝r. 第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步． 2．更相减损术 第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步． 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． 3．辗转相除法和更相减损术的区别与联系：

答 先判断a ，b 是否为偶数，若是，都除以2再进行． 知识点二 秦九韶算法 1．秦九韶算法简介 (1)秦九韶算法要解决的问题是求多项式的值． (2)秦九韶算法的特点： 通过一次式的反复计算，逐步得到高次多项式的值，即将一个n 次多项式的求值问题归结为重复计算n 个一次多项式的值的问题． (3)秦九韶算法的原理： 将f (x )＝a n x n ＋a n －1x n － 1＋…＋a 1x ＋a 0改写为： f (x )＝(a n x n －1＋a n －1x n － 2＋…＋a 1)x ＋a 0 ＝((a n x n －2＋a n －1x n － 3＋…＋a 2)x ＋a 1)x ＋a 0 ＝… 先计算最内层括号内一次多项式的值，即v 1＝a n x ＋a n －1，再由内向外逐层计算一次多项式v k 的值． 2．秦九韶算法的操作方法 (1)算法步骤如下： 第一步，输入多项式次数n 、最高次项的系数a n 和x 的值． 第二步，将v 的值初始化为a n ，将i 的值初始化为n －1. 第三步，输入i 次项的系数a i . 第四步，v ＝v x ＋a i ，i ＝i －1. 第五步，判断i 是否大于或等于0.若是，则返回第三步；否则，输出多项式的值v . (2)程序框图如图所示．

高中数学常见题型解法归纳 - 四种算法案例

高中数学常见题型解法归纳 - 四种算法案例 【知识要点】 算法案例有辗转相除法、更相减损术、秦九韶算法和进位制. 一、辗转相除法 辗转相除法求两个数的最大公约数，其算法可以描述如下： ① 输入两个正整数m 和n ； ② 求余数r ：计算m 除以n ，将所得余数存放到变量r 中； ③更新被除数和余数：m =n ，n =r ； ④判断余数r 是否为0.若余数为0，则输出结果；否则转向第②步继续循环执行 如此循环，直到得到结果为止. 例：利用辗转相除法求6105与2146的最大公约数 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 最后的除数37是6105与2146的最大公约数. 二、更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术.在《九章算术》中记 载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母?子之数，以少减多，更相减损，求其等也，以等数约之. 解题步骤：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止,则这个相等的数就是所求的最大公约数. 例：用更相减损术求98与63的最大公约数 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以98和63的最大公约数是7. 三、秦九韶算法 秦九韶算法适用一般的多项式121210()n n n n n n f x a x a x a x a x a ----=+++???++ 的求值问题.用秦九韶算法求一般多项式121210()n n n n n n f x a x a x a x a x a ----=+++???++.当0x x =时的函 数值，可把n 次多项式的求值问题转化成求n 个一次多项式的值的问题，即求 0n v a = 1v =x v 0+1-n a 2v =1v x +2n a - 3v =2v x +3n a - …… n v =x v n 1-+n a

秦九韶算法教学设计

秦九韶算法教学设计 Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998

《秦九韶算法》教学设计 一、教学目标 （一）知识与技能 1、理解秦九韶算法的计算过程及其程序； 2、会用秦九韶算法计算高次多项式的值． （二）过程与方法 1、体验用秦九韶算法计算高次多项式的值的过程； 2、体验写秦九韶算法的程序的过程． （三）情感态度与价值观 1、通过对秦九韶算法的理解和运用，体会我国古代数学家对数学的贡献，激发学生的民族自豪感和爱国热情,增强他们学习数学的积极性； 2、培养学生理解、运用知识的能力． 二、教学重、难点 重点：用秦九韶算法计算高次多项式的值． 难点：用循环结构表示“秦九韶算法”的算法步骤． 三、教学方法：情景教学法、启发式教学法、练习法和讲授法． 四、教学用具：电脑、投影仪、计算器． 五、教学设计 （一）提出问题，引出新课 当x=5时，求多项式f(x)=x5+x4+x3+x2+x+1的值 让学生填空:

一个自然的做法：把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时你一共做了 10 次乘法运算， 5次加法运算. 另一种做法：先计算x 2的值，然后一次计算x 2﹒x,( x 2﹒x)﹒x,( (x 2﹒x)﹒x)﹒x 的值，这样每次都可以用上一次的结果，这时你用了 4 次乘法运算， 5 次加法运算. 显然，第二种做法少了6次乘法运算。这第二种算法就叫秦九韶算法(秦九韶，我国南宋时期的数学家，其着作有《数书九章》). 秦九韶算法就来自于秦九韶的《数书九章》. （二）探究新知 1、秦九韶算法 把一个n 次多项式()0111a x a x a x a x f n n n n ++++=-- 改写成如下形式: 求多项式的值时,首先计算最内层括号内一次多项式的值,即 然后由内向外逐层计算一次多项式的值,即 这样，求n 次多项式()x f 的值就转化为求n 个一次多项式的值． 上述方法称为秦九韶算法. 直到今天,这种算法仍是多项式求值比较先进的算法. 2、用秦九韶算法计算高次多项式的值 例1 已知一个5次多项式为(),8.07.16.25.3242345-+-++=x x x x x x f 用秦九韶算法求这个多项式当5=x 时的值. 解：将多项式变形为： 按照从内到外的顺序，依次计算一次多项式当x = 5时的值： 所以，当x = 5时，多项式的值等于 另解：（秦九韶算法的另一种直观算法）

秦九韶算法 人教版高中数学必修3教材教案

第2课时案例2 秦九韶算法 授课时间：第周年月日（星期） 导入新课 思路1（情境导入） 大家都喜欢吃苹果吧，我们吃苹果都是从外到里一口一口的吃，而虫子却是先钻到苹果里面从里到外一口一口的吃，由此看来处理同一个问题的方法多种多样.怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？方法也是多种多样的，今天我们开始学习秦九韶算法. 思路2（直接导入） 前面我们学习了辗转相除法与更相减损术，今天我们开始学习秦九韶算法. 推进新课 新知探究 提出问题 （1）求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值有哪些方法？比较它们的特点. （2）什么是秦九韶算法？ （3）怎样评价一个算法的好坏？ 讨论结果： （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)=a n x n+a n-1x n-1+…+a1x+a0改写成如下形式： f(x)=a n x n+a n-1x n-1+…+a1x+a0 =（a n x n-1+a n-1x n-2+…+a1）x+ a0 =（（a n x n-2+a n-1x n-3+…+a2）x+a1)x+a0 =… =（…（（a n x+a n-1）x+a n-2）x+…+a1）x+a0. 求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1=a n x+a n-1， 然后由内向外逐层计算一次多项式的值，即 v2=v1x+a n-2， v3=v2x+a n-3， … v n=v n-1x+a0， 这样，求n次多项式f（x）的值就转化为求n个一次多项式的值. 上述方法称为秦九韶算法.直到今天，这种算法仍是多项式求值比较先进的算法. （3）计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这

高中数学新课程----算法案例教案

高中数学新课程----算法案例 一．【课标要求】 通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。 二．【命题走向】 算法是高中数学新课程中的新增内容，本讲的重点是几种重要的算法案例思想，复习时重算法的思想轻算法和程序的构造。 预测2020年高考队本讲的考察是：以选择题或填空题的形式出现，分值在5分左右，考察的热点是算法实例和传统数学知识的结合题目 三．【要点精讲】 1．求最大公约数 （1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来 （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法可以描述如下： ①输入两个正整数m和n； ②求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r； ④判断余数r是否为0。若余数为0，则输出结果；否则转向第②步继续循环执行 如此循环，直到得到结果为止。 （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术。在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母?子之数，以少减多，更相减损，求其等也，以等数约之 步骤： Ⅰ．任意给出两个正数；判断它们是否都是偶数。若是，用

2约简；若不是，执行第二步。 Ⅱ．以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。 2．秦九韶算法 秦九韶算法的一般规则： 秦九韶算法适用一般的多项式f(x)=a n x n +a n-1x n-1 +….+a 1x+a 0 的求值问题。用秦九韶算法求一般多项式 f(x)=a n x n +a n-1x n-1 +….+a 1x+a 0当x=x 0时的函数值，可把n 次多项式的求值问题转化成求n 个一次多项式的值的问题，即求 v 0=a n v 1=a n x+a n －1 v 2=v 1x+a n －2 v 3=v 2x+a n －3 …….. v n =v n －1x+a 0 观察秦九韶算法的数学模型，计算v k 时要用到v k －1的值，若令v 0=a n 。 我们可以得到下面的递推公式： v 0=a n v k =v k －1+a n －k (k=1,2,…n) 这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现 3．进位制 （1）概念 进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n ，即可称n 进位制，简称n 进制。现在最常用的是十进制，通常使用10个阿拉伯数字0—9进行记数。 对于任何一个数，我们可以用不同的进位制来表示。比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。 一般地，若k 是一个大于一的整数，那么以k 为基数的k 进制可以表示为： 110() 110...(0,0,...,,) n n k n n a a a a a k a a a k --<<≤<，