人教版新课标A必修31.3 算法与案例课前预习ppt课件

这是一份人教版新课标A必修31.3 算法与案例课前预习ppt课件
算 法 案 例(第一课时)求以下几组正整数的最大公约数。（1）（18，30） （2）（24，16）（3）（63，63） （4）（72，8） （5）（301，133 ）想一想，如何求8251与6105的最大公约数？ 例、求18与24的最大公约数：6；8；63；8；7；短除法辗转相除法（欧几里得算法）观察用辗转相除法求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练习：用辗转相除法求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）45982417辗转相除法求两个数的最大公约数，其算法可以描述如下：辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构 思考：辗转相除直到何时结束？主要运用的是哪种算法结构？① 给定两个正整数m和n；② 计算m除以n的余数r；③m=n，n=r。④若r=0,则m,n的最大公约数等于m;否则返回第二步.辗转相除除法的程序框图与程序开始输入m,n r=mMODn m=nn=rr=0？输出m结束否是 INPUT m,nDO r=mMODn m=n n=r LOOP UNTIL r=0PRINT mEND《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。例、用更相减损术求98与63的最大公约数（自己按照步骤求解）解：由于63不是偶数，把98和63以大数减小数，并辗转相减。= 7所以，98和63的最大公约数等于7。（98，63）=（63，35）98-63=35   63-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）练习：用更相减损术求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）45982417更相减损是一个反复执行直到减数等于差时停止的步骤，这实际也是一个循环结构 把更相减损术与辗转相除法比较,你有什么发现?你能根据更相减损术设计程序,求两个正整数的最大公约数吗?思考?辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构 程序：INPUT “a,b”;a,bi=0WHILE a MOD 2=0 AND b MOD 2=0 a=a/2 b=b/2 i=i+1 WEND DOIF b>a THENt=aa=bb=tEND IFa=a-bLOOP UNTIL a=bPRINT a*2^iEND辗转相除法与更相减损术的区别：小 结（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到的。作业：P50 习题：1.3 第1题再见