当前位置：文档之家 › 1.3算法案例-完整PPT课件

1.3算法案例-完整PPT课件

  • 格式：ppt
  • 大小：782.00 KB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

1.3算法案例(进位制)(yong)

1.3算法案例(进位制)(yong)
满十二进一，就是十二进制； 满六十进一，就是六十进制
思考：生活最常见的进位制是什么？除此之外还有
哪些常见的进位制？请举例说明． • 最常见的进位制应该是我们数学中的十进制,比 如一般的数值计算，但是并不是生活中的每一种 数字都是十进制的. • 古人有半斤八两之说，就是十六进制与十进制的 转换. • 比如时间和角度的单位用六十进制, 计算“一打” 数值时是12进制的。 • 电子计算机用的是二进制 。
思考：其它进制是否也有类似的规律呢？
八进制
7342（8） =783+382+48+2 110011（2）=125+124+023 +022+12+1
二进制
一般地，若k是一个大于1的整数，那么以k为基 数的k进制可以表示为以下形式：
a n a n 1 a 1 ( k ) ( 0 a n k , 0 a 1 , , a n 1 k ).
a×82+b×8+c=c×72+b×7+a，得：63a+b﹣48c=0， b=3（16c﹣21a）， 由此知b是三的倍数，且是整数, ∴b=0，3，6， 21 a 当b=0时，可得c= 1 6 又1≤a≤6，检验知，不存在符合条件的a使得c是整数，
当3时,得c=
当b=6时,得c=
21a 1 16
开始
输入a ,k,n b=0 i=1
把a的右数第i位数字赋给t b=b+t*ki－1 i=i+1
否
i＞n
是
输出结果b 结束
三、十进制化为k进制 思考：既然，k进制转化为十进制有前述的方法与 相应的算法，那么十进数又是如何才能转化为k进 数呢？ 回想：a=anan-1…a2a1（k） =ankn-1+an-1kn-2+ …+a2k+a1 =b

(人教a版)必修三同步课件：1.3算法案例

(人教a版)必修三同步课件：1.3算法案例

故加法次数要减少一次，为5－1＝4.故选D.
要点三 进位制
例3 (1)把二进制数1110011(2)化为十进制数．
(2)将8进制数314706(8)化为十进制数．
解
(1)1110011(2)＝1×26＋1×25＋1×24＋0×23＋0×22＋
1×21＋1＝115. (2)314706(8)＝3×85＋1×84＋4×83＋7×82＋0×81＋6×80 ＝104902.所以，化为十进制数是104902.
所以80与36的最大公约数为4.
要点二
例2
秦九韶算法
已知一个5次多项式为f(x)＝4x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个
多项式当x＝5时的值．
解
将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－
0.8， 由内向外依次计算一次多项式当x＝5时的值： v0＝4；
2．注意：当多项ห้องสมุดไป่ตู้中n次项不存在时，可将第n次项看作0· xn.
跟踪演练2
用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算 ( )
的次数分别为
A．5，4 B．5，5 C．4，4 D．4，5 答案 D
解析
n次多项式需进行n次乘法；若各项均不为零，则需进
行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，
v2x＋an－3
vn－1x＋a0 n个一次多项式
4．进位制
运算方便 进位制是人们为了_____和_________ k进一”就是k进制，k进 计数 而约定的记数系统，“满
制的基数是k.把十进制转化为k进制数时，通常用除k取余法．

人教版高中数学必修三课件：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 =…=

数学必修ⅲ人教新课标1.3算法案例-进位制课件解读

数学必修ⅲ人教新课标1.3算法案例-进位制课件解读
数学必修Ⅲ人教新课标课 件
1.3.3
《算法案例-进位制》
• 了解各种进位制与十进制之间转换的规律，会 教学目标 利用各种进位制与十进制之间的联系进行各种 进位制之间的转换. • 教学重点 ： 各进位制表示数的方法及各进位制之间的 转换 。
一、K进位制数的表示
进位制是人们为了计数和运算方便而约定的计数 系统。
例6 把89化为五进制数
பைடு நூலகம்89=324（5）
练习：课本P45
3
四、K1进制数与K2进制数之间的转化
先由K1进制数转化为十进制数 再由十进制数转化为K2进制数
练习：课本P48
3（2）（4）
一、进位制
小结
anan1 a1a0(k ) (0 an k,0 an1, , a1, a0 k ).
为了区分不同的进位制，常在数的右下角标明基数， 十进制一般不标注基数.
例如十进制的133.59，写成133.59(10)
七进制的13，写成13(7)；二进制的10，写成10(2)
一般地，若k是一个大于1的整数，那么以k
为基数的k进制可以表示为一串数字连写在一起
的形式：
anan1 a1a0(k ) (0 an k,0 an1, , a1, a0 k ).
=51
练习：课本P48
3（1）（3）
三、十进制数化为K进制数：除以K取余，倒序读数
例5 把89化为二进制数。
解：
余数
把上式各步所得的余数
从下到上排列，
得到89=1011001（2）
除2取余法
2 89 2 44 2 22 2 11 2 5 2 2 21 0
1 0 0 1 1 0 1
可以推广为把十进制数化为k进制数的算 法，称为除以k取余,倒序读数。

