用Python实现常见算法 -- ["qingfeng"] (Date(2009-04-21T16:35:01Z)) TableOfContents

求最大公约数

分析：求最大公约数的算法思想：
(1) 对于已知两数m，n，使得m>n； 
(2) m除以n得余数r； 
(3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； 
(4) m←n，n←r，再重复执行(2)。 
例如: 求 m=14 ,n=6 的最大公约数. m n r

代码: 

   1 def f(m,n):
   2     r=m%n
   3     if r==0:return m/n
   4     return f(n,r)
   5 f(14,6)