高中数学新课标人教A版必修三1.3.算法案例三课时课件

1、算 法 案 例(第一课时)案例1 辗转相除法与更相减损术1. 回忆算法的三种表述：自然语言程序框图程序语言三种逻辑结构五种根本语句2. 思考： 小学学过的求两个数最大公约数的方法？ 先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.1、求两个正整数的最大公约数1求25和35的最大公约数2求49和63的最大公约数25（1）5535749（2）77639所以，25和35的最大公约数为5所以，49和63的最大公约数为72、除了用这种方法外还有没有其它方法？算出8256和6105的最大公约数. 辗转相除法欧几里得算法观察用辗转相除法求8251和6105的最大公约数的

2、过程 第一步 用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步 对6105和2146重复第一步的做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。 为什么呢？思考：从上述的过程你体会到了什么？完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例2 用辗转

3、相除法求225和135的最大公约数225=1351+90135=901+4590=452显然37是148和37的最大公约数，也就是8251和6105的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 思考1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数S2：除数变成被除数，余数变成除数S3：重复S1，直到余数为0 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m

4、 = n q r用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否思考2：辗转相除法中的关键步骤是哪种逻辑结构？ 1、辗转相除法欧几里得算法1算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。假设余数不为零，那么将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，那么这时较小的数就是原来两个数的最大公约数。2算法步骤第一步：输入两个正整数m,n(mn).第二步：计算m除以n所得的余数r.第三步：m=n,n=r.第四步：假设r0,那么m,n的最大公约数等于m； 否那么转到第二步. 第五步：输出最大公约数m.3程序框图4程序INPUT “

5、m,n=“;m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND开始输入m,n r=m MOD n m=nr=0?是否 n=r 输出m结束?九章算术?更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。假设是，那么用2约简；假设不是那么执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，那么这个等数就是所求的最大公约数。2、更相减损术1算理：所谓更相减损术，就是对于给定的两个数，

6、用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。2算法步骤第一步：输入两个正整数a,b(ab);第二步：假设a不等于b ,那么执行第三步；否那么转到第五步；第三步：把a-b的差赋予r;第四步：如果br, 那么把b赋给a,把r赋给b;否那么把r赋给a，执行第二步；第五步：输出最大公约数b.3程序框图4程序INPUT “a,b=“;a,bWHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND开始输入a,bab?是

7、否 输出b结束 b=ra=br=a-br=0?输出v结束v=vx+aii=i-1YNi=n-1V=an3程序：INPUT “n=；nINPUT “an=“;aINPUT “x=“;xv=ai=n-1WHILE i=0 PRINT “i=“;i INPUT “ai=“;a v=v*x+a i=i-1WENDPRINT vEND1、多项式f(x)=x5+5x4+10 x3+10 x2+5x+1用秦九韶算法求这个多项式当x=-2时的值。练习：2、多项式f(x)=2x4-6x3-5x2+4x-6用秦九韶算法求这个多项式当x=5时的值。作业：P48 A2小结：1、秦九韶算法的方法和步骤2、秦九韶算法的程

8、序框图算法案例3一、进位制1、什么是进位制？进位制是人们为了计数和运算方便而约定的记数系统。进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值。可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制。新课讲解： 比方： 满二进一，就是二进制； 满十进一，就是十进制； 满十二进一，就是十二进制； 满六十进一，就是六十进制“满几进一就是几进制，几进制的基数就是几.基数：2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明最常见的进位制应该是我们数学中的十进制,比方一般的数值计算，但是并不是生活中的每一种数字都是十进制的.古人有半斤八两之说，就是十六进制与十进制的

9、转换.比方时间和角度的单位用六十进位制, 计算“一打数值时是12进制的。电子计算机用的是二进制 。 式中1处在百位，第一个3所在十位，第二个3所在个位，5和9分别处在十分位和百分位。十进制数是逢十进一的。 我们最常用最熟悉的就是十进制数，它的数值局部是十个不同的数字符号0，1，2，3，4，5，6，7，8，9来表示的。十进制：例如133.59，它可用一个多项式来表示：133.59=1*102+3*101+3*100 +5*10-1+9*10-2 实际上，十进制数只是计数法中的一种，但它不是唯一记数法。除了十进制数，生产生活中还会遇到非十进制的记数制。如时间：60秒为1分，60分为1小时，它是六十

