当前位置：文档之家 › 高中数学人教A版必修三 1.3 算法案例 课件 (共37张PPT)

高中数学人教A版必修三 1.3 算法案例 课件 (共37张PPT)

  • 格式：pptx
  • 大小：674.03 KB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

人教版高中数学 A版 必修三 第一章 《1.3算法案例》教学课件

人教版高中数学 A版 必修三 第一章 《1.3算法案例》教学课件

D.8
解析 f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7，
∴加法6次，乘法6次，
∴6＋6＝12次，故选C.
解析答案
规律与方法
1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数， 若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除 法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最 大公约数. 2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数， 然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较 小的数相等，此时相等的两数即为原来两个数的最大公约数.
1 2345
答案
4.把89化成五进制的末尾数是( D )
A.1
B.2
C.3
1 2345
D.4
答案
5.下列各数中最小的数是 ( D )
A.85(9) C.1 000(4)
B.210(6) D.111 111(2)
1 2345
答案
ቤተ መጻሕፍቲ ባይዱ 规律与方法
1.要把k进制数化为十进制数，首先把k进制数表示成不同位上数字与k的 幂的乘积之和，其次按照十进制的运算规则计算和. 2.十进制数化为k进制数(除k取余法)的步骤：
答案
2.更相减损术的运算步骤 第一步，任意给定两个正整数，判断它们是否都是偶数 .若是，用 2 约简； 若不是，执行 第二步 . 第二步，以较大 的数减去 较小的数，接着把所得的差与 较小 的数比较， 并以大数减小数，继续这个操作，直到所得的数 相等 为止，则这个数(等 数)或这个数与约简的数的乘积就是所求的最大公约数.
解析答案
返回
达标检测
1.7不可能是( A ) A.七进制数 C.十进制数

高中数学人教版必修三：1.3算法案例ppt课件

高中数学人教版必修三：1.3算法案例ppt课件

＝ 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
＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋1 ＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1
LOOP UNTIL i>n PRINT b END
2、十进制转换为二进制
(除2取余法：用2连续去除89或所得的商， 然后取余数)
例2 把89化为二进制数
解： 根据“逢二进一”的原则，有
89＝2×44＋1
89＝2×44＋1
44＝ 2×22＋0
＝ 2× (2×22＋0)+1
22＝ 2×11＋0
11＝ 2× 5＋1 5＝ 2× 2＋1
ｆ（5）=5５＋5４＋5３＋5２＋5＋１
=（（ （（5 ＋１ ） × 5 ＋１ ） ×5 ＋１ ） × 5＋１ ） ×5 ＋１
《数书九章》——秦九韶算法
设 f ( x) 是一个n次的多项式
f(x ) a n x n a n 1 x n 1 a 1 x a 0
对该多项式按下面的方式进行改写：
第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146
结论： 8251和6105的公约数就是6105和2146的公约数，求 8251和6105的最大公约数，只要求出6105和2146的公约数 就可以了。
第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大 公约数。

(算法案例)人教版高中数学必修三教学课件(第1.3课时)

(算法案例)人教版高中数学必修三教学课件(第1.3课时)
问题：求8251和6105的最大公约数
第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146
被除数
除数
商
余数
分析：6105和2146的公约数就是8215和6105的公约数,除数和余数的公约数就是被除数和除数的公约
数。 因此，求8251和6105的最大公约数，只需求出6105和2146的公约数即可。
第九页，共二十页。
新知探究
例1：用辗转相除法求378和90的最大公约数
18
例2：用辗转相除法求1734，816和1343的最大公约数
17
第十页，共二十页。
新知探究
更相减损术
简介
更相减损术是出自《九章算术》的一种求最大公约 数的算法，它原本是为约分而设计的。 但它适用于任何需要求最大公约数的场合。
第五页，共二十页。
新知探究
思考：辗转相除法用哪种逻辑结构书写？
辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。
a =b× 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
辗转相除法求最大公约数的步骤较少，而更相减
损术运算简易，因此解题时要灵活运用.
第十八页，共二十页。
新知探究
辗转相除法与更相减损法的比较：
辗转相除法和更相减损法都是用来求两个数的最大公约数的.
区别：
辗转相除法进行的是除法运算，即辗转相除，直到余数为0为止；
更相减损术进行的是减法运算，即辗转相减，直到减数和差Hale Waihona Puke 等为止.人教版高中数学必修3

