Java - Рекурсивная функция алгоритма Евклида

Я не могу показаться, чтобы преобразовать следующий алгоритм в Java успешно, пожалуйста, простите ужасное качество изображения, но вопрос я работаю спрашивает:Java - Рекурсивная функция алгоритма Евклида

Euclidean Algorithm

Я попытался использовать следующий код для представления евклидова алгоритма, но он, похоже, не работает. Я действительно не знаю, как я буду представлять его в Java-коде. Любая помощь?

public static int gcd(int x, int y) { 
    if (y == 0) { 
     return x; 
    } else if (x >= y && y > 0) { 
     return gcd(y, (x % y)); 
    } 
}

спасибо.

источник

2011-12-31 mino

Правильно следуйте алгоритму текстового блока. Это просто, что алгоритм текстовой книги является неполным - поскольку он не учитывает случай, когда ни одна из категорий не выполняется. – Mysticial

Как это не работает? Что на самом деле происходит, когда вы называете это? Какие аргументы вы передаете, и что он возвращает? –

@KeithThompson Я уверен, что непосредственная проблема OP заключается в том, что код не компилируется. – dasblinkenlight

Между х и у нет произвольного порядка.

источник

2011-12-31 18:30:00

'return y == 0? x: gcd (y, x% y); 'все, что вам нужно. не имеет значения, что больше. Тем не менее, это займет 1 рекурсию. – st0le

FYI: Этот ответ ранее был более полезным (см. Историю изменений). – nobar

Вы почти находитесь. Вам нужно подумать о том, что произойдет, когда y > x, и вернуть результат из финальной ветки else (подсказка: x и y могут свободно переключаться местами).

источник

2011-12-31 18:20:28 dasblinkenlight

Вы почти находитесь.

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

Это действительно зависит от того, собираетесь ли вы передавать отрицательные значения y в эту функцию. Если вы ожидаете только положительных значений, просто выбросьте исключение.

public static int gcd(int x, int y) { 

    if (y == 0) { 

     return x; 

    } else if (x >= y && y > 0) { 

     return gcd(y, (x % y)); 

    } 

    throw 
     new IllegalArgumentException(
      String.format(
       "Unexpected values for x(%d) and y(%d)", 
       Integer.valueOf(x), 
       Integer.valueOf(y) 
      ) 
     ); 
}

источник

2011-12-31 18:21:09

В идеале я хотел бы включить отрицательные значения. – mino

@ m92 Формула повторения из назначения не охватывает отрицательные числа. – dasblinkenlight

Ваш код не заполнен!

Что делать, если x < y? Тогда ваш код не возвращает значение!

В книге не упоминается, что два параметра функции не обязательно должны находиться в порядке убывания (то есть x >= y). Что вам нужно сделать, это вычислить gcd, учитывая этот факт.

Просто вы можете сделать следующее:

public static int gcd (int x , int y) 
{ 
    if (y == 0)       
     return x; 
    else if (x >= y && y > 0) 
     return gcd (y , x % y); 
    else return gcd (y , x);  // if x < y then go ahead and switch them around. 
}

источник

2011-12-31 18:40:44

Вот что у меня есть, что счета для отрицательных чисел:

public static int gcd(int x, int y) 
{ 
    if (y == 0) 
     return x; 
    if (x < 0) 
     return gcd(x * -1, y); //turns the first parameter to a positive if it's initally negative 
    if (y < 0) 
     return gcd(x, y * -1); //turns the second parameter to a positive if it's initally negative 
    if (y <= x && x % y == 0) 
     return y; 

    return gcd(y, x%y); 
}

Примечания с отрицательными числами, если вы пытаетесь найти наибольший общий делитель, и любое из чисел отрицательно, вы можете просто изменить его на положительный, и результат будет таким же.

Если оба числа отрицательные, тогда я не уверен, что должен быть gcd. 1? -1? idk, поэтому я оставил это. Код, который я только что рассматривал, как будто они оба положительные.

источник

2014-09-30 09:20:59

Java - Рекурсивная функция алгоритма Евклида

ответ

Смежные вопросы