高中数学算法案例课件新人教A版35页PPT

开始
输入f (x)的系数： a0、a1、a2、a3、a4、a5
输入x0
n=0
v=a5
v= v· x0+a5-n
n=n+1
n < 5? 否 输出v 结束
是
秦九韶算法的特点：
通过一次式的反复计算，逐步得出高次 多项式的值，对于一个n次多项式，只需做n 次乘法和n次加法即可。
练习：
1、已知多项式f(x)=x5+5x4+10x3+10x2+5x+1
所以：89=1011001（2）
2、十进制转换为二进制(除2取余法：用2连续去除89或所得的
商，然后取余数)
注意： 1.最后一步商为0， 2.将上式各步所得 的余数从下到上排 列，得到： 89=1011001（2）
2 89 48 2 22 2 2 11 2 5 2 2 2 1 0
余数 1 0 0 1 1 0 1
练习 将下面的十进制数化为二进制数？ （1）10 （2）20 （3）128 （4）256
2、十进制转换为其它进制
例4 把89 化为五进 制数 解：根据除k取余法 以5作为除数，相应的除法算式为： 5 5
数为0
思考2：辗转相 用程序框图表示出右边的过程 除法中的关键 r=m MOD n 步骤是哪种逻 辑结构？ m=n 辗转相除法中 n=r 的关键步骤是哪 r=0? 种逻辑结构？辗 否 是 转相除法是一个 反复执行直到余 数等于0停止的 步骤，这实际上 是一个循环结构。
m=n×q＋r
8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0

否
333=148×2+37 148=37×4+0
思考：你能把辗转相除法编成一入m,n
r=m MOD n m=n
n=r 否
r=0? 是
输出m 结束
程序：
INPUT “m,n=”;m,n DO
r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
第一章 算法初步 1.3 算法案例
辗转相除法与更相减损术
例：求下面两个正整数的最大公约数：
（1）求25和35的最大公约数 （2）求49和63的最大公约数
（1）5 25 35 57
所以，25和35的最大公 约数为5
（2）7 49 63 79
所以，49和63的最大公 约数为7
思考：除了用这种方法外还有没有其它方法？
( ( a n x a n 1 ) x a n 2 ) x a 1 ) x a 0
f ( x ) ( ( a n x a n 1 ) x a n 2 ) x a 1 ) x a 0
要求多项式的值，应该先算最内层的一次多项式的值，即
v1anxan1
然后，由内到外逐层计算一次多项式的值，即
（4）用秦九韶算法求多项式的值，与多项式组成有直接关 系吗？用秦九韶算法计算上述多项式的值，需要多少次乘
？ 法运算和多少次加法运算
计算只与多项式的 系数有关，
《数书九章》——秦九韶算法
设f (x) 是一个n 次的多项式
这是怎样
f(x ) a n x n a n 1 x n 1 a 1 x a 0 对该多项式按下面的方式进行改写：
完整的过程
例： 用辗转相除法求225和135
8251=6105×1+2146 的最大公约数 225=135×1+90

知识探究（二）:算法的步骤设计 人教A版高中数学必修3第一章.1算法的概念课件
思考32::设计一个算法，判断8 3975是否为质数。
第一步，用2除783，95 得到余数1,因为余数不为0，所 以2不能整除738.59 第二步，用3除738，59 得到余数2,因为余数不为0，所 以3不能整除783.95
人教A版高中数学必修3第一章.1算法 的概念 课件
算法设计: 第一步， 第二步， 第三步，
第四步，
人教A版高中数学必修3第一章.1算法 的概念 课件
在中央电视台幸运52节目中,有一个猜商品 价格的环节,竟猜者如在规定的时间内大体猜出 某种商品的价格,就可获得该件商品.现有一商品, 价格在0～2000元之间,采取怎样的策略才能在较 短的时间内说出正确(大体上)的答案呢?
第三步，用4除738，59 得到余数31,因为余数不为0，所 以4不能整除783.95
第…四…步，用5除73，5 得得到到余余数数20,，因因为为余余数数不为为00, ，所
以以第55八能不十整能七除整步3除5，.7用88除89，得到余数1,因为余数不
第所为五 以 0，因因步6不所此，此能以，用，整8683除除不85不977能是.，是整得质质除到数8数余9..。数1,因因为此余，数7是不为质0数，. 人教A版高中数学必修3第一章.1算法 的概念 课件
以3不能整除73.5
第三步，用4除73，5 得到余数3,因为余数不为0，所 以4不能整除73.5
第四步，用5除73，5 得得到到余余数数20,，因因为为余余数数不为为00, ，所 以以55能不整能除整3除5.7
第五步，用6除7，得到余数1,因为余数不为0，
所以6不能整除7.
因此，7是质数.
人教A版高中数学必修3第一章.1算法 的概念 课件