人教A版高中数学必修3课件1.3算法案例课件

人教A版高中数学必修3课件1.3算法案例课件

算法案例
【变式训练】
算法步骤： 第一步：将840进行素数分解23×3×5×7； 第二步：将1764进行素数分解22×32×72； 第三步：确定它们的公共素因数：2，3，7； 第四步：确定公共素因数2，3，7的指数分别是： 2， 1， 1； 第五步：最大公因数为22×31×71=84.
点评：质数是除１以外只能被１和本身整除 的正整数，它应该是无限多个，但是目前没 有一个规律来确定所有的质数.
算法案例
【进位制】
(1)概念 进位制是为了计数和运算方便而约定的记数系统，约定 “满几进一”就是几进制，几进制的基数（大于1的整 数）就是几. 对于任何一个数，我们可以用不同的进位制来表示。比 如：十进数57，可以用二进制表示为111001，也可以用 八进制表示为71、用十六进制表示为39，它们所代表的 数值都是一样的. 一般地，若k是一个大于一的整数，那么以k为基数的k 进制可以表示为： anan-1…a1a0(k) (0<an<k，0 ≤an-1…a1,a0<k), 而表示各种进位制数一般在数字右下脚加注来表示,如 111001(2)表示二进制数,34(5)表示5进制数.
算法案例
【典型例题】 点评：对比两种方法控制好算法的结束， 辗转相除法是到达余数为0，更相减损术 是到达减数和差相等. 2、某程序框图如图所示，该程 序运行后输出的k的值是( ) A.4 B.5 C.6 D.7
算法案例
【典型例题】 解析：对于k=0 ,s=1, ∴k=1, 而对于k=1,s=3, ∴k=2, 则 k=2,s=3+8 ,∴k=3, 后面是k=3,s=3+8+211， ∴k=4,不符合条件时输出的k=4 ． 答案 A
算法案例
【秦九韶算法】

人教版高中数学必修三课件：1.3 算法案例(共55张PPT)

人教版高中数学必修三课件：1.3 算法案例(共55张PPT)

解:用辗转相除法求最大公约数:612=468×1+144,468=144×3+36,144=36×4,即612
和468的最大公约数是36. 用更相减损术检验:612和468均为偶数,两次用2约简得153和117,153-117=36,11736=81,81-36=45,45-36=9,36-9=27,27-9=18,18-9=9,所以612和468的最大公约数为
转化为求n个一次多项式的值.
预习探究
知识点二 进位制
1.进位制:进位制是为了计数和运算方便而约定的记数系统,约定“满k进一”就 是 k进制 ,k进制的基数(大于1的整数)就是 k . 2.将k进制数化为十进制数的方法:先把k进制数写成各位上的数字与k的幂的乘积之和 的形式,再按照十进制数的运算规则计算出结果. 3.将十进制数化为k进制数的方法是 除k取余法 .即用k连续去除十进制数所得 的 商 ,直到商为零为止,然后把各步得到的余数 倒序 写出.所得到的就是相应的k 进制数. 4.k进制数之间的转化:首先转化为十进制数,再转化为 k进制数.
第一章 算法初步
1.3 算法案例 第2课时 秦九韶算法与进位制
预习探究
知识点一 秦九韶算法
1.秦九韶算法是我国南宋数学家秦九韶在他的著作《数书九章》中提出的一 个用于计算多项式值的方法. 2.秦九韶算法的方法: 把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0 改写成下列的形式: f(x)=(anxn-1+an-1xn-2+…+a1)x+a0= ((anxn-2+an-1xn-3+…+a2)x+a1)x+a0 =…=

