文档章节

求一组数的最大公约数

a
 avalon3515
发布于 2016/02/01 15:48
字数 298
阅读 33
收藏 0
点赞 1
评论 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

数论——(扩展)欧几里得算法辨析

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

qq_39670434 ⋅ 2017/12/12 ⋅ 0

c语言实现求最大公约数的三种方法

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

Landscape_ ⋅ 2017/03/22 ⋅ 0

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

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

duanbowen ⋅ 2017/05/17 ⋅ 0

数论基础 扩展欧几里得 线性筛 逆元 欧拉函数 Lucas定理

扩展欧几里得 欧几里得算法,又叫辗转相除法,用于求两个数的最大公约数(gcd)。 由此可以得到最小公倍数 (先除防止溢出)。 扩展欧几里得,是用于解出方程 的一组解的。比如方程 ,可以解...

myjs999 ⋅ 2017/10/25 ⋅ 0

最大公约数与最小公倍数(gcd,lcm)

先来说求最大公约数的方法 1.欧几里得算法(辗转相除法) int gcd(int a,int b){return b==0?a:gcd(b,a%b);}设两数为a、b(a>b),用gcd(a,b)表示a,b的最大公约数,r=a (mod b) 为a除以b的余数...

ZscDst ⋅ 2017/07/19 ⋅ 0

求两个数的最大公约数:Java、Scala

辗转相除法.   当两个数都较大时,采用辗转相除法比较方便.其方法是:   以小数除大数,如果能整除,那么小数就是所求的最大公约数.否则就用余数来除刚才的除数;再用这新除法的余数去...

hanzhankang ⋅ 2014/02/16 ⋅ 0

【语法篇】6、while循环

一、while循环 1、for语句vs while语句 对于明确知道需要重复次数的事情,我们可以用for语句快速地实现,譬如我们输出从1~10的数,只需要for(int i=1; i<=10; i++)就可以了,但是有时候我们...

沧海无雨 ⋅ 2017/09/27 ⋅ 0

程序员的数学思维修炼(趣味阅读)

没有密密麻麻的文字让人恐惧。 这本书最喜欢的两段文字: “1加1等于10”,“所有的事件都有产生它的原因” 可能一本书让读者顿有所悟的时候,它才会变的有存在的意义。 不去思考它存在的意义...

李老三 ⋅ 2016/10/20 ⋅ 0

金阳光测试算法专题——精选小算法汇总

[本文出自天外归云的博客园] 本文是对金阳光测试算法专题中一些小算法的精选汇总,利于思考与收获。 注意:原版是用java解,以下题目部分使用python解(python3),对于题目中描述不清楚的地...

天外归云 ⋅ 2017/06/13 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

NFS介绍 NFS服务端安装配置 NFS配置选项

NFS介绍 NFS是Network File System的缩写;这个文件系统是基于网路层面,通过网络层面实现数据同步 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netapp公司参与并主导...

lyy549745 ⋅ 28分钟前 ⋅ 0

Spring AOP 源码分析 - 筛选合适的通知器

1.简介 从本篇文章开始,我将会对 Spring AOP 部分的源码进行分析。本文是 Spring AOP 源码分析系列文章的第二篇,本文主要分析 Spring AOP 是如何为目标 bean 筛选出合适的通知器(Advisor...

java高级架构牛人 ⋅ 51分钟前 ⋅ 0

HTML-标签手册

标签 描述 <!--...--> 定义注释。 <!DOCTYPE> 定义文档类型。 <a> 定义锚。超链接 <abbr> 定义缩写。 <acronym> 定义只取首字母的缩写。 <address> 定义文档作者或拥有者的联系信息。 <apple......

ZHAO_JH ⋅ 53分钟前 ⋅ 0

SylixOS在t_main中使用硬浮点方法

问题描述 在某些使用场景中,应用程序不使用动态加载的方式执行,而是跟随BSP在 t_main 线程中启动,此时应用代码是跟随 BSP 进行编译的。由于 BSP 默认使用软浮点,所以会导致应用代码中的浮...

zhywxyy ⋅ 今天 ⋅ 0

JsBridge原理分析

看了这个Github代码 https://github.com/lzyzsd/JsBridge,想起N年前比较火的Hybrid方案,想看看现在跨平台调用实现有什么新的实现方式。代码看下来之后发现确实有点独特之处,这里先把核心的...

Kingguary ⋅ 今天 ⋅ 0

Intellij IDEA神器常用技巧五-真正常用快捷键(收藏级)

如果你觉得前面几篇博文太啰嗦,下面是博主多年使用Intellij IDEA真正常用快捷键,建议收藏!!! sout,System.out.println()快捷键 fori,for循环快捷键 psvm,main方法快捷键 Alt+Home,导...

Mkeeper ⋅ 今天 ⋅ 0

Java 静态代码分析工具简要分析与使用

本文首先介绍了静态代码分析的基本概念及主要技术,随后分别介绍了现有 4 种主流 Java 静态代码分析工具 (Checkstyle,FindBugs,PMD,Jtest),最后从功能、特性等方面对它们进行分析和比较,...

Oo若离oO ⋅ 今天 ⋅ 0

SpringBoot自动配置小记

spring-boot项目的特色就在于它的自动配置,自动配置就是开箱即用的本源。 不过支持一个子项目的自动配置,往往比较复杂,无论是sping自己的项目,还是第三方的,都是如此。刚接触会有点乱乱...

大_于 ⋅ 今天 ⋅ 0

React jsx 中写更优雅、直观的条件运算符

在这篇文字中我学到了很多知识,同时结合工作中的一些经验也在思考一些东西。比如条件运算符 Conditional Operator condition ? expr_if_true : expr_if_false 在jsx中书写条件语句我们经常都...

开源中国最帅没有之一 ⋅ 今天 ⋅ 0

vim编辑模式与命令模式

5.5 进入编辑模式 从编辑模式返回一般模式“Esc” 5.6 vim命令模式 命令 :“nohl”=no high light 无高亮,取消内容中高亮标记 "x":保存退出,和wq的区别是,当进入一个文件未进行编辑时,使...

弓正 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部