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

Тема в разделе "Общие вопросы по С и С++", создана пользователем amfisat, 18 сен 2010.

  1. amfisat

    amfisat Гость

    Всем привет!
    Запутался с вроде бы элементарной задачкой: найти НОД 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
    }
    Спасибо
     
  2. astronom

    astronom Гость

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

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

    Код (Text):
    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 ;)
     
Загрузка...

Поделиться этой страницей