第一章 1.3 算法案例：辗转相除法、秦九韶算法

第一章 1.3 算法案例：辗转相除法、秦九韶算法

3，答案：C
返回
• 4．用秦九韶算法求f(x)＝3x？＋4x？＋5x？ ＋6x？＋7x？＋8x＋1，当x＝0.4时的值， 需进行乘法运算和加法运算的次数分别为 ( ) • A． 6 6 B． 5 6 • C．6 5 D．6 12 • 解析：改写多项多f(x)＝(((((3x＋4)x＋5)x＋ 6)x＋7)x＋8)x＋1，则需要6次乘法和6次加 法． • 答案：A
返回
课堂练习
2．用辗转相除法求294和84的最大公约数时，需要 做除法的次数是( ) A．1 B． 2 C．3 D． 4 3．用秦九韶算法求多项式的值，可用哪种结构的算 法实现( ) A．顺序结构 B．条件结构 C．循环结构 D．A、B两种 • 2，解析：由294＝84×3＋42,84＝42×2知，共需 做2次除法． • 答案：B
返回
法二：更相减损术：
因为378与90都是偶数． 所以用2约简得189和45. 189－45＝144,144－45＝99， 99－45＝54,54－45＝9， 45－9＝36,36－9＝27， 27－9＝18,18－9＝9.
所以378与90的最大公约数为2×9＝18.
返回
[例2]
用秦九韶算法求多项式
1.3 算法案例 辗转相除法、秦九韶算法
返回
预习思考
• 1，用辗转相除法求80和36的最大公约数， 并用更相减损术检验所得结果．
• 2，用秦九韶算法求多项式f(x)＝2x4－6x3 －5x2＋4x－6在x＝5时的值．
返回
[例1]
用辗转相除法求80和36的最大公约数，并
用更相减损术检验所得结果． [自主解答] 用辗转相除法：
返回
1．秦九韶算法的步骤
返回
2．应用秦九韶算法计算多项式的值应注意的问题 (1)要正确将多项式的形式进行改写． (2)计算应由内向外依次计算． (3)当多项式函数中间出现空项式，要以系数为零的

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

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

1.3 算法案例
题型1 辗转相除法与更相减损术
4．分别用辗转相除法和更相减损术求36和80的最大公约数．
解
辗转相除法：
80＝36×2＋8，36＝8×4＋4，8＝4×2.
故36和80的最大公约数是4.
更相减损术：
80－36＝44，44－36＝8，36－8＝28，28－8＝20，
20－8＝12，12－8＝4，8－4＝4.
解析
111÷2＝55……1，55÷2＝27……1，27÷2＝13……1，13÷2＝6……1， 6÷2＝3……0，3÷2＝1……1，1÷2＝0……1， 故111(10)＝1101111(2)．故选C.
1.3 算法案例
题型3 进位制
11．把十进制数189化为四进制数，则末位数字是( B )
A．0
B．1
1.3 算法案例
刷基础
题型3 进位制
13．十六进制数与十进制数的对应如下表：
十 六 进 1 2 3 4 5 6 7 8 9 10 A B C D E F 制 数 十 进 制 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 数
例如：A＋B＝11＋12＝16＋7＝F＋7＝17(16)，所以A＋B的值用十六进制表示就等于17(16)．
f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的具体函数值，运用常规方法计算出结果最多需要n次加法和
n(n 2
1)
次乘法，而运用秦九韶算法由内而外逐层计算一次多项式的值的算法至多需要n次加法和n次乘法．对于计
算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以此算法极大地缩短了CPU运算的
A．2
B．3
C．4
D．5

高一数学 1.3.1 辗转相除法与更相减损术、秦九韶算法课件 新人教A版必修2