山东省高中数学(新课标人教A版)必修三《1.3-算法案例》课件

山东省高中数学(新课标人教A版)必修三《1.3-算法案例》课件

山 东 省 高 中 数学(新 课标人 教A版 )必修三 《1.3 -算法案 例》课 件
课前探究学习
课堂讲练互动
活页规范训练
山 东 省 高 中 数学(新 课标人 教A版 )必修三 《1.3 -算法案 例》课 件
3．关于进位制应注意的问题
(1)十进制的原理是满十进一．一个十进制正整数N可以写
成an×10n＋an－1×10n－1＋…＋a1×101＋a0×100的形式， 其中an，an－1，…，a1，a0都是0至9中的数字，且an≠0.例 如365＝3×102＋6×10＋5.
山 东 省 高 中 数学(新 课标人 教A版 )必修三 《1.3 -算法案 例》课 件
课前探究学习
课堂讲练互动
活页规范训练
山 东 省 高 中 数学(新 课标人 教A版 )必修三 《1.3 -算法案 例》课 件
依次类推，即每一步的计算之后都赋予一个新值vk，即从 最内层的括号到最外层． 括号的值依次赋予变量v1，v2，…，vk，…，vn，第n步所 求值vn＝vn－1x＋a0即为所求多项式的值． (3)秦九韶算法有以下几个优点： ①大大减少了乘法的次数，使计算量减小．在计算机上做 一次乘法所需要的时间是做加法、减法的几倍到十几倍， 减少做乘法的次数也就加快了计算的速度； ②规律性强，便于利用循环语句来实现算法； ③避免了对自变量x单独做幂的计算，每次都是计算一个 一次多项式的值，从而可以提高计算的精度．
课前探究学习
课堂讲练互动
活页规范训练
2．更相减损术 第一步，任意给定两个正整数，判断它们是否都是_偶__数__．若 是，用__2约___简__；若不是，执行_第__二__步__ ． 第二步，以_较__大__的数减去_较__小__的数，接着把所得的差与 _较__小__的数比较，并以大数减小数，继续这个操作，直到所得 的数_相__等__为止，则这个数(等数)或这个数与约简的数的乘积 就是所求的最大公约数． 任意给定两个正整数，用辗转相除法和更相减损术是否 都可以求它们的最大公约数？ 提示 是．更相减损术与辗转相除法都能在有限步内结束， 故均可以用来求两个正整数的最大公约数．

人教A版高中数学必修三 1.3 算法案例 课件 (共47张PPT)

人教A版高中数学必修三 1.3 算法案例 课件 (共47张PPT)

中国剩余定理的应用 秦九韶在其名著《数书九章》中提出一则历史名题， 史称“三贼盗米问题”： 问有米铺，诉被盗去米一般三箩，皆适满，不记细 数．今左壁箩剩一合，中壁箩剩一升四合，右壁箩 剩一合，后获贼，系甲、乙、丙三名 ．甲称当夜摸 的马杓，在左壁箩舀入袋；乙称踢着木履，在中壁 箩舀入袋； 丙称摸得漆碗，在右壁箩舀入袋．将归 食用，日久不知数．索得三器，马杓满容一升九合， 木履容一升七合，漆碗容一升二合．欲知所失米数， 计赃结断三盗各几何？(注：“合”是容量单位，10 合是一升)
中点函数近似值
－0.084 0.512 0.215 0.066
－0.009 0.029 0.010 0.001
例2 用二分法求关于x的方程f(x)＝0在某有解区间[a,b]上符合 误差限制c的近似解。 算法描述 第一步 给定精确度d
第二步 确定区间[a,b],验证Байду номын сангаасf (a) • f (b) 0
引例：求f(x)=x5+x4+x3+x2+x+1在x=5时的值。
分析:可以利用前面的计算结果，以减少计算量
即先计算x2,然后依次计算 x2 x
的值.
(x2 x) x
算法2：
ｆ（5）=5５＋5４＋5３＋5２＋5＋１
((x2 x) x) x
=5×（5４＋5３＋5２＋5＋１） ＋１
=5×（5×（5３＋5２＋5 ＋１ ）＋１ ） ＋１ =5×（5×（ 5× （5２＋5 ＋１） ＋１ ）＋１ ） ＋１ =5×（5×（ 5× （5× （5＋１ ） ＋１ ） ＋１ ）＋１ ） ＋１
问:上面算法中,共用了多少次乘法和加法?
计算多项式ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值

