文档章节

求一组数的最大公约数

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

没有更多内容

加载失败,请刷新页面

加载更多

5whys分析法在美团工程师中的实践

前言 网站的质量和稳定性对于用户和公司来说至关重要,但是在网站的快速发展过程中,由于各种原因导致事故不可避免的发生,这些大大小小的事故对公司难免会造成一些负面的影响,为了避免同类...

Skqing
20分钟前
0
0
Android 接收监听开机完成,并且开机自启动

1,定义一个广播接收者的类 ,并重写抽象方法 public class BootCompleteReceiver extends BroadcastReceiver 2,在Androidmanifest 注册 <receiver android:name=".receiver.BootCompleteRece......

lanyu96
23分钟前
1
0
小程序记录

1、button的边框、角等需要在伪元素after修改去除

originDu
26分钟前
0
0
微博什么技术啊……还说支持八个明星并发出轨,结果…

是的,大家可能都知道了,女神张靓颖结婚了。。 我去,写错了,是————赵丽颖。 为什么我头脑一瞬间出现的是张靓颖,作为一个码农,技术宅,拼音缩小都是 ZLY,博主我真有点傻傻分不清楚了...

Java技术栈
26分钟前
3
0
模块化

1,什么是模块化? 模块化是指将一个复杂的系统分解为多个模块,方便编码。 2,为什么要用模块化? 降低复杂性,降低代码耦合度,部署方便,提高效率。 3,模块化的好处? a,避免命名冲突,减少...

羊皮卷
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部