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

Question

[Natalia Veis]

Сижу целый день и не могу понять как выполняется программа по коду.. Нахождение наибольшего общего делителя.
Вот код

Def gcd(a, b) :
    return a If b==0 else gcd(b, a%b)

Что непонятно: в случае если -а<b , как она будет работать.?
Вот к примеру
gcd(243,456)
Она будет делать - (456, 243%456)?

Comments

[Wataru]

Оберните весь код в тег code. И у вас там наверное сравнение парсер съел в вопросе. Его тоже в code оберните.

[Natalia Veis]

Wataru, спасибо, научилась, сделала)

Answer 1

[Alexandroppolus]

если a < b, то a%b всегда равно a

Comments

[Natalia Veis]

Спасибо, что объяснили.. Существует правило такое? Или это как то логично можно объяснить?

[Alexandroppolus]

Наталья Соляник, это напрямую следует из определения остатка

https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D...

r = x%y
тогда x = n*y + r

в нашем случае

a = 0*b + a

[Natalia Veis]

Простите пожалуйста, если я задаю глупый вопрос но все же..
Почему в нашем случаеa=0*b+aмы прибавляем а, но не остаток от деления?

[AVKor]

если a < b, то a%b всегда равно a

$ python3
Python 3.9.2 (default, Feb 28 2021, 17:03:44) 
[GCC 10.2.1 20210110] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> a = -3
>>> b = 2
>>> a % b
1
>>>

[Alexandroppolus]

Наталья Соляник,

Почему в нашем случаеa=0*b+aмы прибавляем а, но не остаток от деления?

потому что "а" - и есть остаток от деления

[Alexandroppolus]

AVKor, с отрицательными числами своя наркомания. Я про неотрицательные говорил

[Natalia Veis]

AVKor, спасибо большое, я разобралась, нашла правило.
Если при делении с остатком делимое меньше делителя, то их неполное частное равно нулю, остаток равен делимому.. Не знала это правило, восполняю знания школьной математики..
Только теперь не пойму почему в вашем примере остаток от деления не равен -3

[AVKor]

Alexandroppolus,

с отрицательными числами своя наркомания.

Какая ещё "наркомания"? С определением ознакомьтесь.

Я про неотрицательные говорил

Ниоткуда не следует в ответе.

И в вопросе нет такого ограничения.

И НОД определяется не только для неотрицательных.

[Natalia Veis]

AVKor, во всяком случае, я разобралась в алгоритме, за это спасибо)

[Natalia Veis]

Alexandroppolus, спасибо, что объяснили, ещё бы сидела до завтра, не зная куда думать)

[AVKor]

Наталья Соляник, Точно? Советую посчитать несколько примеров на бумажке, а потом свериться с питоновским результатом. Для отрицательных чисел, в том числе.

[Natalia Veis]

AVKor, спасибо, буду упражняться сейчас)

[Alexandroppolus]

AVKor, если числа отрицательные, то в разных языках программирования может быть разный остаток. См. параграф "Знак остатка" в ссылке на википедию. Поскольку для НОД не имеет значения знак чисел (НОД всегда положительный), правильнее будет не заморачиваться и взять числа по модулю.

[AVKor]

Alexandroppolus,

если числа отрицательные, то в разных языках программирования может быть разный остаток

См. тег вопроса и приведённый код. И ваш (неправильный) ответ:

если a < b, то a%b всегда равно a

Answer 2

[Александр Скуснов]

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

Comments

[Natalia Veis]

Я не понимаю, почему в первом вызове не происходит вычисления остатка от деления, а они просто меняются местами..

Answer 3

[bbkmzzzz]

Def gcd(a, b) :
    return a If b==0 else gcd(b, a%b)
# эквивалентно
def gcd(a,b):
    if b == 0:
        return a
    else:
        #вызываем сами себя (рекурсия)
        gcd(b, a % b)

Comments

[Natalia Veis]

Я понимаю, что это рекурсия.
Не понимаю почему если a<bто а и b меняются местами и не происходит деления в первом вызове функции ?

[Akina]

Не понимаю почему если a < b то а и b меняются местами

Меняются местами - потому что условие в IF ложно, и выполняется ветка ELSE.

не происходит деления в первом вызове функции ?

Там нет деления. Вообще. Есть получение остатка от целочисленного деления. Но т.к. a < b, то остаток равен значению a.