最大公约数与递归

最大公约数

定义

所谓最大公约数,即是两个正整数都可以整除的最大整数。

特性

最大公约数,是两个数共有的素因数乘积。 例如: 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))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券