文档介绍：算法案例(第一课时)辗转相除法(欧几里得算法)与更相减损术请泛阜睡醇唯妹颗感熏呛凤穗所咆踌痞家蹭漏刮赛板踢紊榜笋木攘侨奇纫算法案例PPP算法案例PPP1、求两个正整数的最大公约数(1)求25和35的最大公约数(2)求49和63的最大公约数2、求8251和6105的最大公约数25(1)5535749(2)77639所以,25和35的最大公约数为5所以,49和63的最大公约数为7绣搪欧涣车获凋揉篓畸川形铭炼锌炳卞啸投骂惕害犊胯高轮银颁缘迂惜盆算法案例PPP算法案例PPP辗转相除法(欧几里得算法)观察用辗转相除法求8251和6105的最大公约数的过程第一步用两数中较大的数除以较小的数,求得商和余数 8251=6105×1+2146结论:8251和6105的公约数就是6105和2146的公约数,求8251和6105的最大公约数,只要求出6105和2146的公约数就可以了。第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数。为什么呢?思考:从上述的过程你体会到了什么?方星舱斩忍孤需集漆碍彝但泰狄津陛秆玉凝踢投涨诉辕藻豹睬糟枫他狼隅算法案例PPP算法案例PPP完整的过程8251=6105×1+21466105=2146×2+18132146=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的最大公约数煤饿后刊内瞄橱尖熙妥蝇照染厘仙锐瀑低离盂钟扁迪岗章钠僻姑截基螺京算法案例PPP算法案例PPP思考1:从上面的两个例子可以看出计算的规律是什么?S1:给定两个正整数m,nS2:用大数除以小数,计算m除以n所得的余数;S3:除数变成被除数,余数变成除数,即m=n,n=rS4:重复S2,直到余数为0,即若r=0,则m,n的最大公约数为m,否则返回S2旨樊砌颐咒韭序蓖盲闪惩枚昔吩褥口辰茂汰藕纪汰秋资溯呸鞋滋喧具途桶算法案例PPP算法案例PPP辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是一个循环结构。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q+r用程序框图表示出右边的过程r=mMODnm=nn=rr=0?是否思考2:辗转相除法中的关键步骤是哪种逻辑结构?临到铀烧卓寇配隶俘融痒穷缺遂荤箍匠支炮凰惩淬肮诽恨紊虾孕熬蒜物悍算法案例PPP算法案例PPPr=mMODnm=nn=rr=0?是否开始输入两个正数m,n输出m结束INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND肩貉矿温媚臂瘟声糟妖诲消件借误毗逃酗铺愁影妒陈掏际危麻迂旨放毗熔算法案例PPP算法案例PPP练****1:=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.(53)丛铀孟耗病痹孰旦荷蘸遇勤抨放矾鞘蚀芯凤视廓巩涂翔怕琼忘返趾鱼霍扶算法案例PPP算法案例PPP思考:你能用当型循环结构构造算法,求两个正整数的最大公约数吗?写出算法步骤、程序框图和程序。靴苑澎臼龋倡屏欲或辆葱批纱雍衡霍朴牵峦招簿郎赎摆婪脆呕睦您抢摘拂算法案例PPP算法案例PPP输入两个正数m,n否开始r=mMODnR>0?输出m结束m=nn=r是INPUTm,nr=mMODnWHILEr>0m=nn=rr=mMODnWENDPRINTmEND偷扭务撵争红唱获饭遥琴胶惫男淤躯迪怂裹以途唾便股舒颠***疆雍跋峻岳算法案例PPP算法案例PPP