福建省晋江市首峰中学人教版高一数学必修三课件：1.3 算法案例（共34张PPT）
文档属性
| 名称 | 福建省晋江市首峰中学人教版高一数学必修三课件：1.3 算法案例（共34张PPT） |  | |
| 格式 | zip | ||
| 文件大小 | 322.6KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 人教新课标A版 | ||
| 科目 | 数学 | ||
| 更新时间 | 2015-12-28 13:51:51 | ||
图片预览
文档简介
课件34张PPT。算 法 案 例（第一课时）1、求两个正整数的最大公约数（1）求25和35的最大公约数
（2）求225和135的最大公约数2、求8251和6105的最大公约数 所以，25和35的最大公约数为5所以，225和135的最大公约数为45辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程 第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。 思考：从上述的过程你体会到了什么？完整的过程8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2 用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然37是148和37的最大公约数，也就是8251和6105的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 思考1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。m = n × q ＋ r用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否思考2：辗转相除法中的关键步骤是哪种逻辑结构？ INPUT m , n
DO
r=m mod n
m=n
n=r
LOOP UNTIL r=0
PRINT m
End
《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。例3 用更相减损术求 225 与 135 的最大公约数解：由于两数不是偶数，把225和135以大数减小数，
并辗转相减 225－135＝90
135－90＝45 90－45＝45所以，225和135的最大公约数等于45INPUT a,b
WHILE a<>b
IF a>b THEN
a=a-b
ELSE
b=b-a
END IF
WEND
PRINT a
END《九章算术》——更相减损术的算法程序语句： 练习：
用辗转相除法求 294 与84的最大公约数，再用更相减损术验证。思考：求三个数：168，54，264的最大公约数。算 法 案 例（第二课时）计算多项式ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值算法1：ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１
=x ×x×x×x ×x ＋ x × x×x ×x ＋ x × x × x
＋ x × x ＋ x ＋ 1所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１= 3906算法2：ｆ（5）=5５＋5４＋5３＋5２＋5＋１=（（ （（5 ＋１ ） × 5 ＋１ ） ×5 ＋１ ） × 5＋１ ） ×5 ＋１分析：两种算法中各用了几次乘法运算？和几次加法运算？ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１
=((((x+1)x+1)x+1)x+1)x+1《数书九章》——秦九韶算法对该多项式按下面的方式进行改写：这样改写的目的是什么？简化计算的次数（尤其是乘法的次数）。对该多项式按下面的方式进行改写：思考：当知道了x的值后该如何求多项式的值？要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的方法，称为秦九韶算法。思考：在求多项式的值上，这是怎样的一个转化？例2 已知一个五次多项式为用秦九韶算法求这个多项式当x = 5的值。解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x = 5时的值：所以，当x = 5时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？练习：2、已知多项式f(x)=2x7-5x5+4x3+x2-x-6
用秦九韶算法求这个多项式当x=2时的值。INPUT “n=“；n
INPUT “an=“;ai
INPUT “x=“; x
V=an
i=n-1
DO
PRINT “i=“;i
INPUT “ai=“;ai
v=v*x+ai
i=i-1
LOOP UNTIL i<0
PRINT v
END算法案例（第三课时）一、进位制1、什么是进位制？2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明．进位制是人们为了计数和运算方便
而约定的记数系统。1、我们了解十进制吗？所谓的十进制，它是如何构成的？十进制由两个部分构成例如：3721其它进位制的数又是如何的呢？第一、它有0、1、2、3、4、5、6、7、8、9十个数字；第二、它有“权位”，即从右往左为个位、十位、百位、千位等等。(用10个数字来记数，称基数为10)表示有：1个1，2个十， 7个百即7个10的平方，
3个千即3个10的立方2、 二进制二进制是用0、1两个数字来描述的。如11001等（１）二进制的表示方法区分的写法：11001（2）或者（11001）28进制呢？如7342(8)k进制呢？anan-1an-2…a2a1(k)？二、二进制与十进制的转换1、二进制数转化为十进制数例1 将二进制数110011(2)化成十进制数解：根据进位制的定义可知所以，110011（2）=51。将（1）10303（4） ； （2）1234（5）.化为十进制数练习将下面的二进制数化为十进制数？（1）11（2）101（3）1101（4）10101 例2 已知10b1（2）=a02（3）,求数字a，b的值.所以2b+9=9a+2，即9a-2b=7. 10b1（2）=1×23+b×2+1=2b+9.a02（3）=a×32+2=9a+2.故a=1，b=1. 将k进制数a转换为十进制数(共有 n位)的程序a=anan-1… a3a2a1(k) =ank(n-1)+an-1k(n-2)+ … + a3k2 +a2k1+a1k0b=a1k0b=a2k1 +bb=a3k2 + b…b=ankn-1 +bai=GET a[i]
GET函数用于取出a的右数第i位数i=i+1i=1b=aiki-1+bINPUT “a,k,n=”；a,k,n
b=0
i=0
t=a MOD 10
DO
b=b+t*k^(i-1)
a=a10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END2、十进制转换为二进制 (除2取余法：用2连续去除89或所得的商，
然后取余数)例2 把89化为二进制数解：根据“逢二进一”的原则，有89＝2×44＋1＝ 2× (2×22＋0)+1＝ 2×( 2×( 2×11＋0)+0)+1＝ 2× (2× (2× (2× 5＋1)+0)+0)+15＝ 2× 2＋1＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝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＋2189＝2×44＋144＝ 2×22＋022＝ 2×11＋011＝ 2× 5＋1＝ 2× (2× (2× (2× (2× 2＋1)+1)+0)+0)+1所以89＝2×（2×（2×（2×（2 × 2 ＋1）＋1）＋0）＋0）＋12、十进制转换为二进制例2 把89化为二进制数522212010余数11224889222201101注意：
1.最后一步商为0，
2.将上式各步所得的余数从下到上排列，得到：89=1011001（2）练习将下面的十进制数化为二进制数？（1）10（2）20（3）128（4）256例3 把89化为五进制数3、十进制转换为其它进制解：根据除k取余法以5作为除数，相应的除法算式为：所以，89=324（5）。设计一个程序，实现“除k取余法”Input “a,k=”;a,k
b=0
i=0
DO
q=ak
r=a MOD k
b=b+r*10^I
i=i+1
a=q
LOOP UNTIL q=0
PRINT b
END思考题： 如何将101（2） 化为五进制数？
（2）求225和135的最大公约数2、求8251和6105的最大公约数 所以，25和35的最大公约数为5所以，225和135的最大公约数为45辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程 第一步 用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。 思考：从上述的过程你体会到了什么？完整的过程8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例2 用辗转相除法求225和135的最大公约数225=135×1+90135=90×1+4590=45×2显然37是148和37的最大公约数，也就是8251和6105的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 思考1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。m = n × q ＋ r用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否思考2：辗转相除法中的关键步骤是哪种逻辑结构？ INPUT m , n
DO
r=m mod n
m=n
n=r
LOOP UNTIL r=0
PRINT m
End
《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是，则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。例3 用更相减损术求 225 与 135 的最大公约数解：由于两数不是偶数，把225和135以大数减小数，
并辗转相减 225－135＝90
135－90＝45 90－45＝45所以，225和135的最大公约数等于45INPUT a,b
WHILE a<>b
IF a>b THEN
a=a-b
ELSE
b=b-a
END IF
WEND
PRINT a
END《九章算术》——更相减损术的算法程序语句： 练习：
用辗转相除法求 294 与84的最大公约数，再用更相减损术验证。思考：求三个数：168，54，264的最大公约数。算 法 案 例（第二课时）计算多项式ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值算法1：ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１
=x ×x×x×x ×x ＋ x × x×x ×x ＋ x × x × x
＋ x × x ＋ x ＋ 1所以ｆ（5）=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１= 3906算法2：ｆ（5）=5５＋5４＋5３＋5２＋5＋１=（（ （（5 ＋１ ） × 5 ＋１ ） ×5 ＋１ ） × 5＋１ ） ×5 ＋１分析：两种算法中各用了几次乘法运算？和几次加法运算？ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１
=((((x+1)x+1)x+1)x+1)x+1《数书九章》——秦九韶算法对该多项式按下面的方式进行改写：这样改写的目的是什么？简化计算的次数（尤其是乘法的次数）。对该多项式按下面的方式进行改写：思考：当知道了x的值后该如何求多项式的值？要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的方法，称为秦九韶算法。思考：在求多项式的值上，这是怎样的一个转化？例2 已知一个五次多项式为用秦九韶算法求这个多项式当x = 5的值。解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x = 5时的值：所以，当x = 5时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？练习：2、已知多项式f(x)=2x7-5x5+4x3+x2-x-6
用秦九韶算法求这个多项式当x=2时的值。INPUT “n=“；n
INPUT “an=“;ai
INPUT “x=“; x
V=an
i=n-1
DO
PRINT “i=“;i
INPUT “ai=“;ai
v=v*x+ai
i=i-1
LOOP UNTIL i<0
PRINT v
END算法案例（第三课时）一、进位制1、什么是进位制？2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明．进位制是人们为了计数和运算方便
而约定的记数系统。1、我们了解十进制吗？所谓的十进制，它是如何构成的？十进制由两个部分构成例如：3721其它进位制的数又是如何的呢？第一、它有0、1、2、3、4、5、6、7、8、9十个数字；第二、它有“权位”，即从右往左为个位、十位、百位、千位等等。(用10个数字来记数，称基数为10)表示有：1个1，2个十， 7个百即7个10的平方，
3个千即3个10的立方2、 二进制二进制是用0、1两个数字来描述的。如11001等（１）二进制的表示方法区分的写法：11001（2）或者（11001）28进制呢？如7342(8)k进制呢？anan-1an-2…a2a1(k)？二、二进制与十进制的转换1、二进制数转化为十进制数例1 将二进制数110011(2)化成十进制数解：根据进位制的定义可知所以，110011（2）=51。将（1）10303（4） ； （2）1234（5）.化为十进制数练习将下面的二进制数化为十进制数？（1）11（2）101（3）1101（4）10101 例2 已知10b1（2）=a02（3）,求数字a，b的值.所以2b+9=9a+2，即9a-2b=7. 10b1（2）=1×23+b×2+1=2b+9.a02（3）=a×32+2=9a+2.故a=1，b=1. 将k进制数a转换为十进制数(共有 n位)的程序a=anan-1… a3a2a1(k) =ank(n-1)+an-1k(n-2)+ … + a3k2 +a2k1+a1k0b=a1k0b=a2k1 +bb=a3k2 + b…b=ankn-1 +bai=GET a[i]
GET函数用于取出a的右数第i位数i=i+1i=1b=aiki-1+bINPUT “a,k,n=”；a,k,n
b=0
i=0
t=a MOD 10
DO
b=b+t*k^(i-1)
a=a10
t=a MOD 10
i=i+1
LOOP UNTIL i>n
PRINT b
END2、十进制转换为二进制 (除2取余法：用2连续去除89或所得的商，
然后取余数)例2 把89化为二进制数解：根据“逢二进一”的原则，有89＝2×44＋1＝ 2× (2×22＋0)+1＝ 2×( 2×( 2×11＋0)+0)+1＝ 2× (2× (2× (2× 5＋1)+0)+0)+15＝ 2× 2＋1＝2×（2×（2×（2×（22＋1）＋1）＋0）＋0）＋189＝1×26＋0×25＋1×24＋1×23＋0×22＋0×21＋1×20所以：89=1011001（2）＝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＋2189＝2×44＋144＝ 2×22＋022＝ 2×11＋011＝ 2× 5＋1＝ 2× (2× (2× (2× (2× 2＋1)+1)+0)+0)+1所以89＝2×（2×（2×（2×（2 × 2 ＋1）＋1）＋0）＋0）＋12、十进制转换为二进制例2 把89化为二进制数522212010余数11224889222201101注意：
1.最后一步商为0，
2.将上式各步所得的余数从下到上排列，得到：89=1011001（2）练习将下面的十进制数化为二进制数？（1）10（2）20（3）128（4）256例3 把89化为五进制数3、十进制转换为其它进制解：根据除k取余法以5作为除数，相应的除法算式为：所以，89=324（5）。设计一个程序，实现“除k取余法”Input “a,k=”;a,k
b=0
i=0
DO
q=ak
r=a MOD k
b=b+r*10^I
i=i+1
a=q
LOOP UNTIL q=0
PRINT b
END思考题： 如何将101（2） 化为五进制数？