# 最大公约数的编程求解

## 迭代法

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)

# 其他递归问题

## 汉诺塔

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))

145 篇文章47 人订阅

0 条评论