Главная » Реализация известных алгоритмов на языке программирования Python

Алгоритм Евклида (нахождение наибольшего общего делителя)

Опубликовано plustilino в Январь 10, 2010 - 13:39. Changed Январь 3, 2011 - 18:48

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.
Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Описание алгоритма нахождения НОД делением

  1. Большее число делим на меньшее.
  2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)
12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6

Исходный код на Python

a = 50
b = 130
 
while a!=0 and b!=0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print (a+b)

Примечание к коду. В цикле в a или b записывается остаток от деления. Когда остатка нет (мы не знаем в а он или b, поэтому проверяем оба условия), то цикл завершается. В конце выводится сумма a и b, т.к. мы не знаем, в какой переменной записан НОД, а в одной из них в любом случае 0, который на результат суммы никак не влияет.

Описание алгоритма нахождения НОД вычитанием

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6

Исходный код на Python

a = 50
b = 130
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print (a)

Оформление кода в виде функции

def gcd(a,b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a        
    print (a)

Блок-схема "Алгоритм Евклида"

Блок-схема к алгоритму `Алгоритм Евклида`
#1Опубликовано Гость в Январь 8, 2012 - 13:51.

пишите: Если есть остаток, то

пишите:
Если есть остаток, то большее число заменяем на остаток от деления.

а в примере всё не так
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)
#2Опубликовано Гость в Декабрь 11, 2011 - 02:58.

алгоритма Евклида

Dim n As Double
Dim m As Double
 
Private Sub Command1_Click()
m = InputBox("Ââåäèòå çíà÷åíèå ïåðâîãî ÷èñëà")
n = InputBox("Ââåäèòå çíà÷åíèå âòîðîãî ÷èñëà")
While (m <> 0) And (n <> 0)
If m > n Then
m = m - n
End If
n = n - m
Wend
Print m
End Sub
Вот и все.
#3Опубликовано plustilino в Декабрь 11, 2011 - 10:06.

Это случайно не VisualBasic?

Это случайно не VisualBasic?
#4Опубликовано Гость в Июнь 23, 2011 - 12:42.

зачем вы усложняете....

def gcd(a, b):
    return b and gcd(b, a%b) or a
#5Опубликовано Гость в Апрель 3, 2011 - 17:11.

Рекурсивно

def gcd(n,m):
    if n<m:
        n, m = m, n
    if m<>0:
        return gcd(m, n%m)
    else:
        return n
#6Опубликовано Гость в Июнь 23, 2011 - 12:41.

зачем вы усложняете....

def gcd(a, b):
    return b and gcd(b, a%b) or a
#7Опубликовано Гость в Февраль 3, 2011 - 17:07.

проще же

def getNOD(n,m):
 if n<m:
  p=m
  m=n
  m=p
 while 1:
  p=n%m
  if not p:
   return m
  n=m
  m=p
#8Опубликовано Гость в Июнь 20, 2011 - 01:15.

ну тогда ужdef nod(x,y):

ну тогда уж

def nod(x,y):
   while x*y!=0:
      if x>y: x=x%y
      else: y=y%x
   return x+y
#9Опубликовано Гость в Ноябрь 18, 2011 - 10:04.

короче не могу

a,b=50,130
while b!=0: a,b=b,a%b
print a