文档章节

求一组数的最大公约数

a
 avalon3515
发布于 2016/02/01 15:48
字数 298
阅读 37
收藏 0
#欧几里德定理求2个数的最大公约数
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

def mgcd(s):
    #两两求最大公约数,会得到1个数组,在这个数组里再两两求公约数,如此递归,最终会得到1个只有1个数的数组,就是最大公约数
    if len(s)==1:
        return s[0]
    elif len(s)==2:
        return gcd(s[0],s[1])
    else:
        cd=[]
        for i in s:
            #不求自己与自己的最大公约数
            if i!=s[0]:
                cd.append(gcd(s[0],i))
        #去除数组中的重复数据
        cd=list(set(cd))
        return mgcd(cd)
        
def greatest_common_divisor(*args):
    """
        Find the greatest common divisor
    """
    #两两求最大公约数,会得到1个数组,在这个数组里再两两求公约数,如此递归,最终会得到1个只有1个数的数组,就是最大公约数
    return mgcd(args)

if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert greatest_common_divisor(6, 4) == 2, "Simple"
    assert greatest_common_divisor(2, 4, 8) == 2, "Three arguments"
    assert greatest_common_divisor(2, 3, 5, 7, 11) == 1, "Prime numbers"
    assert greatest_common_divisor(3, 9, 3, 9) == 3, "Repeating arguments"

在checkio.org遇到的一道题,觉得挺有总结意义的。

© 著作权归作者所有

共有 人打赏支持
a
粉丝 0
博文 2
码字总数 482
作品 0
南京
程序员
数论常用内容——欧几里得算法与扩展欧几里得算法

欧几里得算法 欧几里得算法有一个为更多人所知的名字叫“辗转相除法”,它是用来求解两个数的最大公约数的算法 其计算原理依赖于下面的定理: 通过这个定理,我们可以很快的求解出两个数的最...

tick_tock97
2017/05/04
0
0
数论——(扩展)欧几里得算法辨析

欧几里得算法 欧几里得算法链接:传送门 欧几里得算法就是我们通常说的“辗转相除法” 扩展欧几里得 扩展欧几里得是用来求:已知 时,求解一组 ,使得 。 (根据裴蜀等式,一定存在整数解:裴...

qq_39670434
2017/12/12
0
0
c语言实现求最大公约数的三种方法

一、最大公约数 最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的...

Landscape_
2017/03/22
0
0
C语言 -- 递归求最大杏彩源码下载公约数和最小公倍数

递归求杏彩源码下载论坛:haozbbs.com Q1446595067最大公约数和最小公倍数 int gcd(int a, int b) { return a % b ? gcd(b, a % b) : b; } 用辗转相除法求最大公约数,用递归写的代码会比循环...

iuiu230
07/04
0
0
RSA的安全性---学习笔记(不包含数学关系的推导)

最近了解了RSA算法的安全性的基本原理,简单记录一下方便以后回顾(不包含数学公式的推导以及产生大质数和求模反元素的具体算法)。 RSA加密解密的数学公式: c=m^e%n m=c^d%n 需要的数学条件:...

duanbowen
2017/05/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

最全最强解析:支付宝钱包系统架构内部剖析(架构图)

支付宝系统架构概况 典型处理默认 资金处理平台 财务会计 支付清算 核算中心 交易 柔性事务 支付宝的开源分布式消息中间件–Metamorphosis(MetaQ) Metamorphosis (MetaQ) 是一个高性能、高可...

晨猫
29分钟前
4
0
竞品分析

那什么样的场景需要用关键纬度分析法分析竞品呢? 竞品分析的目的是为了看竞品们和自己产品重合的业务都具备哪些功能点,以及这些功能是怎么做的,以此确定自己产品的优化方向。 竞品们的业务...

于谦老师
37分钟前
1
0
OSChina 周三乱弹 —— 公司女同事约我

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:分享水木年华的单曲《蝴蝶花(2002年大提琴版)》 《蝴蝶花(2002年大提琴版)》- 水木年华 手机党少年们想听歌,请使劲儿戳(这里) ...

小小编辑
今天
1K
16
Linux环境搭建 | VMware下共享文件夹的实现

在进行程序开发的过程中,我们经常要在主机与虚拟机之间传递文件,比如说,源代码位于虚拟机,而在主机下阅读或修改源代码,这里就需要使用到 「共享文件」 这个机制了。本文介绍了两种共享文...

良许Linux
今天
9
0
JUC锁框架——AQS源码分析

JUC锁介绍 Java的并发框架JUC(java.util.concurrent)中锁是最重要的一个工具。因为锁,才能实现正确的并发访问。而AbstractQueuedSynchronizer(AQS)是一个用来构建锁和同步器的框架,使用A...

长头发-dawn
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部