高中数学人教A版必修三1.3【教学课件】《算法案例》人教版

高中数学人教A版必修三1.3【教学课件】《算法案例》人教版
人民教育出版社 | 必修三
第一章 · 算法初步
第一课时
《 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

人教A版高中数学必修三课件1.3算法案例3.ppt

人教A版高中数学必修三课件1.3算法案例3.ppt
10b1（2）=1×23+b×2+1=2b+9. a02（3）=a×32+2=9a+2. 所以2b+9=9a+2，即9a-2b=7. 故a=1，b=1.
将k进制数a转换为十进制数(共有 n位)的程序
a=anan-1… a3a2a1(k)
=ank(n-1)+an-1k(n-2)+ … + a3k2 +a2k1+a1k0
完整的过程
例2 用辗转相除法求225和135的最大公约数
8251=6105×1+2146
225=135×1+90
6105=2146×2+1813
135=90×1+45
2146=1813×1+333 1813=333×5+148
90=45×2
显然45是90和45的最大公约数，也就是 225和135的最大公约数
要求多项式的值，应该先算最内层的一次多项式的值，即
v0 an
vk vk 1x ank
v1 an x an1
然后，由内到外逐层计算一次多项式的值，即
v2 v1x an2 v3 v2 x an3
vn vn1x a0
最后的一项 是什么？
这种将求一个n次多项式f（x）的值转化成求n个 一次多项式的值的方法，称为秦九韶算法。
这实际上是一个循环结构。
m=n×q＋r
用程序框图表示出右边的过程
8251=6105×1+2146
r=m MOD n m=n n=r
r=0?
否
是
INPUT m , n DO
6105=2146×2+1813
r=m mod n m=n

高中数学人教A版必修3第一章1.3算法案例课件

高中数学人教A版必修3第一章1.3算法案例课件

去
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个数学问题及其 解法，是当时世界上最简练 有效的应用数学，它的出现 标志中国古代数学形成了完 整的体系。

人教a版必修三：《1.3算法案例(1)》ppt课件(322页)

人教a版必修三：《1.3算法案例(1)》ppt课件(322页)

