Приведем реализацию алгоритма Евклида нахождения наибольшего общего делителя двух целых неотрицательных чисел. В качестве аргументов методу gcd передаются 2 числа, в качестве результата он возвращает их НОД. Вычисления производятся с типом данных int (при необходимости, разумеется, можно заменить его на любой другой целочисленный).
import java.io.PrintWriter;
import java.util.Scanner;
public class Solution <
public static void main(String[] args) <
// Для считывания воспользуемся классом Scanner
// Для вывода — классом PrintWriter
Scanner scanner = new Scanner(System.in);
PrintWriter printWriter = new PrintWriter(System.out);
int a;
a = scanner.nextInt();
int b;
b = scanner.nextInt();
// После выполнения программы необходимо закрыть
// потоки ввода и вывода
scanner.close();
printWriter.close();
>
private static int gcd(int a, int b) <
if (b == 0) <
return a;
> else <
return gcd(b, a % b);
>
>
>
Очевидно, метод gcd можно вычисляться нерекурсивно, например, с помощью следующего кода.
private static int gcd(int a, int b) <
while (a != 0 && b != 0) <
if (a > b) <
a %= b;
> else <
b %= a;
>
>
// Так как после выполнения цикла одна из
// переменных гарантированно равна нулю, то
// сумма (a + b) будет НОД
return a + b;
>
Алгоритм Евклида
Python
Pascal:
Данная статья не подлежит комментированию, поскольку её автор ещё не является полноправным участником сообщества. Вы сможете связаться с автором только после того, как он получит приглашение от кого-либо из участников сообщества. До этого момента его username будет скрыт псевдонимом.
- 23 сентября 2019 в 18:25 Простейшая змейка на Python менее, чем в 100 строчек кода
- 7 октября 2019 в 12:28 Биткоин клиппер на C#, или как не потерять свои битки
- 21 октября 2019 в 13:58 Как легко создать графический интерфейс Java с помощью WindowBuilder в Eclipse
- 4 ноября 2019 в 20:32 Пример создания утилиты для Unigraphics NX с помощью библиотеки NXOpen на языке Java
- 15 ноября 2019 в 11:44 Почему стоит научиться > сайты, или как написать свой первый парсер на Python
Это «Песочница» — раздел, в который попадают дебютные посты пользователей, желающих стать полноправными участниками сообщества.
Если у вас есть приглашение, отправьте его автору понравившейся публикации — тогда её смогут прочитать и обсудить все остальные пользователи Хабра.
Чтобы исключить предвзятость при оценке, все публикации анонимны, псевдонимы показываются случайным образом.
Я видел, что такая функция существует для BigInteger , то есть BigInteger#gcd . Есть ли другие функции в Java, которые также работают для других типов ( int , long или Integer )? Кажется, это имело бы смысл, как java.lang.Math.gcd (со всеми видами перегрузок), но его там нет. Это где-то еще?
(не путайте этот вопрос с «как я могу реализовать это сам», пожалуйста!)
20 ответов
для int и долго, как примитивы, не очень. Для Integer, возможно, кто-то написал один.
учитывая, что BigInteger является (математическим/функциональным) надмножеством int, Integer, long и Long, если вам нужно использовать эти типы, преобразуйте их в BigInteger, выполните GCD и преобразуйте результат обратно.
насколько я знаю, для примитивов нет встроенного метода. Но что-то простое, как это должно сделать трюк:
вы также можете однострочный, если вы в такого рода вещи:
следует отметить, что нет абсолютно нет разница между ними, когда они компилируются в один и тот же байтовый код.