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

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

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

  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)

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

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

на джаве здесь

на джаве здесь есть
https://www.youtube.com/watch?v=wxJidn84WzY

while (b) { a %= b; swap

while (b) { 
	a %= b; 
	swap (a,b);
}
gcd = a;
cout << "Наибольий общий делитель: " << gcd << endl;

с++ готовый вид #include

с++ готовый вид

#include <iostream>
#include <conio.h>
#include <clocale>
using namespace std;
int main()
{ 
setlocale (LC_CTYPE,"rus");
unsigned long long int a,b;
cout<<"введите а и б : ";
cin>>a>>b;
do
{
	if(a>b) a=a%b;
	else b=b%a;
}
while(a!=0&&b!=0);
	cout<<"наибольший общий делитель : "<<a+b<<endl;
_getch();
}

а что значит a != b что за

а что значит a != b
что за знак восклицания?
это факториал?

a не равно b

a не равно b

это значит "не а"

это значит "не а"

Это означает, что a не равно

Это означает, что a не равно b.

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

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

а в примере всё не так
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)

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

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
Вот и все.

почему Double? GCD для целых

почему Double? GCD для целых чисел, иначе операция остаток от деления ( % ) не определена

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

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

Точно, visual basic

Точно, visual basic

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

def gcd(a, b):
    return b and gcd(b, a%b) or a

Рекурсивно

def gcd(n,m):
    if n<m:
        n, m = m, n
    if m<>0:
        return gcd(m, n%m)
    else:
        return n

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

def gcd(a, b):
    return b and gcd(b, a%b) or a

спасибо, что упростил так,

спасибо, что упростил так, что я ничего вообще не понимаю.
Дословно понимаю - "возврати мне, функция b И рекурсию для меньшего, остатка от деления большего на меньшее ИЛИ а.
Не пойму, как функция принимает решение - возвращать ТО ИЛИ ТО???!!!!

Важна последовательность

Важна последовательность логических операторов. Сначала and, потом or.
1) Если b ноль, то операнд после and не проверяется (т. к. нет смысла, т.к в любом случае будет ложь, раз уж первый операнд 0). Далее идем на or и проверяется a. Она и возвращается.
2) Если b не ноль, то выражение после and выполняется. Если оно возвращает отличное от нуля число, то его и вернет текущий вызов. Проверять второй операнд после or нет смысла.

Понять как все это работает действительно трудно из-за рекурсии.

вот рекурсию я, в принципе

вот рекурсию я, в принципе понимаю. Это функция вызывает сама себя с новыми параметрами глубже и глубже, пока выполняется условие запуска самой себя. Помню, хороший пример с Ханойскими башнями.
А вот что лингвистика языков программирования все человечней и человечней - к этому я никак не привыкну.
Не за горами время, когда программист просто будет объяснять машине, какая ему нужна программа и машина сама будет составлять код.

Исходно естественные языки

Исходно естественные языки позволяют человеку нечетко формулировать мысль, может быть неоднозначность трактовок. Формальные же языки исключают всякую неоднозначность. Чтобы прийти к "общему знаменателю", либо человек должен формализовать свой естественный язык, четко и однозначно излагать свои мысли (а это уже и есть язык программирования), либо среда разработки должна содержать функцию формализации (скажем, по определенным заложенным правилам). Второй вариант опасней, т. к. человек может иметь в виду одно, а программа запрограммирует другое.

проще же

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

ну тогда уж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

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

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

#include void main() { int

#include

void main()
{
int a,b;
a=50;
b=130;

while(a&&b)
a>b ? a%=b : b%=a;

std::cout< }