aとbの最大公約数(GCD)は、余りなしで両方を除算する最大数です。
2つの数値のGCDを見つける1つの方法は、ユークリッドのアルゴリズムです。これは、がで除算されr
たときの余りであるという観測に基づいています。基本ケースとして、を使用できます。a
b
gcd(a, b) = gcd(b, r)
gcd(a, 0) = a
a
パラメータを受け取りb
、最大公約数を返すgcdという関数を記述します。
aとbの最大公約数(GCD)は、余りなしで両方を除算する最大数です。
2つの数値のGCDを見つける1つの方法は、ユークリッドのアルゴリズムです。これは、がで除算されr
たときの余りであるという観測に基づいています。基本ケースとして、を使用できます。a
b
gcd(a, b) = gcd(b, r)
gcd(a, 0) = a
a
パラメータを受け取りb
、最大公約数を返すgcdという関数を記述します。
>>> from fractions import gcd
>>> gcd(20,8)
4
inspect
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
Python 3.5の時点で、gcd
はmath
モジュール内にあります; の1つfractions
は非推奨です。さらに、inspect.getsource
どちらのメソッドについても説明的なソースコードを返さなくなりました。
このバージョンのコードは、ユークリッドのアルゴリズムを利用して GCD を見つけます。
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)
gcd = lambda m,n: m if not n else gcd(n,m%n)
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)
Euclid のアルゴリズムに基づく別のアプローチ。
別の方法は、再帰を使用することだと思います。これが私のコードです:
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
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
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
def gcd(a,b):
if b > a:
return gcd(b,a)
r = a%b
if r == 0:
return b
return gcd(r,b)
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
値の交換はうまくいきませんでした。そのため、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)
#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: ",
maximum_common_devisor(A)