§1.3 算法案例
第一课时 辗转相除法与更相减损术､秦九韶算法
自学导引 1.理解辗转相除法与更相减损术的含义,了解执行过程. 2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用. 3.进一步体会算法的基本思想.
课前热身
欧几里得算法
两个正整数的最大公约数
1.辗转相除法是用于求
_____________________的一种方 较大的数
解:解法1(辗转相除法):先求175与100的最大公约数: 175=100×1+75, 100=75×1+25, 75=25×3. ∴175与100的最大公约数是25. 以下再求25与75的最大公约数: 75=25×3 ∴25和75的最大公约数是25.
故25是75和25的最大公约数,也就是175､100､75的最大公约数.
Hale Waihona Puke (3)任何两个数,用辗转相除法求其最大公约数的程序框图. 由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一 开始给定的两数的大小进行判断,并将大数赋给m,小数赋给n,然 后再执行下面的过程.程序框图如下图所示:
(4)辗转相除法求两个数的最大公约数的程序设计.
INPUT “a,b”;a,b IF a<b THEN t=a a=b b=t END IF r=a MOD b WHILE r<>0 a=b b=r r=a MOD b WEND PRINT b END
解:(1)98和63 辗转相除法 S1 98=63 ×1+35, S2 63=35 ×1+28, S3 35=28×1+7, S4 28=4 ×7, 最大公约数为7.
更相减损术 S1 98-63=35, S2 63-35=28, S3 35-28=7, S4 28-7=21, S5 21-7=14, S6 14-7=7, 故98和63的最大公约数为7.

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

1、3、1算法案例(辗转相除法)


你从中看到了 怎样的规律？ 怎么用程序框 图来描述呢？
所以， 所以，当x = 5时，多项式的值等于 时 多项式的值等于17255.2
开始
程序框图：
输入f(x)的系数： a0,a1,a2,a3,a4a5 输入x0
v0 = an vk = vk−1 x + an−k (k =1,2,L, n)
课堂小结： 课堂小结：
1、秦九韶算法的方法和步骤 、 2、秦九韶算法的程序框图 、
算法步骤： 第一步：给定两个正整数m，n； 第二步：计算m除以n所得的余数r； 第三步：m=n，n=r； 第四步：若r=0，则m，n的最大公约数等于m； 否则，返回第二步。
开始
程序框图： 程序：
输入m,n 求m除以n的余数r m=n n=r 否 r=0 ? 是 输入m
INPUT m,n DO r= m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
按由里到外的顺序，依此计算一次多项式当 时的值： 按由里到外的顺序，依此计算一次多项式当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 = 3451.2 v5 = 3451.2×5−0.8 =17255.2
结束
欧几里得辗转相除法找出a,b的最大公约数的步骤是: （1）计算a÷b的余数r,若r=0,则b为a,b的最大公约数； （2）若r≠0,则把前面的除数b作为新的被除数,把r作 为新的除数,继续运算,直到余数为0,此时的除数即为 a,b的最大公约数.
算 法 案 例
第二课时

人教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. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

