第一章第一章 算法初步算法初步 1.3 1.3 算法案例算法案例2020年9月28日1例：求下面两个正整数的最大公约数：例：求下面两个正整数的最大公约数：（1）求）求25和和35的最大公约数的最大公约数（2）求）求49和和63的最大公约数的最大公约数25（1）5535749（2）77639所以，所以，25和和35的最大公的最大公约数为约数为5所以，所以，49和和63的最大公的最大公约数为约数为7思考：除了用这种方法外还有没有其它方法？思考：除了用这种方法外还有没有其它方法？例：如何算出例：如何算出8251和和6105的最大公约数？的最大公约数？辗转相除法与更相减损术2020年9月28日2一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的上面的除法，直到大数被小数除尽，则这时
