最大公约数与递归
最大公约数
定义
所谓最大公约数，即是两个正整数都可以整除的最大整数。
特性
最大公约数，是两个数共有的素因数乘积。 例如： 462 = 2*3*7*11 1071=3*3*7*17 所以，最大公约数为3*7=21
辗转相除法
辗转相除法首先出现在欧几里得的《几何原本》，在中国则可以追溯到东汉出现的《九章算术》。
其核心思想是：每次取两个数中最小的数和最大数除以最小数的余数，重复进行直到余数为0，这时两个数相等，为最大公约数。
举例如下： （200，160）-》（160，40）-》（40，0）-》40为最大公约数
图形化的描述如下图：
这里写图片是描述
求一个长方形的长和宽的最大公约数，就相当于在里面填上面积最大的小正方形，不断地辗转相除，最后得到可以划分长方形的最大正方形。
最大公约数的编程求解
迭代法
def gcdIter(a, b):
'''
input: a, b: positive integers
output: a positive integer, the greatest common divisor of a & b.
'''
low = min(a,b)
while (low>0):
if((a%low==0) & (b%low==0)):
return low
else:
low -= 1以上迭代法肯定能达到终止条件，但是问题规模大的时候速度会很慢。
递归法
def gcdRecur(a, b):
'''
input: a, b: positive integers
output: a positive integer, the greatest common divisor of a & b.
'''
if (b==0):
return a
else:
return gcdRecur(b,a%b)对以上代码做一下简要说明： 1. 每次递归的内容是获得两个较小的数和大数除以小数的余数。分三种情况，一种是gcd(max,min)=gcd(min,max%min)正好符合情况；另一种是gcd(min,max) = gcd(max,min%max=min)正好转换到第一种情况，第三种两者相等不言。 2. 递归的终止条件是余数为0，易证：无论如何，总会达到终止条件（两个素数的极限为1）。
其他递归问题
汉诺塔
这个问题很难用迭代法解决，只能采用递归，将大问题分解为小问题。
def printMove(fr, to):
print('move from ' + str(fr) + ' to ' + str(to))
def Towers(n, fr, to, spare):
if n == 1:
printMove(fr, to)
else:
Towers(n-1, fr, spare, to)
Towers(1, fr, to, spare)
Towers(n-1, spare, to, fr)斐波那契数列
def fib(x):
"""assumes x an int >= 0
returns Fibonacci of x"""
assert type(x) == int and x >= 0
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)回文
def isPalindrome(s):
def toChars(s):
s = s.lower()
ans = ''
for c in s:
if c in 'abcdefghijklmnopqrstuvwxyz':
ans = ans + c
return ans
def isPal(s):
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and isPal(s[1:-1])
return isPal(toChars(s))本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年06月29日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录