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

  • Автор темы amfisat
  • Дата начала
A

amfisat

#1
Всем привет!
Запутался с вроде бы элементарной задачкой: найти НОД 2 чисел. B) Дело в том, что программа работает только для ненулевых чисел, а хотелось бы совершенства: если 1 из них = 0, то НОД ведь будет равен второму числу! - но программка это не понимает. Посмотрите, пжлст, и укажите, что доделать:
C++:
gcd(int a, int b)
{
while a != b
{
if a > b
a = a - b
else
b = b - a
}
return a
}
Спасибо
 
A

astronom

#2
Алгоритм должен не просто не понимать, он должен вообще зациклиться при таких условиях :)

По идее, можно сотворить что-нибудь некрасивое на тему:

Код:
gcd(int a, int b) {
int temp = 0;

// обмениваем значения a и b, чтобы не проходить ветку else, когда НОД уже определен
if(a < b) {
temp = a;
a = b;
b = temp;
}

/* 
Если b = 0, приравниваем ее к а и тем самым, обходим цикл стороной.
Переменная а не может быть равна нулю, ибо, в этом случае, мы обменяли бы ее с b.
*/
if (!b) {
b = a;
}

while(a > b) {
a = a - b;
}

return a
}
p.s. если a = 0 и b = 0, функция вернет 0 ;)