[整理]1.3算法案例.pptVIP

1.3算法案例;3 5;〖研探新知〗;〖研探新知〗;利用辗转相除法求最大公约数的步骤如下： ;第一步,给定两个正数m,n 第二步,计算m除以n所得到余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m; 　　　　否则返回第二步;否;练习1：利用辗转相除法求两数4081与20723的最大公约数. ;2.更相减损术:;例2 用更相减损术求98与63的最大公约数.;第一步,给定两个正整数,不妨设mn, 第二步,若m,n都是偶数,则不断用2约简,使他们不同时是偶数,约简后的两个数仍记为m,n 第三步,d=m-n 第四步,判断”d0”是否成立,若是,则将n,d 中较大者记为m,较小的记为n,返回第三步;否则,2^k *n(k是约简整数的2的个数)为所求的最大公约数.;开始;INPUT “m,n=“;m,n IF mn THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n ;3.辗转相除法与更相减损术的比较: ;作业: 课本P45页练习T1; P48页A组T1.;案例2 秦九韶算法;〖教学设计〗; 这析计算上述多项式的值,一共需要9次乘法运算,5次加法运算.; [问题3]能否探索更好的算法,来解决任意多项式的求值问题?;例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.;2 -5 -4 3 -6 7;2 -5 0 -4 3 -6 0;f(x)=anxn+an-1xn-1+an-2xn-2+……+a1x+a0.; 点评:秦九韶算法是求一元多项式的值的一种方法. 它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和n次加法运算,减少为n次乘法运算和n次加法运算,大大提高了运算效率.;v1=anx+an-1,;否; 课本P45页练习T2; P48页A组T2.;案例3 进位制;二、教学重难点 重点：各进位制表示数的方法及各进位制之间的转换 难点：除k去余法的理解以及各进位制之间转换的程序框图的设计 三、学法 在学习各种进位制特点的同时探讨进位制表示数与十进制表示数的区别与联系，熟悉各种进位制表示数的方法，从而理解十进制转换为各种进位制的除k去余法。; [问题1]我们常见的数字都是十进制的,但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十??位制,电子计算机用的是二进制.那么什么是进位制?不同的进位制之间又有什么联系呢?; 如二进制可使用的数字有0和1,基数是2; 十进制可使用的数字有0,1,2,…,8,9等十个数字,基数是10; 十六进制可使用的数字或符号有0~9等10个数字以及A~F等6个字母(规定字母A~F对应10~15),十六进制的基数是16.;[问题2]十进制数3721中的3表示3个千,7表示7个百,2表示2个十,1表示1个一,从而它可以写成下面的形式:; 一般地,若k是一个大于1的整数,那么以k为基数的k进制数可以表示为一串数字连写在一起的形式; [问题3]二进制只用0和1两个数字,这正好与电路的通和断两种状态相对应,因此计算机内部都使用二进制.计算机在进行数的运算时,先把接受到的数转化成二进制数进行运算,再把运算结果转化为十进制数输出. 那么二进制数与十进制数之间是如何转化的呢?;例1:把二进制数110011(2)化为十进制数.; k进制数转化为十进制数的方法;例2:把89化为二进制的数.;89=44×2+1, ;44 1;例3:把89化为五进制的数.;[问题5]你会把三进制数10221(3)化为二进制数吗?;小结;作业: 1.课本P45页A组T3.