文档章节

求一组数的最大公约数

a
 avalon3515
发布于 2016/02/01 15:48
字数 298
阅读 57
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

错误: 找不到或无法加载主类

在IDEA的使用过程中,经常断掉服务或者重启服务,最近断掉服务重启时突然遇到了一个启动报错: 错误:找不到或无法加载主类 猜测:1,未能成功编译; 尝试:菜单---》Build---》Rebuild Pro...

安小乐
13分钟前
1
0
vue路由传参,刷新页面,引发的bug

最近遇到一个bug 通过vue路由跳转到页面, 然后接参控制(v-if ),成功显示 而刷新页面,显示失败。 苦苦地找了半天原因,打印参数发现正确,再打印下类型......,路由跳过来会保持传参时的...

hanbb
14分钟前
0
0
【58沈剑 架构师之路】InnoDB,select为啥会阻塞insert?

MySQL的InnoDB的细粒度行锁,是它最吸引人的特性之一。 但是,如《InnoDB,5项最佳实践》所述,如果查询没有命中索引,也将退化为表锁。 InnoDB的细粒度锁,是实现在索引记录上的。 一,Inn...

张锦飞
17分钟前
0
0
冒泡,选择和插入排序比较

/** * 冒泡排序,两层嵌套循环,内层局部比较后,找出最大或者最小数据并交换数据,使其局部有序,外层用于比较剩余元素,相较于选择排序,选择排序相当于是冒泡的一个优化版本(减少了交换...

strict_nerd
18分钟前
0
0
html内联(行内)元素、块级(块状)元素和行内块元素分类

HTML可以将元素分类方式分为内联(行内)元素、块级(块状)元素和行内块元素三种。 注:HTML是标签语言,那么既然是标签,就可以自己定义一些自己元素(如<wode>自定义的元素</wode>等),自...

NB-One
24分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部