44＝2×22＋0 22＝2×11＋0 11＝2×5＋1 5＝2×2＋1
＝2×(2×22＋0)+1 ＝2×(2×(2×11＋0)+0)+1 ＝2×(2×(2×(2×5＋1)+0)+0)+1
＝2×(2×(2×(2×(2×2＋1)+1)+0)+0)+1
所以89＝2×（2×（2×（2×（2×2＋1）＋1）＋0）＋0）＋1
其它进制：
实际上，十进制数只是计数法中的一种，但它不是唯一 记数法。除了十进制数，生产生活中还会遇到非十进制的 记数制。如时间：60秒为1分，60分为1小时，它是六十进 制的。两根筷子一双，两只手套为一副，它们是二进制的。
二进制、七进制、八进制、十二进制、 六十进制……
二进制只有0和1两个数字，七进制用0~6七个数字 十六进制有0~9十个数字及ABCDEF六个字母.
(2)程序框图:
开始 输入a,k,n
b=0 i=1
把a的右数第i位数字赋给t
b=b+t*ki-1
i=i+1 否
i>n?
是 输出b 结束
2、十进制转换为二进制
方法：除2取余法，即用2连续去除89或所得的商，然后取余数。
例、把89化为二进制数
解：根据“逢二进一”的原则，有
89＝2×44＋1
89＝2×44＋1
k
0 (10)
其它进制数化成十进制数公式
例2、设计一个算法，将k进制数a(共有n位)转换为十进制 数b。
(1)算法步骤: 第一步，输入a,k和n的值； 第二步，将b的值初始化为0,i的值初始化为1；
第三步，b=b+ai*ki-1,i=i+1

[解] (1)辗转相除法： 779＝209×3＋152， 209＝152×1＋57， 152＝57×2＋38， 57＝38×1＋19， 38＝19×2. 所以，779 与 209 的最大公约数为 19.
[类题通法] 1．用辗转相除法求最大公约数的步骤
秦九韶算法及其应用
[例 2] 用秦九韶算法求多项式 f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x
为 642.
进位制
[例 3] (1)将 101 111 011(2)转化为十进制数； (2)将 235(7)转化为十进制数； (3)将 137(10)转化为六进制数； (4)将 53(8)转化为二进制数． [解] (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)235(7)＝2×72＋3×71＋5×70＝124(10)．
2.利用秦九韶算法求值的易错点
[典例] 利用秦九韶算法求 f(x)＝x5＋x3＋x2＋x＋1 当 x＝3
时的值
()
A．121
B．283
C．321
D．239
[随堂即时演练]
1．在对 16 和 12 求最大公约数时，整个操作如下：16－12＝4,12 －4＝8,8－4＝4.由此可以看出 12 和 16 的最大公约数是( )
当 x＝2 时的值． [解] f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x， 当 x＝2 时，有 v0＝6， v1＝6×2＋5＝17， v2＝17×2＋4＝38， v3＝38×2＋3＝79， v4＝79×2＋2＝160， v5＝160×2＋1＝321， v6＝321×2＝642， 故当 x＝2 时，多项式 f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x 的值

思考：从上述的过程你体会
完整的过程 8251=6105×1+2146
例2 用辗转相除法求225和135的最大公约数 225=135×1+90
6105=2146×2+1813
135=90×1+45
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
显然37是148和37的最大 公约数，也就是8251和 6105的最大公约数
333=148×2+37 148=37×4+0
算法2：
程序： INUPU m,n DO
r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
开始 输入m,n
r=m MOD n m=n n=r
否
r=0?
是
输出m 结束
算法1： 程序： INUPU m,n IF m<n THEN x=m m=n n=x END IF DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
观察求8251和6105的最大公约数的过程
第一步 用两数中较大的数除以较小的数，求得商和 余数 8251=6105×1+2146 结论： 8251和6105的公约数就是6105和2146的 公约数，求8251和6105的最大公约数，只要求出 6105和2146的公约数就可以了。 为什么呢？
第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813 的最大公约数。
较大那个除以较小那个，求得

