Почему моя программа GCD на C не работает?

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

#include <stdio.h>

int gcd(int m, int n);

int main() {
    return gcd(60, 24);
}

int gcd(int m, int n) {
    if (m < n) {
        //swapping both a and b
        m = m + n;
        n = m - n;
        m = m - n;
    }
    if (m == n) {
        return m;
    } else {
        return gcd(n, m % n);   
    }
}

c function recursion algorithm greatest-common-divisor
person ThisSiteSucks    schedule 29.01.2016    source источник
comment
Ваше условие прекращения недостаточно широкое; не всегда в конце концов m==n выполняется в конце (фактического) алгоритма. Примеры помогают (например, gcd(4, 2) -> gcd(2, 0)...)   -  person Pachelbel    schedule 30.01.2016
comment
Да, это правда, но, на самом деле, для всех положительных чисел они в конечном итоге сводятся к нулю, кроме того, главное, что я хочу знать, это почему эта программа не работает для gcd (60,24), что, я почти уверен, придет к ноль, если мы следуем алгоритму Евклида.   -  person ThisSiteSucks    schedule 30.01.2016
comment
Итак, (60, 24) -> (24, 12) -> (12, 0). Ваш алгоритм продолжается. А это плохо...   -  person Pachelbel    schedule 30.01.2016
comment
Большинство случаев в конечном итоге достигнет (m, 0) в качестве последней итерации. В этот момент он должен вернуть m. Вместо этого он попытается оценить m % 0, что, конечно же, вызовет ошибку. Измените условие m == n на n == 0, чтобы исправить это.   -  person Tom Karzes    schedule 30.01.2016
comment
Спасибо, Пахельбель и @Tom Karzes Большое спасибо. Хотя я сохранил это условие m==n, чтобы программа не начала вычисления, потому что совершенно очевидно, что gcd будет m, если m==n. Поэтому я просто добавлю еще одну проверку для if(n==0) вместо того, чтобы просто заменить оператор m==n if. Спасибо. :D   -  person ThisSiteSucks    schedule 30.01.2016
comment
Выбранный вами метод обмена чувствителен к переполнению. Используйте временную переменную или полностью избегайте замены.   -  person axiac    schedule 30.01.2016
comment
Посмотрите на решение, опубликованное пользователем 3386109. Он полностью исключает подкачку и является более простым и эффективным, чем другие решения.   -  person Tom Karzes    schedule 30.01.2016

Ответы (2)


arrow_upward
4
arrow_downward

gcd(60, 24) -> gcd(24, 12) -> gcd(12, 0).

Это означает, что вам нужно добавить чек.

if ( n == 0 )
{
   return m;
}

or

if ( m%n == 0 )
{
   return n;
}

Вы также можете удалить код замены переменных с помощью другого вызова функции со значениями, замененными в вызове.

int gcd(int m, int n) {

   if (m < n) {
      return gcd(n, m);
   }

   if (m%n == 0) {
      return n;
   } else {
      return gcd(n, m % n);   
   }
}
person R Sahu    schedule 29.01.2016
comment
Это должно заменить проверку m == n. То есть это не добавленная проверка, а исправленная проверка. - person Tom Karzes; 30.01.2016
comment
Это решение выполняет две операции % за итерацию, когда требуется только одна (если только компилятор не подменяет операцию). Гораздо лучшим решением будет просто проверить наличие нулевого операнда. Не говоря уже о том, что это решение терпит неудачу, если операнд равен нулю (чего не сделает ни один хороший алгоритм gcd). - person Tom Karzes; 30.01.2016
comment
@TomKarzes, я поиграл с идеей использования первого условия - if ( n == 0 ) return m;. Я колебался, потому что не был уверен, каково математическое определение НОД между ненулевым числом и нулем. Что происходит, когда main звонит gcd(20, 0). Я понимаю, что этот вызов приведет к сбою программы. Тем не менее вопрос остается в памяти. - person R Sahu; 30.01.2016
comment
Взгляните на решение, опубликованное пользователем 3386109. Это намного проще и эффективнее. - person Tom Karzes; 30.01.2016
comment
@TomKarzes, это точно чище. Не могу точно сказать, что он эффективнее. - person R Sahu; 30.01.2016
comment
Конечно, это более эффективно. Посмотрите на работу, проделанную за итерацию в нетерминальном случае: здесь выполняются две операции %, два сравнения, два условных перехода. Другое решение выполняет одно сравнение, одну условную ветвь и одну целочисленную операцию %. В зависимости от накладных расходов на вызовы потенциально может быть в два раза быстрее. - person Tom Karzes; 30.01.2016
comment
@TomKarzes, то, что ты говоришь, имеет смысл. - person R Sahu; 30.01.2016
comment
if ( m%n == 0 ) { return n; } приводит к UB, когда n == 0. - person chux - Reinstate Monica; 26.11.2020

arrow_upward
7
arrow_downward

Код для рекурсивного НОД выглядит так

int gcd(int m, int n)
{
    if (n==0)
        return m;

    return gcd(n, m % n);
}

Нет необходимости менять местами аргументы, так как об этом позаботится рекурсия. Например, рассмотрим gcd(24, 60). В данном случае n=60 и m % n = 24%60 = 24. Таким образом, рекурсивный вызов gcd(60,24) автоматически меняет местами аргументы.

person user3386109    schedule 29.01.2016
comment
Да, это намного чище и эффективнее принятого решения. - person Tom Karzes; 30.01.2016
comment
Найдены только дела с UB: gcd(INT_MIN,-1), gcd(-1, INT_MIN). gcd() действительно предназначен для аргументов без знака. - person chux - Reinstate Monica; 26.11.2020