programa - Código para el Divisor común más grande en Python
minimo comun multiplo 2 numeros python (16)
El mayor divisor común (GCD) de ayb es el número más grande que los divide a ambos sin resto.
Una forma de encontrar el GCD de dos números es el algoritmo de Euclides, que se basa en la observación de que si r es el resto cuando a se divide por b , entonces gcd(a, b) = gcd(b, r) . Como caso base, podemos usar gcd(a, 0) = a .
Escribe una función llamada gcd que toma los parámetros a y b y devuelve su máximo común divisor.
Este código calcula el gcd de más de dos números dependiendo de la opción dada por # el usuario, aquí el usuario da el número
numbers = [];
count = input ("HOW MANY NUMBERS YOU WANT TO CALCULATE GCD?/n")
for i in range(0, count):
number = input("ENTER THE NUMBER : /n")
numbers.append(number)
numbers_sorted = sorted(numbers)
print ''NUMBERS SORTED IN INCREASING ORDER/n'',numbers_sorted
gcd = numbers_sorted[0]
for i in range(1, count):
divisor = gcd
dividend = numbers_sorted[i]
remainder = dividend % divisor
if remainder == 0 :
gcd = divisor
else :
while not remainder == 0 :
dividend_one = divisor
divisor_one = remainder
remainder = dividend_one % divisor_one
gcd = divisor_one
print ''GCD OF '' ,count,''NUMBERS IS /n'', gcd
Para a>b :
def gcd(a, b):
if(a<b):
a,b=b,a
while(b!=0):
r,b=b,a%r
a=r
return a
Para a>b a<b :
def gcd(a, b):
t = min(a, b)
# Keep looping until t divides both a & b evenly
while a % t != 0 or b % t != 0:
t -= 1
return t
Creo que otra forma es usar recursión. Aquí está mi código:
def gcd(a, b):
if a > b:
c = a - b
gcd(b, c)
elif a < b:
c = b - a
gcd(a, c)
else:
return a
El intercambio de valores no funcionó bien para mí. Así que configuré una situación similar a un espejo para los números que se ingresan en a <b OR a> b:
def gcd(a, b):
if a > b:
r = a % b
if r == 0:
return b
else:
return gcd(b, r)
if a < b:
r = b % a
if r == 0:
return a
else:
return gcd(a, r)
print gcd(18, 2)
Está en la biblioteca estándar .
>>> from fractions import gcd
>>> gcd(20,8)
4
Código fuente del módulo de inspect en Python 2.7:
>>> print inspect.getsource(gcd)
def gcd(a, b):
"""Calculate the Greatest Common Divisor of a and b.
Unless b==0, the result will have the same sign as b (so that when
b is divided by it, the result comes out positive).
"""
while b:
a, b = b, a%b
return a
A partir de Python 3.5, gcd está en el módulo math ; el uno en fractions está en desuso. Además, inspect.getsource ya no devuelve el código fuente explicativo de ninguno de los métodos.
Esta versión de código utiliza el algoritmo de Euclid para encontrar GCD.
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)
Los algoritmos con mn pueden correr terriblemente largo.
Este funciona mucho mejor:
def gcd(x, y):
while y != 0:
(x, y) = (y, x % y)
return x
Una solución muy concisa usando la recursión:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a%b)
en python con recursión:
def gcd(a, b):
if a%b == 0:
return b
return gcd(b, a%b)
#This program will find the hcf of a given list of numbers.
A = [65, 20, 100, 85, 125] #creates and initializes the list of numbers
def greatest_common_divisor(_A):
iterator = 1
factor = 1
a_length = len(_A)
smallest = 99999
#get the smallest number
for number in _A: #iterate through array
if number < smallest: #if current not the smallest number
smallest = number #set to highest
while iterator <= smallest: #iterate from 1 ... smallest number
for index in range(0, a_length): #loop through array
if _A[index] % iterator != 0: #if the element is not equally divisible by 0
break #stop and go to next element
if index == (a_length - 1): #if we reach the last element of array
factor = iterator #it means that all of them are divisibe by 0
iterator += 1 #let''s increment to check if array divisible by next iterator
#print the factor
print factor
print "The highest common factor of: ",
for element in A:
print element,
print " is: ",
greatest_common_devisor (A)
a=int(raw_input(''1st no /n''))
b=int(raw_input(''2nd no /n''))
def gcd(m,n):
z=abs(m-n)
if (m-n)==0:
return n
else:
return gcd(z,min(m,n))
print gcd(a,b)
Un enfoque diferente basado en el algoritmo de euclides.
def gcd(a,b):
if b > a:
return gcd(b,a)
r = a%b
if r == 0:
return b
return gcd(r,b)
def gcd(m,n):
return gcd(abs(m-n), min(m, n)) if (m-n) else n
def gcdIter(a, b):
gcd= min (a,b)
for i in range(0,min(a,b)):
if (a%gcd==0 and b%gcd==0):
return gcd
break
gcd-=1
def gcdRecur(a, b):
''''''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
''''''
# Base case is when b = 0
if b == 0:
return a
# Recursive case
return gcdRecur(b, a % b)
gcd = lambda m,n: m if not n else gcd(n,m%n)