新课标人教A版高中数学必修3第一章1 .3.1算 法案例 (1) 课件(共17张PPT)
新课标人教A版高中数学必修3第一章1 .3.1算 法案例 (1) 课件(共17张PPT)
（3）程序框图 （4）程序
INPUT “m,m=”;m,n DO
r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
新课标人教A版高中数学必修3第一章1 .3.1算 法案例 (1) 课件(共17张PPT)
（2）算法步骤 第一步：输入两个正整数m,n(m>n). 第二步：计算m除以n所得的余数r. 第三步：m=n,n=r. 第四步：若r＝0,则m,n的最大公约数等 于m；否则转到第二步. 第五步：输出最大公约数m.
m=n
r< >0? 是 否
输出n
程序
INPUT “m,n=”;m,n r=m MOD n WHILE r< >0
m=n n=r r=m MOD n WEND PRINT n END
结束
新课标人教A版高中数学必修3第一章1 .3.1算 法案例 (1) 课件(共17张PPT)
新课标人教A版高中数学必修3第一章1 .3.1算 法案例 (1) 课件(共17张PPT)
数学必修③
1.3 算法案例(1) 辗转相除法与更相减损术
1. 回顾算法的三种表述： 自然语言
程序框图 （三种逻辑结构） 程序语言 （五种基本语句） 2. 思考： 小学学过的求两个数最大公约数的方法？
先用两个公有的质因数连续去除，一直除到所得的 商是互质数为止，然后把所有的除数连乘起来.
1、求两个正整数的最大公约数 求18和30的最大公约数
新课标人教A版高中数学必修3第一章1 .3.1算 法案例 (1) 课件(共17张PPT)

第二步: 以较大的数减去较小的数，接着把 较小的数与所得的差比较，并以大数减小数。继 续这个操作，直到所得的数相等为止，则这个数 （等数）就是所求的最大公约数。
例2 用更相减损术求98与63的最大公约数. 解: 由于63不是偶数，把98和63以大数
减小数，并辗转相减，
即: 98－63＝35; 63－35＝28; 35－28＝7; 28－7＝21; 21－7＝14; 14－7＝7.
〖研探新知〗
1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 解: 8251＝6105×1＋2146;
6105＝2146×2＋1813; 2146＝1813×1＋333; 1813＝333×5＋148; 333＝148×2＋37; 148＝37×4＋0. 则37为8251与6105的最大公约数。
（c）情感态度与价值观 1.通过阅读中国古代数学中的算法案例，体会中
国古代数学对世界数学发展的贡献。 2.在学习古代数学家解决数学问题的方法的过程
中培养严谨的逻辑思维能力，在利用算法解决数学问题 的过程中培养理性的精神和动手实践的能力。 二、教学重难点
重点: 理解辗转相除法与更相减损术求最大公约数 的方法。
解法二:列表
原多项式 的系数
2 -5 -4 3 -6 7
x=5
10 25 105 540 2670
2 5 21 108 534 2677
所以,当x=5时,多项式的值是2677. 多项式
的值.
练一练:用秦九韶算法求多项式 f(x)=2x6-5x5-4x3+3x2-6x当x=5时的值.
解:原多项式先化为:
[问题]画出程序框图,表示用秦九韶算法求5次多 项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0 (x0是任意实数)时的值的过程,然后写出程序.

人民教育出版社 | 必修三
第一章 · 算法初步
第一课时
《 1.3 秦九韶算法与进位制》
人民教育出版社 | 必修三
新课导入
设计求多项式 f ������ = 2������ 5 − 5������ 4 − 4������ 3 + 3������ 2 − 6������ + 7 当 x=5 时的值的算法程序。 x=5
人民教育出版社 | 必修三
思考1：怎么用秦九韶算法求多项式的值。
通过
������0 = ������������ ������������ = ������������−1 ������ + ������������ −������
(k=1,2,……n)这是一个在秦九韶算
法中反复执行的步骤，因此可用循环结构来实现。
一般地,对于一个n次多项式 然后由内向外逐层计算一次多项式的值，即
������2 = ������1 ������ + ������������−2 , ������3 = ������2 ������ + ������������−3 ,…������������ = ������������−1 ������ + ������0
人民教育出版社 | 必修三
思考4：十进制数怎么转化成k进制数？ 其方法是除k取余法，用十进制数除以k进制 数，将各步所得的余数从下到上排列，就会 得到相应的k进制数。
人民教育出版社 | 必修三
例题讲解
例1： 求多项式 ������ ������ = ������ 5 − ������ 3 + 2������ 2 − 3 在 ������ = 5 时的函数值。 解：原多项式先化为:
y=2*x^5-5*x^4-4*x^3+3*x^2-6*x+7