一个数除以3余2，除以5余3，除以7余2，求
符合条件的最小数.
解：第1步 先列出满足其中一个条件的数（一般从小到大），即除以3余 2的数：
2， 5， 8， 11， 14， 17， 20， 23， 26，…， 第2步再列出满足其中第二个条件的数，即除以5余3的数：
3， 8， 13， 18， 23， 28，…. 第3步归纳前面第3步首先出现的公共数是8. 8就是满足除以3余2，除以5余3的最小的那个数。 3与5的最小公倍数是15.两个条件合并成一个就是8＋15×n (n=0，1， 2，…)。 列出这一串数是8， 23， 38，…， 第4步再列出满足其中第三个条件的数，即除以7余2的数
穷举法
穷举法（也叫枚举法）步骤： 从两个数中较小数开始由大
到小列举，直到找到公约数立即 中断列举，得到的公约数便是最 大公约数 。
思考2:当两个数的公有质因数较大时,我们怎 样去求两个数的最大公约数呢?
辗转相除法:用于求两个正整数的最大公 约数的一种算法,是由欧几里得在公元 前300年左右首先提出的,因而又叫做 欧几里得算法.
得：18和24最大公约数是：2×3＝6
求以下几组正整数的最大公约数。
(注：若整数m和n满足n整除m，则（m,n） =n。用（m,n）来表示m和n的最大公约数。) (1) (18,30) 6； (2) (24,16) 8； (3) (301,133 ) 7;
想一想，如何求8251与6105的最大公约数？
2， 9， 16， 23， 30，…， 第5步归纳第3步第4步得到的数列。就得出符合题目条件的最小数是23. 事实上，我们已把题目中
三个条件合并成一个。3，5，7的最小公倍数是 105 ，满足三个条件的 所有数是23+105×n(n=0，1，2，…)
第6步那么韩信点的兵在1000-1100之间，应该是23+105×10=1073人
=（148，37）
148=37 ×4
=37
练习：用辗转相除法求下列两数的最大公 约数： (1) (225，135) 45 (2) (98，196) 98
思考3：辗转相除直到何时结束？ 主要运用的是哪种算法结构？
辗转相除法是一个反复执行直到余数等 于0停止的步骤，这实际上是一个循环 结构
思考4：你能根据辗转相除法的 算法步骤画出它的程序框图以及 相应的程序语句吗?
1.3 算法案例
1.3 算法案例
1.3.1 辗转相除法和更相减损术 1.3.2 秦九韶算法 1.3.3 K进制与十进制互化
韩信是秦末汉初的著名军事家. 情境创设
秦朝末年，楚汉相争.韩信帅1500名将士与楚 王大将李锋交战。苦战一场，楚军不敌，败退 回营，汉军也死伤四五百人，于是韩信整顿兵 马也返回大本营。当行至一山坡，忽有后军来 报，说有楚军骑兵追来。只见远方尘土飞扬， 杀声震天。汉军本来已十分疲惫，这时队伍大 哗。韩信急速点兵迎敌。他命令士兵3人一排， 结果多出2名；接着命令士兵5人一排，结果多 出3名；他又命令士兵7人一排，结果又多出2 名。韩信马上向将士们宣布：我军有1073人， 敌人不足五百，我们居高临下，以众击寡，一 定能打败敌人。
例1、求8251和6105的最大公约数。
解：
（8251，6105）
8251=6105×1+2146 =（6105，2146）
6105=2146 ×2+1813 =（2146，1813）
2146=1813 ×1+333 =（1813，333）
1813=333 ×5+148 =（333，148）
333=148 ×2+37
更相减损是一个反复执行直到 减数等于差时停止的步骤，这 实际也是一个循环结构
探究二,更相减损术
<九章算术> “可半者半之,不可半者,副置分母、 子之数，以少减多，更相减损，求其等也， 以等数约之。”
即：a,b,c为正整数,若a-b=c,则（a,b）=(b,c)。
“更相减损术”(也是求两个正整数的最大公约数的算法) 步骤：
第一步：任意给定两个正整数;判断他们是否都是偶 数。若是，则用2约简;若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与 较小的数比较，并以大数减小数。继续这个操作，直 到所得的减数和差相等为止，则这个等数就是所求的 最大公约数。
例2、用更相减损术求98与63的最大公约数 Fra bibliotek自己按照步骤求解）
解:由于63不是偶数,把98和63以大数减小数,辗转相减。
（98，63） 98-63=35 =（63，35）
定义:所谓的辗转相除法,就是对于给定 的两个数,用较大的数除以较小的数,若 余数不为零,则将余数和较小的数构成 新的数对,继续上面的除法,直到大数被 小数除尽,则这是较小的数就是原来两 个数的最大公约数.
辗转相除法的理论基础:
定理: 已知m,n,r为正整数,若m=nq+r(0≤r<n) （即r=m MOD n）,则（m,n）=(n,r)。
开始
输入：m,n
INPUT m,n
r=1
r=m MOD n
WHILE r<>0 r=m MODm=nn
m=n
n=r
n=r
WEND
N r=0?
PRINT m
Y
END
输出：m
结束
程序： INPUT “m，n=”;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
韩信点兵问题的解决方法实质上就 是中国剩余定理，中国古代在数学 史上作出过重大贡献，有很多经典 方法被传承下来。
探究一,辗转相除法
思考1:在小学中我们是如何求出两个正整数的 最大公约数的呢?
算法案例之求最大公约数
例、求18与24的最大公约数：
解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 短除法 3 4 3和4互质不除了。
63-35=28 =（35，28）
35-28=7 =（28，7）
28-7=21 21-7=14
=（21，7） =（14，7）
14-7=7 =（7，7） = 7
所以，98和63的最大公约数等于7。
练习：用更相减损术求下列两数的最大公约数：
（1）(225，135) 45 （2）(98，196) 98
思考：更相减损直到何时结束？运用的是哪种 算法结构？