注册 登录
每天一道算法题

第一章:计算最值,次最值

第二章:进制的转换

第三章:质数,水仙花,公约数

第四章:子序列问题

首页 > 每天一道算法题 > 第三章:质数,水仙花,公约数 > 3.3节:最大公约数-欧几里得算法

3.3节:最大公约数-欧几里得算法

薯条老师 2021-04-07 10:43:50 205703 0

编辑 收藏

广州番禺Python, Java小班周末班培训

薯条老师的线下Python小班办得很好,学员的平均就业薪资有11K。线下小班培训的课程有Python爬虫,Python后端开发,Python办公自动化,Python大数据分析,Python量化投资,Java中高级后端开发。授课详情请点击:http://chipscoco.com/?cate=6

3.3.1 算法思路

公约数是指能同时整除n(n>1)个数的数,那么最大公约数就是这些公约数中的最大的数。

例如9和6的公约数有3和1,3能整除9和6,1也能整除9和6。很显然,二者的最大公约数就是3。

在程序中计算两个数的最大公约数,可采用欧几里得算法。该算法基于以下定理:

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

欧几里得算法的计算过程,以14和8为例:

(1) 14除以8,商为1,余数为6

(2) 8除以6,  商为1,余数为2

(3) 6除以2,  商为3,余数为0

当余数为0时,说明被整除,此时的被除数即为最大公约数。从以上计算过程可以分析出,从第2步开始,每一步的被除数都是上一步的余数。相信不少同学会对该计算过程感到疑惑,为什么被余数整除时,该余数就一定能整除第一步的两个数,且是最大的公约数?

3.3.2 定理证明

首先任何一个正整数n都可以由其它正整数进行线性表示: n = kp + r (r < p) 。

k 为 n 除以 p 的商,r 为 n 除以 p 的余数。

假设a为n与p的一个公约数,那么n/a+p/a也一定是整数。可将(n/a+p/a)变换为(n+p)/a, 进一步可变换为(n-kp)/a。由等式n = kp + r可得r = n-kp, 等式两边同时除以a,可得r/a = (n-kp)/a, 既然(n-kp)/a为整数,那么r/a也一定是整数,由此可证明a也是p和r的公约数。因(n,p)和(p,r)的公约数相等,则其最大公约数也相等

继续回到14和8的例子,14与8的最大公约数等于8与6的最大公约数(14不能被8整除),8与6的最大公约数等于6与2的最大公约数(8不能被6整除)。当6与2相除时,余数为0,说明6能被2整除, 此时的余数2就是6与2的最大公约数,也就是14与8的最大公约数。

3.3.3 算法实现

# __author__ = 薯条老师

import random

def gcd(a, b):    
    while a != 0:        
        a, b = b % a, a     
  return b
  
  
if  __name__ == "__main__":
    a, b = random.randint(1, 1000), random.randint(1,  1000)
    print("{}与{}的最大公约数:{}".format(a,b, gcd(a,  b)))

欧几里得算法的递归版本:

# __author__ = 薯条老师

import random

def gcd(a, b):    
    return b if a == 0 else gcd(b % a, a)
    
    
    
if __name__ == "__main__":
    a, b =  random.randint(1, 1000), random.randint(1,  1000)
    print("{}与{}的最大公约数:{}".format(a, b,  gcd(a, b)))

3.3.4 最具实力的小班培训

来这里参加Python和Java小班培训的学员大部分都找到了很好的工作,平均月薪有11K,学得好的同学,拿到的会更高。由于是小班教学,所以薯条老师有精力把每位学员都教好。打算参加线下小班培训的同学,必须遵守薯条老师的学习安排,认真做作业和项目。把知识学好,学扎实,那么找到一份高薪的工作就是很简单的一件事。

(1) Python后端工程师高薪就业班,月薪11K-18K,免费领取课程大纲
(2) Python爬虫工程师高薪就业班,年薪十五万,免费领取课程大纲
(3) Java后端开发工程师高薪就业班,月薪11K-20K, 免费领取课程大纲
(4) Python大数据分析,量化投资就业班,月薪12K-25K,免费领取课程大纲

扫码免费领取学习资料:



欢迎 发表评论:

请登录

忘记密码我要注册

注册账号

已有账号?请登录