去
9－ 3= 6
6 － 3 = 3 减数与差相等
3×2=6
78与36的最大公约数为6.
更相减损术
问题6.根据更相减损术的过程，设计求两个正整数m，n最 大公约数的算法，需要用到什么逻辑结构？为什么？
第一步：任意给定两个正整 算法分析：
数，判断它们是否都是偶数。第一步，给定两个正整数m，n(m>n).
更相减损术
例2. 用更相减损术求78与36的最大公约数.
解： 78与36都是偶数
“可半”
78 ÷ 2 = 39 36 ÷ 2 = 18
“可半者半之”
除 完
39 － 18 = 21 大减小 21 － 18 = 3
再
18 － 3 = 15
乘
15 － 3 = 12
“更相减损”（辗转相减）
回
12 － 3 = 9
2 18 30 3 9 15 35
18与30的最大公约数为2 3 6 .
问题1. 求8251与6105的最大公约数. 可以使用短除法吗？
困难：两数比较大、公约数不易视察。 （辗转相除法、更相减损术）
知问
思考1：辗转相除法与更相减损术可以用来解 决什么问题？ 可以解决求两个正整数最大公约数的任何问题。
《九章算术》——更相减损术
“可半者半之，不可半者，副置分母、子之数，以少 减多，更相减损，求其等也，以等数约之。”
《九章算术》
刘徽
《九章算术》其作者已不可 考，现今流传的大多是在三 国时期刘徽为《九章》所作 的注本。它是中国古代第一 部数学专著，系统总结了战 国、秦、汉时期的数学成绩， 收录了246个数学问题及其 解法，是当时世界上最简练 有效的应用数学，它的出现 标志中国古代数学形成了完 整的体系。

2.若二进制数1 00y 011和八进制数x03相等，求x+y的值. 解：1 00y 011（2）＝1×26+y×23+1×2+1＝67+8y， x03（8）＝x×82+3＝64x+3，∴ 8y+67＝64x+3. 由y可取0，1，x可以取1，2，3，4，5，6，7， 得y＝0时，x＝1；y＝1时， 64x＝72无整数解. ∴ x+y＝1.
除k取余法的注意事项： （1）要连续除，用k连续去除十进制数或所得的商，直到商为零为止； （2）倒着写，把各步得到的余数倒写（即从下到上排列）就是相应 的k进制数.
训练题
1.（1）将101 111 011（2）转化为十进制数； （2）将235（7）转化为十进制数； （3）将137转化为六进制数； （4）将53（8）转化为二进制数.
◆求最大公约数的方法 （1）利用辗转相除法求给定的两个数的最大公约数，即利用带余除 法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较 小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这 时的较小数就是原来两个数的最大公约数. （2）利用更相减损术求两个正整数的最大公约数的一般步骤是：首 先判断两个正整数是否都是偶数.若是，用2约简.若不是，以较大的数 减去较小的数，接着把所得的差与较小的数比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数 与约简的数的乘积就是所求的最大公约数.
1.3 算法案例
学习目标
了解中国古代及西方数学中辗转相除法、更相减损术、秦九韶算 法及进位制等几个典型的算法案例，理解其中所包含的算法思想 ，体会中国古代数学对世界数学发展的贡献.
重点：以三个典型的算法案例为载体，经历算法设计的过程，进 一步体会算法的基本思想，感受算法在解决实际问题中的重要作 用. 难点：提炼出算法中的循环结构，并用程序框图和算法语句表示 出来.

高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
Байду номын сангаас
高一数学
例2（1）设计算法，判断7是否质数. （2）设计算法，判断35是否质数.
高中数学人教A版必修 算法的概念 课件
例2（1）设计算法，判断7是否质数. （2）设计算法，判断35是否质数.
分析：根据质数的定义，可以这样判断： 依次用2~6去除7如果它们中有一个数能 整除7，则7不是质数，否则7是质数.
高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件
高中数学人教A版必修 算法的概念 课件 高中数学人教A版必修 算法的概念 课件

返回
【评析】辗转相除法是当大数被小数除尽时,结束 除法运算,较小的数就是最大公约数;更相减损术是当大 数减去小数的差等于小数时停止减法,较小的数就是最 大公约数.
返回
用辗转相除法求80与36的最大公约数,并用更相减损术检 验所得结果.
解：用辗转相 除:80=36×2+8,36=8×4+4,8=4×2+0;用更相减损术 检验:80-36=44,44-36=8,36-8=28,28-8=20, 20-8=12,12-8=4,8-4=4.故80和36的最大公约数是4.
返回
2.求多项式f(x)=x5+5x4+10x3+10x2+5x+1当x=-2时 的值【.分析】本题考查秦九韶算法.
【解析】解：先改写多项式,再由内向外计算. f(x)=x5+5x4+10x3+10x2+5x+1
=((((x+5)x+10)x+10)x+5)x+1.
而x=-2,所以有:
v0=1,v1=v0x+a4=1×(-2)+5=3, v2=v１x+a3=3×(-2)+10=4, v3=v2x+a2=4×(-2)+10=2, v4=v3x+a1=2×(-2)+5=1, v5=v4x+a0=1×(-2)+1=-1. 所以当x=-2时，多项式的值为-1.
返回
【评析】利用秦九韶算法计算多项式的值关键是能正确地 将所给多项式改写,然后由内向外逐次计算,由于后项计算 需用到前项的结果,故应认真、细心,确保中间结果的准确 性.
返回
已知一个5次多项式为:f(x)=5x5+2x4+3.5x32.6x2+1.7x-0.8,用秦九韶算法求这个多项式当x=5时的 值.