求最大公约数的算法(来自软件工程QQ群)

火麟蚀日(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

哦,谢谢了

know parents' hardship when I am a father

  Yesterday morning,daughter had cough continually suddenly.We took her to a 儿科西医。But no effection,from yesterday night to this morning,she cought very frequently.We desided to take her to a 中医(we take her to him often),and ask doctor to use injection for her to stop this bad trend.

  These things are always bother us very much.Her mother got a cold for taking care of her last night.I am very solicitous too.

a new bad habit

  It's eating 零食 too much.Last sunday,we took her go to street,she asked for 零食 all the afternoon.This habit need to be controled and corrected.I think,child like a little tree,need correcting at any time.

a little cartoon fan

  About three weeks ago,wife bought some cartoon vcd for daughter,includes:Cat Fish,White Snow Princess,伊索allegory,etc..Soon,daughter became a real cartoon fan,she always sees a same vcd again and again.This makes us feel worried.Because watch TV too long time will hurt her eyes!We must restrict her the time of watching cartoon.

  We can feel daughter's goodness when she watch the cartoon.When she saw the crocodile will eat the dog,she would worry to shed tears.Although we told her that wasn't in real world,she took about a week time to understand our meaning.Now,she doesn't act too worry when she see the same cartoon.