2021-2022学年度高中数学新课标人版A版必修3课件 1.3 算法与案例 (共30张PPT)
文档属性
| 名称 | 2021-2022学年度高中数学新课标人版A版必修3课件 1.3 算法与案例 (共30张PPT) |  | |
| 格式 | ppt | ||
| 文件大小 | 1.0MB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 人教新课标A版 | ||
| 科目 | 数学 | ||
| 更新时间 | 2021-12-10 10:05:38 | ||
图片预览
文档简介
(共30张PPT)
基本结构
程序框图
顺序结构
变量与赋值
循环结构
基本语句
循环语句
条件语句
WHILE语句
UNTIL语句
IF-THEN语句
语句适用结构
算法
条件结构
我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。
案例1.辗转相除法与更相减损术
在初中，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？
2 30
3 9 15
3 5
所以，18和30的最大公约数是：2×3＝6
互质
因数
但是，当我们处理较大数（如：8251与6105）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法——辗转相除法
这种算法是欧几里得公元前300年左右首先提出的，因此又叫欧几里得算法
例1 求两个正数8251和6105的最大公约数。
分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数
解
8251＝6105×1＋2146
显然8251和6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数
继续下去，我们得到：
欧几里得（公元前330-公元前275）：古希腊数学家，雅典人
欧几里得是柏拉图的学生，长期在亚历山大里亚教书。
公元前300年左右，代表作《几何原本》13卷问世，创立了著名的欧氏几何，至今仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。
6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8251与6105的最大公约数
这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成
利用辗转相除法求最大公约数的步骤如下：
第一步：给定两个正整数m,n.
第二步：计算m除以n的余数.
第三步：m=n,n=r.
第四步：若r＝0,则m,n的最大公约数等于m;否则,返回第二步.
r= m MOD n
m=n
n=r
r=o
否
是
程序图框
带余除法
INPUT “请输入m，n的值”；m，n
DO
r=m MOD N
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
为什么要用直到型循环结构？
1.利用辗转相除法求两数4081与20723的最大公约数 ，写出它的流程框图和BASIC程序
更相减损术
我国早期也有解决求最大公约数问题的算法
《九章算术》（公元50年～100年或更早 ）是中国古代数学专著，承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古代数学体系的形成。
历代数学家把它尊为“算经之首”．这是世界上最早的印刷本数学书。
《九章算术》共收有 246个数学问题，分为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。
《九章算术》是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；“方程”章还在世界数学史上首次阐述了负数及其加减运算法则。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数
例1 用更相减损术求98与63的最大公约数.
解 由于63不是偶数，把98和63以大数减小数，并辗转相减
98-63＝35
63-35＝28
35-28＝7
28-7＝14
14-7＝7
所以，98与63的最大公约数是7
比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
思考一.用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。 （1）225，135 （2）98，196 （3）72，168
思考二：用更相减损法可否求上述3组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上测试自己的程序；若不能说明无法实现的理由。
思考三：利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在BASIC中实现。
案例二（秦九韶算法）怎样求多项式
当x=5时的值？
据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算
我们把多项式变形为： 再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。这种算法就叫秦九韶算法。
秦九韶（1202--1261年），字道古，安岳县人。其父秦季栖，进士出身，官至工部郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父居中都（今北京），受到名师指导，学习日益增进。及长，随父迁湖州（今浙江吴兴县），在西门外修建住房，由秦九韶设计施工，堂分7间，后为列室，仅中堂1间，纵横7丈，极其宏伟宽敞，显示出他在建筑方面的才能
把一个多项式
改写为：
求多项式的值时，首先计算最内层括号内的一次多项式的值，即：
再有内向外逐层计算一次多项式的值，即：
这样将求n次多项式f(x)的值转化为求n个一次多项式的值。
例2 已知一个5次多项式为
当
用秦九韶算法求这个多项式的值。
用秦九韶算法求这个多项式当 时的值。
3. 已知一个5次多项式为
思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？
（2）在利用秦九韶算法计算n次多项式当时需要多少次乘法计算和多少次加法计算？
进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说满几进一就是几进制，几进制的基数就是几
大于1的整数
由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度--进位制
十进制数 表示实际数值为：
K进制数 实际表示数为：
在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关
为了区别进制，我们就用下标（k）表示k进制数
a [n]是0～9的数子
下面我们来用一个具体的例子来分析：
例3.将二进制数110 011(2)化成十进制数
解 根据k进制数的实际意义，我们可以这样来转换：
INPUT a,b,c
b=0
i=1
T=a MOD 10
DO
b=b+t*k^(i-1)
a=a\10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END
例4 设计一个算法,把k进制数a(共n位)转化为十进制数b.
缺少算法分析和
程序框图
例5.把89化为二进制数
分析：89=2×(2×(2×(2×(2×2+1)+1)+0)+0)+1
=…
=1 011 001(2)
2 89 1
2 44 0
2 22 0
2 11 1
2 5 1
2 2 0
2 1 1
0
所以上式可以表示为：1 011 001
综合：上述方法叫做k进制数的除k取余法
5.把89化为五进制数
思考：1如何将十六进制数A1F721化为二进制数
一般方法：
k进制数
十进制数
n进制数
1010 0001 1111 0111 0010 0001
算法
程序图框
算法语句
辗转相除与更相减损术
秦 九 韶 算 法
进 位 制
基本结构
程序框图
顺序结构
变量与赋值
循环结构
基本语句
循环语句
条件语句
WHILE语句
UNTIL语句
IF-THEN语句
语句适用结构
算法
条件结构
我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。
案例1.辗转相除法与更相减损术
在初中，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？
2 30
3 9 15
3 5
所以，18和30的最大公约数是：2×3＝6
互质
因数
但是，当我们处理较大数（如：8251与6105）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法——辗转相除法
这种算法是欧几里得公元前300年左右首先提出的，因此又叫欧几里得算法
例1 求两个正数8251和6105的最大公约数。
分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数
解
8251＝6105×1＋2146
显然8251和6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数
继续下去，我们得到：
欧几里得（公元前330-公元前275）：古希腊数学家，雅典人
欧几里得是柏拉图的学生，长期在亚历山大里亚教书。
公元前300年左右，代表作《几何原本》13卷问世，创立了著名的欧氏几何，至今仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。
6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8251与6105的最大公约数
这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成
利用辗转相除法求最大公约数的步骤如下：
第一步：给定两个正整数m,n.
第二步：计算m除以n的余数.
第三步：m=n,n=r.
第四步：若r＝0,则m,n的最大公约数等于m;否则,返回第二步.
r= m MOD n
m=n
n=r
r=o
否
是
程序图框
带余除法
INPUT “请输入m，n的值”；m，n
DO
r=m MOD N
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
为什么要用直到型循环结构？
1.利用辗转相除法求两数4081与20723的最大公约数 ，写出它的流程框图和BASIC程序
更相减损术
我国早期也有解决求最大公约数问题的算法
《九章算术》（公元50年～100年或更早 ）是中国古代数学专著，承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古代数学体系的形成。
历代数学家把它尊为“算经之首”．这是世界上最早的印刷本数学书。
《九章算术》共收有 246个数学问题，分为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。
《九章算术》是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；“方程”章还在世界数学史上首次阐述了负数及其加减运算法则。
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数
例1 用更相减损术求98与63的最大公约数.
解 由于63不是偶数，把98和63以大数减小数，并辗转相减
98-63＝35
63-35＝28
35-28＝7
28-7＝14
14-7＝7
所以，98与63的最大公约数是7
比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到
思考一.用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。 （1）225，135 （2）98，196 （3）72，168
思考二：用更相减损法可否求上述3组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上测试自己的程序；若不能说明无法实现的理由。
思考三：利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在BASIC中实现。
案例二（秦九韶算法）怎样求多项式
当x=5时的值？
据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算
我们把多项式变形为： 再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。这种算法就叫秦九韶算法。
秦九韶（1202--1261年），字道古，安岳县人。其父秦季栖，进士出身，官至工部郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父居中都（今北京），受到名师指导，学习日益增进。及长，随父迁湖州（今浙江吴兴县），在西门外修建住房，由秦九韶设计施工，堂分7间，后为列室，仅中堂1间，纵横7丈，极其宏伟宽敞，显示出他在建筑方面的才能
把一个多项式
改写为：
求多项式的值时，首先计算最内层括号内的一次多项式的值，即：
再有内向外逐层计算一次多项式的值，即：
这样将求n次多项式f(x)的值转化为求n个一次多项式的值。
例2 已知一个5次多项式为
当
用秦九韶算法求这个多项式的值。
用秦九韶算法求这个多项式当 时的值。
3. 已知一个5次多项式为
思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？
（2）在利用秦九韶算法计算n次多项式当时需要多少次乘法计算和多少次加法计算？
进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说满几进一就是几进制，几进制的基数就是几
大于1的整数
由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度--进位制
十进制数 表示实际数值为：
K进制数 实际表示数为：
在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关
为了区别进制，我们就用下标（k）表示k进制数
a [n]是0～9的数子
下面我们来用一个具体的例子来分析：
例3.将二进制数110 011(2)化成十进制数
解 根据k进制数的实际意义，我们可以这样来转换：
INPUT a,b,c
b=0
i=1
T=a MOD 10
DO
b=b+t*k^(i-1)
a=a\10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END
例4 设计一个算法,把k进制数a(共n位)转化为十进制数b.
缺少算法分析和
程序框图
例5.把89化为二进制数
分析：89=2×(2×(2×(2×(2×2+1)+1)+0)+0)+1
=…
=1 011 001(2)
2 89 1
2 44 0
2 22 0
2 11 1
2 5 1
2 2 0
2 1 1
0
所以上式可以表示为：1 011 001
综合：上述方法叫做k进制数的除k取余法
5.把89化为五进制数
思考：1如何将十六进制数A1F721化为二进制数
一般方法：
k进制数
十进制数
n进制数
1010 0001 1111 0111 0010 0001
算法
程序图框
算法语句
辗转相除与更相减损术
秦 九 韶 算 法
进 位 制