求最大公约数的算法（来自软件工程ＱＱ群）

火麟蚀日(309762472) 11:13:36

int funl(int m, int n)

{

   while(m!=n)

   {

      if( m > n )

         m = m - n ;

      else

         n = n - m;

      }

   }

}

求最大公约数的方法。

谁能跟我解释一下它的原理？

快乐永远(43984229) 11:14:29

辗转相除法

快乐永远(43984229) 11:14:42

中国古代求最大公约数的方法

火麟蚀日(309762472) 11:15:14

哦

快乐永远(43984229) 11:15:51

除,是"扣除","减掉"的意思.原理很好懂,

快乐永远(43984229) 11:16:05

假设2个数A,B

快乐永远(43984229) 11:16:18

公约数 t

快乐永远(43984229) 11:16:44

A=at     B=bt

那么A-B=(a-b)t

快乐永远(43984229) 11:17:05

所以A和B的查必然也可以用t整除

火麟蚀日(309762472) 11:17:24

哦，谢谢了