10、进制的。两根筷子一双，两只手套为一副，它们是二进制的。其它进制： 二进制、七进制、八进制、十二进制、六十进制二进制只有0和1两个数字，七进制用06七个数字十六进制有09十个数字及ABCDEF六个字母. 为了区分不同的进位制，常在数的右下角标明基数，十进制一般不标注基数.例如十进制的133.59，写成133.59(10)七进制的13，写成13(7)；二进制的10，写成10(2) 一般地，若k是一个大于1的整数，那么以k为基数的k进制可以表示为一串数字连写在一起的形式：A3、十进制的构成十进制由两个局部构成例如：3721其它进位制的数又是如何的呢？第一、它有09十个数字；第二、它有“数位”，即从右

11、往左为个位、十位、百位、千位等等。(用10个数字来记数，称基数为10)表示有：1个1，2个十， 7个百即7个10的平方，3个千即3个10的立方十进制：“满十进一”探究：P40其它进制数化成十进制数公式二、 二进制二进制是用0、1两个数字来描述的如11001二进制的表示方法区分的写法：110012或者(11001)2八进制呢？如7342(8)k进制呢？anan-1an-2a1(k)？三、二进制与十进制的转换1、二进制数转化为十进制数例1：将二进制数110011(2)化成十进制数。解：根据进位制的定义可知所以，1100112=51其它进制数化成十进制数公式1、将下面的二进制数化为十进制数？（1）1

12、1（2）110练习2、把其他进位制的数化为十进制数的公式是什么？例2、设计一个算法，将k进制数a(共有n位)转换为十进制数b。(1)算法步骤:第一步，输入a,k和n的值；第二步，将b的值初始化为0,i的值初始化为1；第三步，b=b+ai*ki-1, i=i+1第四步，判断in是否成立.假设是,那么执行第五步,否那么,返回第三步；第五步，输出b的值.(2)程序框图:开始输入a,k,nb=0i=1把a的右数第i位数字赋给tb=b+t*ki-1i=i+1in?否是输出b结束(3)程序：INPUT “a,k,n=;a,k,nb=0i=1t=a MOD 10DO b=b+t*k(i-1) a=a10 t

13、=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND方法：除2取余法，即用2连续去除89或所得的商，然后取余数。例、 把89化为二进制数解：根据“逢二进一的原那么，有892441 2 (2220)+1 2( 2( 2110)+0)+1 2 (2 (2 (2 51)+0)+0)+15 2 212222221100189126025124123022021120所以：89=101100122222321001222422200122523+220012624+23002089244144 222022 211011 2 51 2 (2 (2 (2 (2 21)+1)+0)+

14、0)+1所以8922222 2 110012、十进制转换为二进制注意：1.最后一步商为0，2.将上式各步所得的余数从下到上排列，得到： 89=10110012另解除2取余法的另一直观写法：522212010余数11224489222201101练习将下面的十进制数化为二进制数？（1）10（2）20例1：把89化为五进制数。3、十进制转换为其它进制解：根据除k取余法以5作为除数，相应的除法算式为：所以，89=3245895175350423余数例2、设计一个程序，实现“除k取余法。(1)、 算法步骤：第一步，给定十进制正整数a和转化后的数的基数k；第二步，求出a 除以k 所得的商q ,余数r；第三步，假设q 0, 那么a=q, 返回第二步；否那么，执行第四步；第四步，将依次得到的余数从右到左排列，得到k 进制数。2程序框图：开始输入a,k 求a除以k的商q 求a除以k的余数rq=0?是否 a=q 将依次输出的r从右到左排列结束输出r(3)程序：INPUT “a，k=；a,kb=0i=0DO q=ak r=a MOD k b=b+r*10i i=i+1 a=qLOOP UNTIL q=0PRINT bEND练习：完成以下进位制之间的转化：1102314= 10；22357= 10；313710= 6；412315= 7；52134= 3；610101112=