C/C++

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

Не понимаю как работает Алгоритм Евклида, вот код который нашёл в инете
#include <iostream>
using namespace std;


int gcd(int a, int b)
{

while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}

int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a, b);
}


На бумаге посчитал
Вводим 12 и 8
с = a % b тоесть 12 % 8 = 4
a = b значит a = 8
b = c значит b = 4

Функция возврашяет Переменную а, значит должна вернуть 8!! но возврашяет 4!!! Как? я не спал часов 14, так что без Хейта!
Станислав Трофимов
Станислав Трофимов
11
обычно смотрят в отладчике, но вот на бумаге:

a = 12, b = 8 - передаём в функцию gcd

b!=0     // да, 8 не равно 0, крутим цикл:
c = a%b   // 12%8 = 4, значит: a = 12, b = 8, с = 4
a = b     // получаем: a = 8, b = 8, с = 4
b = c     // получаем: a = 8, b = 4, с = 4
первый проход завершен

b!=0     // да, 4 не равно 0, крутим цикл:
c = a%b   // 8%4 = 0, значит: a = 8, b = 4, с = 0
a = b     // получаем: a = 4, b = 4, с = 0
b = c     // получаем: a = 4, b = 0, с = 0
второй проход завершен

b!=0     // нет, 0 равно 0, выходим из цикла

return a;   // возвращаем a = 4
ВЛ
Вадим Лутфуллин
81 444
Лучший ответ
Станислав Трофимов Не умею я откладку юзать, сколько гайдов не смотрел у меня не выходит, ставлю точку остановы, говорят жми f11 жму и ничего
Станислав Трофимов А так спасибо за понятный ответ
while (b != 0) цикл выполняется пока b не станет 0, так что ваше b = 4 не есть ==
СЛ
Степан Лебедев
64 430
Нурсултан Габдулхат Ты хоть че не спишь что работаешь что ли ?.
Я то в такое время, нет в 12 уже сплю.
А щас настроение дерьмо.
b = 4 Условие цикла не выполнено значит цикл повторится т. е. никакого «Функция возврашяет Переменную а,» из твоих рассуждений не произойдет а цикл «while (b != 0)» повторится с новыми значениями переменных.
Юрий Самсонов
Юрий Самсонов
12 593
Без хейта ты че дурачок сразу не мог спросить !.
РБ
Ринат Багаутдинов
2 780

Похожие вопросы