例1:用更相减损术求98与63的最大公约数 因为63不是偶数,所以 98-63=35 63-35=28 35-28=7, 28-7=21, 21-7=14, 14-7=7. 所以最大公约数是7
例1：用更相减损术求98与63的最大公约数. 98-63=35， 14-7=7. 21-7=14， 28-7=21， 35-28=7， 63-35=28， 因为63不是偶数，所以 所以最大公约数是7
例2分别用辗转相除法和更相减损术求168与93 的最大公约数 辗转相除法: 更相减损术 168=93×1+75, 168-93=75, 93=75×1+18, 93-75=18, 75=18×4+3, 75-18=57, 18=3×6 57-18=39 39-18=21 21-18=3 18-3=15 15-3=12 12-3=9 9-3=6, 6-3=3
例2 分别用辗转相除法和更相减损术求168与93 的最大公约数. 168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6. 辗转相除法： 更相减损术: 168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3
例3用更相减损术求80与36的最大公 约数
例3 用更相减损术求80与36的最大公 约数
例4求325,130,270三个数的最大公约数 因为325=130×2+65,130=65×2,所以325与130 的最大公约数是65 因为270=65×4+10,65=10×6+5,10=5×2,所 以65与270最大公约数是5 故325,130,270三个数的最大公约数是5
例4 求325，130，270三个数的最大公约数. 因为325=130×2+65，130=65×2，所以325与130 的最大公约数是65. 因为270=65×4+10，65=10×6+5，10=5×2，所 以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5
练习:用更相减损术求两个正整数m,n的最大公 约数,可以用什么逻辑结构来构造算法?其算法步骤 如何设计? 第一步,给定两个正整数m,nm>n) 第二步,计算mn所得的差k 第三步,比较n与k的大小,其中大者用m表示, 小者用n表示 第四步,若mn,则m,m的最大公约数等于m 否则,返回第二步 讨论:该算法的程序框图如何表示?
练习:用更相减损术求两个正整数m，n的最大公 约数，可以用什么逻辑结构来构造算法？其算法步骤 如何设计？ 第一步，给定两个正整数m，n(m>n). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表示， 小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m； 否则，返回第二步. 讨论:该算法的程序框图如何表示？