明目标、知重点
填要点、记疑点
主目录
探要点、究所然
当堂测、查疑缺
探要点、究所然
§1.3（一）
探究点二：更相减损术
思考 2 (1)用更相减损术可以求两个正整数 m，n 的最大公约数，那么用什么逻辑结 构来构造算法？其算法步骤如何设计？
答 (1)用循环结构设计算法，算法如下：
第一步，任意给定两个正整数m，n(m>n)． 第二步，计算 m－n 所得的差 k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示． 第四步，若m＝n，则m，n的最大公约数等于m；否则，返回第二步．
第一章 算法初步
§1.3 算法案例(一)
本节知识目录
§1.3（一）
明目标、知重点
算法 案例 (一)
填要点、记疑点
探究点一 探究点二 探究点三
辗转相除法 更相减损术 秦九韶算法的基本思想
探要点、究所然
当堂测、查疑缺
明目标、知重点
填要点、记疑点
主目录
探要点、究所然
当堂测、查疑缺
明目标、知重点
§1.3（一）
明目标、知重点
填要点、记疑点
主目录
探要点、究所然
当堂测、查疑缺
探要点、究所然
§1.3（一）
探究点二：更相减损术
(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？
答 程序框图： 程序：
INPUT m，n WHILE m< >n k＝m－n IF n>k THEN m＝n n＝k ELSE m＝k END IF WEND PRINT m END
明目标、知重点 填要点、记疑点
主目录
探要点、究所然
当堂测、查疑缺

1.3 算法案例 课件(36张PPT)高中数学必修3(人教版A版)

1.3 算法案例 课件(36张PPT)高中数学必修3(人教版A版)

正解: f(x)=3x4+0· x3+2x2+4x+2=(((3x+0)x+2)x+4)x+2, v1=3×(-2)+0=-6; v2=-6×(-2)+2=14; v3=14×(-2)+4=-24; v4=-24×(-2)+2=50. 故f(-2)=50.
反思利用秦九韶算法计算多项式的值的关键是能正确地将所给多项 式改写,依次计算一次多项式,由于后项计算用到前项的结果,故应认真、 细心,确保中间结果的准确性.若在多项式中有几项不存在,可将这些项的 系数看成0,即把这些项看成0· xn.
列表 2 x=5 2
-5 10 5
0 -4 25 125 25 121
求多项式的值
【例2】 用秦九韶算法求多项式 f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x 当x=3时的值.
分析:解决本题首先需要将原多项式化成 f(x)=((((((7x+6)x+5)x+4)x+3)x+2)x+1)x的形式,其次再弄清 v0,v1,v2,…,v7分别是多少,再针对这些式子进行计算.
《数书九章》——秦九韶算法
设 f ( x) 是一个n 次的多项式
f ( x) an x n an 1 x n 1 a1 x a0
对该多项式按下面的方式进行改写：
f ( x) an x n an 1 x n 1 a1 x a0
(an x n 1 an 1 x n 2 a1 ) x a0
10221(3)=1×34+0×33+2×32+2×31+1×30

高中数学人教A版必修三第一章1.3.3进位制-算法案例课件

高中数学人教A版必修三第一章1.3.3进位制-算法案例课件

把89化为五进制的数.
5 89 5 17 53
0
余数
4 2 3
∴ 89=324(5)
练习：把3282化为16进制的数.
10
11
12
13
14
15
A
B
C
D
E
F
思考 你会把三进制数10221(3)化为二进制数吗?
解:第一步:先把三进制数化为十进制数: 10221(3)=1×34+0×33+2×32+2×31+1×30
51
把89化为二进制的数.
2 89
2 44 2 22 2 11 25
22 21
0
余数
1 0 0 1 1 0 1
把算式中各步所得的余 数从下到上排列,得到
89=1011001(2) 可以用2连续去除89或所得 商(一直到商为0为止),然后 取余数---除2取余法.
这种方法也可以推广为把 十进制数化为k进制数的 算法,称为除k取余法.
=81+18+6+1=106. 第二步:再把十进制数化为二进制数:
106=1101010(2). ∴10221(3)=106=110就是几，基数都是大于1的数.
按照十进制数的运算规则计算出结果， 结果就是十进制下该数的大小了.
1.3算法案例
进位制
十进制数3721中的3表示3个千,7表示7个百,2表示2个 十,1表示1个一,从而它可以写成下面的形式:
3721=3×103+7×102+2×101+1×100.
同理: 3421(5)= 3×53+4×52+2×51+1×50.
每一位上的数都是整数.

人教A版高中数学必修3第一章1.3 算法案例课件

人教A版高中数学必修3第一章1.3 算法案例课件
r =m MOD n m=n n=r WEND PRINT m END
问题提出：除了用上述算法求两个数的最大公 约数之外还有没有别的算法？
点拨：用“更相减损术”：更相减损术，是 我国数学家刘徽的专著《九章算术》中记 载的．更相减损术求最大公约数的步骤如 下：可半者半之，不可半者，副置分母分 子之数，以少减 多，更相减损，求其等也.， 以等数约之．
148 37 4
(148,37) 37
(8251,6105) (148,37) 37
所以
完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333
探究1：用辗转相除法求225 和135的最大公约数
225=135×1+90
135=90×1+45
关于辗转相除法的算理问题
m n q r (0 r n) 若r 0,则(m, n) n 若r 0,则(m, n) (n, r)
以上满足：m, n, q N, r N
例题讲解
例1：用辗转相除法求8251与6105的 最大公约数．
8251 61051 2146 (8251, 6105) (6105, 2146)
1.3.1算法案例
辗转相除法与更相减损术
算法的历史背景
人类最早关于算法的记录是在两河流域发现的公元前两三 千年的黏土板，其中一个典型的例子就是计算利息何时能 够等于本金。在公元前2100年左右，美索不达米亚人已有 了乘法表，其中使用着六十进位制的算法。
算法早期发展中值得一提的是公元前300年古希腊数学家 欧几里得提出的欧几里得算法（辗转相除法），用来求两 个正整数的最大公约数。
（2）二者的实质都是递推的过程.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

开始
输入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
11001(2) 1 24 1 23 0 22 0 21 1 20
二、二进制与十进制的转换
1、二进制数转化为十进制数 例1 将二进制数110011(2)化成十进制数
解： 根据进位制的定义可知
110011( 2) 1 25 1 24 0 23 0 22 1 21 1 20
结论： 8251和6105的公约数就是 2146=1813×1+333 6105和2146的公约数，求8251和 6105的最大公约数，只要求出6105 1813=333×5+148 和2146的公约数就可以了。 333=148×2+37 第二步 对6105和2146重复第一步 的做法 148=37×4+0 6105=2146×2+1813 显然37是148和37的最大公约数， 同理6105和2146的最大公约数也 也就是8251和6105的最大公约数 是2146和1813的最大公约数。
例2 已知一个五次多项式为
f ( x) 5x5 2 x 4 3.5x3 2.6 x 2 1.7 x 0.8
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 3451.2 v5 3451.2 5 0.8 17255.2
3721 3 103 7 10 2 2 101 1100
其它进位制的数又是如何的呢？
2、 二进制
（１）二 进制的表 示方法
十进制是用0、1、2、3、4、5、6、7、 8、9十个数来描述的，二进制是用0、1 两个数字来描述的。如11001等 区分的写法：11001（2）或者（11001）2
要求多项式的值，应该先算最内层的一次多项式的值，即
v1 an x an 1
然后，由内到外逐层计算一次多项式的值，即
v2 v1 x an 2
v3 v2 x an 3

vn vn 1 x a0
这种将求一个n次多项式f（x）的值转化成求n个一次多项 式的值的方法，称为秦九韶算法。
所以89＝2×（2×（2×（2×（2 × 2 ＋1）＋1）＋0）＋0）＋1
＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋1 ＝2×（2×（2×（23＋2＋1）＋0）＋0）＋1 ＝2×（2×（24＋22＋2＋0）＋0）＋1 ＝2×（25＋23+22＋0＋0）＋1 ＝26＋24+23＋0＋0＋21 89＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20
((an x n2 an1 x n3 a2 ) x a1 ) x a0
((an x an 1 ) x an 2 ) x a1 ) x a0
f ( x) ((an x an 1 ) x an 2 ) x a1 ) x a0
探究一：辗转相除法
思考一：在小学里我们是如何救出两个正整数的最大公约数的？ 算法案例之求最大公约数
例：求１８与24的最大公约数
解：２ １８ ３ ９ ２４ １２ 用公有质因数２除 用公有质因数３除
短除法
３ ４ ３和４互质，不除了 得：１８和２４的最大公约数：２x３＝６
思考2:对于8251与6105这两个 想一想， 数，它们的最大公约数是多少？ 如何求 你是怎样得到的？ 由于它们公有的质因数较大， 8251与 6105的 利用上述方法求最大公约数就 最大公 比较困难.有没有其它的方法可 约数？ 以较简单的找出它们的最大公 约数呢？ 思考3：注意到 8251=6105×1+2146，那么 8251与6105这两个数的公约数 和6105与2146的公约数有什么 关系？
情境创设
韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫 士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数, 就能知道场上的士兵的人数,韩信先令士兵排成3列纵队,结果有2 人多余,接着下令排成5列纵队,结果又多出3人,随后他又下令改 为7列纵队,这次又剩下2人无法成整行.在场的人都哈哈大笑,以 为韩信不能清点出准确的人数,不料笑声刚落,韩信高声报告共有 士兵2333人.众人听了一楞,不知道韩信用什么方法这么快就能得 到正确的结果的.今天,我们将以这些古典案例的思想,设计出适 宜计算机的运行程序,提高我们对基本算法结构和算法语句在实 际中的运用能力.
设 f ( x) 是一个n次的多项式
f ( x) an x n an 1 x n 1 a1 x a0
对该多项式按下面的方式进行改写：
f ( x) an x n an 1 x n 1 a1 x a0
(an x n 1 an 1 x n 2 a1 ) x a0
用秦九韶算法求这个多项式当x=-2时的值。 2、已知多项式f(x)=2x4-6x3-5x2+4x-6
用秦九韶算法求这个多项式当x=5时的值。
课堂小结： 1、秦九韶算法的方法和步骤 2、秦九韶算法的程序框图
一、进位制
1、我们 了解十进 制吗？所 谓的十进 制，它是 如何构成 的？
十进制由两个部分构成 第一、它有0、1、2、3、4、5、6、7、8、9 (用10个数字来记数，称基数为10) 十个数字； 第二、它有“权位”，即从右往左为个位、十位、 百位、千位等等。 例如：3721 表示有：1个1，2个十， 7个百即7个10的平方， 3个千即3个10的立方
复习引入: 1、求两个数的最大公约数 的两种方法分别是（ ）和 ( ).
2、两个数21672，8127
的最大公约数是( A.2709 C.2703 B.2606 D.2706 )
新课讲解:
例1 计算多项式ｆ（ｘ） =ｘ５ 算法2： ４ ３ ２ 案例2： ＋ｘ ＋ｘ ＋ｘ ＋ｘ＋１当x ｆ（5）=5５＋5４＋5３＋5２＋5＋１ =5×（5４＋5３＋5２＋5＋１） ＋１ 秦九韶 = 5的值 算法1： =5×（5×（5３＋5２＋5 ＋１ ）＋ 算法 因为ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３ １） ＋１ ＋ｘ２＋ｘ＋１ =5×（5×（ 5× （5２＋5 ＋１） 所以 ＋１ ）＋１ ） ＋１ =5×（5×（ 5× （5 × （5 ＋ f(5)=5５＋5４＋5３＋5２＋5＋１ =3125＋625＋125＋25＋5＋１ １ ） ＋１ ） ＋１ ）＋１ ） ＋ １ = 3906
用秦九韶算法求这个多项式当x = 5的 值。 解： 将多项式变形：
f ( x) (((( 5 x 2) x 3.5) x 2.6) x 1.7) x 项式当x = 5时的值：
你从中看到了怎 样的规律？怎么 用程序框图来描 述呢？
所以，当x = 5时，多项式的值等于 17255.2
1 32 116 1 2 1 51
所以，110011（2）=51。
练习 将下面的二进制数化为十进制数？ （1）11 （2）111 （3）1111 （4）11111
2、十进制转换为二进制(除2取余法：用2连续去除89或所得的商，然后取余数)
例2 把89化为二进制数 根据“逢二进一”的原则，有 89＝2×44＋1 44＝ 2×22＋0 22＝ 2×11＋0 11＝ 2× 5＋1 5＝ 2× 2＋1 89＝2×44＋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
《九章算术》——更相减损术 算理：可 半者半之， 不可半者， 副置分母、 子之数， 以少减多， 更相减损， 求其等也， 以等数约 之。
第一步：任意给 顶两个正整数； 判断他们是否都 是偶数。若是， 则用2约简；若不 是则执行第二步。 第二步：以较大的数 减较小的数，接着把 所得的差与较小的数 比较，并以大数减小 数。继续这个操作， 直到所得的减数和差 相等为止，则这个等 数就是所求的最大公 约数。