Как найти нод чисел java

Мы уже не раз складывали два простых числа, две десятичные дроби или даже простое число с десятичной дробью. Однако мир состоит не только из примитивных данных, порой нам приходится работать и с дробями, с обыкновенными дробями.

Обыкновенные дроби
#

сложение дробей, пример

сложение дробей

Обыкновенная дробь, как мы знаем из школы, состоит из двух частей: верхней и нижней. Это если не считать чёрточку посередине за часть дроби. Верхнюю часть дроби в математике принято называть числитель, а нижнюю часть знаменатель. В английском соответственно numerator и denominator.

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

НОД — наибольший общий делитель
#

Greatest common divisor — GCD.

НОД´ом для чисел 25 и 15 является 5. Это наибольший общий делитель двух этих чисел.
Для чисел 9 и 15 НОД´ом является 3. Оба числа делятся на 3 без остатка. И три является наибольшим общим делителем.

Математика древняя наука и впервые НОД был описан Евклидом в третьем веке до нашей эры. Алгоритм нахождения назван в его честь — Алгори́тм Евкли́да.
В Java Алгоритм Евклида будет реализован вот так:

public static int euclideanAlgorithm(int a, int b) {
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

Этот алгоритм в цикле занимается вычитанием от одной переменной другой и в итоге находит нод. если задуматься, то “бесконечное” вычитание пока A не сравняется с B это деление с нахождением остатка деления. Сегодня у нас есть оператор модуло и мы можем “усовершенствовать” алгоритм:

public static int gcdAlgorithmModulo(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Этот же алгоритм мы можем решить с применением рекурсии, мы должны прописать условие выхода и само решение:

public static int gcdRecursionAlgorithm(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcdRecursionAlgorithm(b, a % b);
}

Это не единственные способы решения. Всегда ещё можно решить бинарным поиском. Но думаю на этом мы пока уже можем остановиться и сказать, что НОД мы находить научились и можем попробовать найти НОК.

НОК — Наименьшее общее кратное
#

Least common multiple — LCM

НОК — это произведение наших двух чисел и делении его на НОД. Реализуется это вот так:

public static int leastCommonMultiple(int a, int b) {
    return a / gcdRecursionAlgorithm(a, b) * b;
}

Теперь мы попробуем реализовать правильное “поведение” дробей.

public class Fraction {
    private int numerator;
    private int denominator;

    Fraction(int numerator) {
        this.numerator = numerator;
        this.denominator = 1;
    }

    public Fraction(int numerator, int denominator) {
        this.numerator = numerator;
        this.denominator = denominator;
    }

    public int getNumerator() {
        return numerator;
    }

    public int getDenominator() {
        return denominator;
    }

    public Fraction sum(Fraction fraction) {
        Fraction result = sum(fraction, this);
        return result;
    }

    public static Fraction sum(Fraction a, Fraction b) {
        // описать сложение;
        // выполнить сокращение дробей, если это возможно
        // находим нок знаменателей дробей
        // подставить полученное значение в знаменатель РЕЗУЛЬТАТА
        // Разделить нок на знаменатели данных дробей.
        // умножить числитель и знаменатель каждой дроби на дополнительный множитель

        int cDenominator = Math.nok(a.denominator, b.denominator);
        int cNumerator =
                a.numerator * (cDenominator / a.denominator) +
                        b.numerator * (cDenominator / b.denominator);

        Fraction c = new Fraction(cNumerator, cDenominator);
        return c;
    }

    @Override
    public String toString() {
        return "Fraction(дробь){" +
                "numerator(числитель)=" + numerator +
                ", denominator(знаменатель)=" + denominator +
                '}';
    }
}

class Math {
    static int nok(int a, int b) {
        return a * b / nod(a, b);
    }

    static int nod(int a, int b) {
        if (b == 0) {
            return a;
        }
        return nod(b, a % b);
    }
}

Дополнительные ссылки
#

  1. https://docs.oracle.com/javase/8/docs/api/java/lang/Number.html
  2. https://habr.com/ru/post/205106/
  3. https://www.baeldung.com/java-least-common-multiple

Автор оригинала: baeldung.

1. Обзор

В математике GCD из двух целых чисел, отличных от нуля, является самым большим положительным целым числом, которое делит каждое из целых чисел равномерно.

В этом уроке мы рассмотрим три подхода к нахождению Наибольшего общего делителя (GCD) двух целых чисел. Далее мы рассмотрим их реализацию на Java.

2. Грубая сила

Для нашего первого подхода мы перебираем от 1 до наименьшего заданного числа и проверяем, делятся ли заданные целые числа на индекс. Наибольший индекс, который делит заданные числа , является GCD данных чисел:

int gcdByBruteForce(int n1, int n2) {
    int gcd = 1;
    for (int i = 1; i <= n1 && i <= n2; i++) {
        if (n1 % i == 0 && n2 % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

Как мы видим, сложность приведенной выше реализации составляет O(min(n1, n2)) , потому что нам нужно повторить цикл в течение n раз (эквивалентно меньшему числу), чтобы найти GCD.

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

Во-вторых, мы можем использовать алгоритм Евклида, чтобы найти GCD. Алгоритм Евклида не только эффективен, но и прост в понимании и реализации с использованием рекурсии в Java.

Метод Евклида зависит от двух важных теорем:

  • Во – первых, если мы вычитаем меньшее число из большего числа, GCD не изменится – поэтому, если мы продолжим вычитание числа, мы в конечном итоге получим их GCD
  • Во-вторых, когда меньшее число точно делит большее число, меньшее число является GCD двух заданных чисел.

Обратите внимание в нашей реализации, что мы будем использовать модуль вместо вычитания, так как это в основном много вычитаний за раз:

int gcdByEuclidsAlgorithm(int n1, int n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcdByEuclidsAlgorithm(n2, n1 % n2);
}

Кроме того, обратите внимание, как мы используем n2 в позиции n1 и используем остаток в позиции n2 на рекурсивном шаге алгоритма .

Кроме того, сложность алгоритма Евклида равна O(Log min(n1, n2)) , что лучше по сравнению с методом грубой силы, который мы видели ранее.

4. Алгоритм Штейна или Двоичный алгоритм GCD

Наконец, мы можем использовать алгоритм Штейна, также известный как двоичный алгоритм GCD , чтобы найти GCD двух неотрицательных целых чисел. Этот алгоритм использует простые арифметические операции, такие как арифметические сдвиги, сравнение и вычитание.

Алгоритм Штейна неоднократно применяет следующие основные тождества, связанные с GCD, чтобы найти GCD из двух неотрицательных целых чисел:

  1. gcd(0,, gcd(n1,, gcd(0,
  2. Когда n1 и n2 являются четными целыми числами, то gcd(n1, * gcd(n1/2, n2/2) , так как 2 является общим делителем
  3. Если n1 четное целое число и n2 нечетное целое число, то gcd(n 1,(n1/2, n2) , так как 2 не является общим делителем и наоборот
  4. Если n1 и n2 являются нечетными целыми числами, и n1 , то gcd(n1, ((n1-n2)/2, n2) и наоборот

Мы повторяем шаги 2-4 до тех пор, пока n1 не станет равным n2 или n1 . GCD-это (2 n ) * n2 . Здесь n – это число раз, когда 2 встречается в n1 и n2 при выполнении шага 2:

int gcdBySteinsAlgorithm(int n1, int n2) {
    if (n1 == 0) {
        return n2;
    }

    if (n2 == 0) {
        return n1;
    }

    int n;
    for (n = 0; ((n1 | n2) & 1) == 0; n++) {
        n1 >>= 1;
        n2 >>= 1;
    }

    while ((n1 & 1) == 0) {
        n1 >>= 1;
    }

    do {
        while ((n2 & 1) == 0) {
            n2 >>= 1;
        }

        if (n1 > n2) {
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        n2 = (n2 - n1);
    } while (n2 != 0);
    return n1 << n;
}

Мы видим, что мы используем арифметические операции сдвига, чтобы разделить или умножить на 2. Далее, мы используем вычитание, чтобы уменьшить заданные числа.

Сложность алгоритма Штейна, когда n1 > n2 является O((журнал 2 n1) 2 ) в то время как. когда n1 < n2, это O((журнал 2 n2) 2 ).

5. Заключение

В этом уроке мы рассмотрели различные методы вычисления GCD двух чисел. Мы также реализовали их на Java и быстро рассмотрели их сложность.

Как всегда, полный исходный код наших примеров здесь, как всегда, на GitHub .

10 марта, 2014 | Автор:
| Категория:
Java, Алгоритмы |
Нет комментариев »

НОД (Наибольший общий делитель) или gcd (Greatest Common Divisor)
НОД — наибольшее число, которое является делителем одновременно для чисел a и b.
Реализация (Алгоритм Евклида):

long gcd(long a,long b){
	return b == 0 ? a : gcd(b,a % b);		
}

Применение:

System.out.println(gcd(10,24));//результат: 2
System.out.println(gcd(12,24));//результат: 12
System.out.println(gcd(11,24));//результат: 1

НОК (Наименьшее общее кратное) или lcm (Least Common Multiple)
НОК — наименьшее число, которое делится на a и b без остатка.
НОК можно найти через НОД по следующей формуле:
нок
Реализация:

long lcm(long a,long b){
	return a / gcd(a,b) * b;
}

Примечание: a / gcd(a,b) * b более предпочтительно, чем a * b / gcd(a,b), т.к. во втором случае при больших числах переполнение случиться намного раньше.
Применение:

System.out.println(lcm(3, 4));//результат: 12
System.out.println(lcm(3, 9));//результат: 9
System.out.println(lcm(5,12));//результат: 60

Поделиться данной статьей через:  

Не понимаю, что может быть не так?

Наибольший общий делитель (НОД).
Ввести с клавиатуры 2 целых положительных числа.
Вывести в консоль наибольший общий делитель.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;



public class NOD {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String X = reader.readLine();
        String Y = reader.readLine();
        reader.close();

        if (X.indexOf("-",0) == -1 || Y.indexOf("-",0) == -1) {
            try {
                int x = Integer.parseInt(X);
                int y = Integer.parseInt(Y);
                System.out.println(MostCommonЬultiple(x, y));
            } catch (Exception e) {}
        } else {}
    }

    public static int MostCommonЬultiple(int x, int y){
        List<Integer> arrayX = del(x);
        List<Integer> arrayY = del(y);
        List<Integer> XandY = CompareArray(arrayX,arrayY);
        return MaxOfCom(XandY);
    }

    public static List<Integer> del(int a){
        List<Integer> divider = new ArrayList<>();
        for (int i = 1; i <= a; i++) {
            if (a % i == 0) {
                divider.add(i);
            }
        }
        return divider;
    }

    public static List<Integer> CompareArray(List<Integer> a, List<Integer> b){
        List<Integer> compare = new ArrayList<>();
        for (int i = 0; i < a.size(); i++){
            for (int j = 0; j < b.size(); j++){
                if (a.get(i).equals(b.get(j))) compare.add(a.get(i));
            }
        }
        return compare;
    }

    public static int MaxOfCom(List<Integer> a){
        int max = a.get(0);
        for (int i = 0; i<a.size();i++){
            if(max<a.get(i)) max = a.get(i);
        }
        return max;
    }
}

задан 9 фев 2020 в 17:01

Sad Lama's user avatar

3

Для такой простой задачи это слишком сложный код. Всегда помните про KISS.

import java.util.Scanner;

    public class NOD {

        public static void main(String[] args) {
            try {
                Scanner sc = new Scanner(System.in);
                int nod = mostCommonMultiple(Integer.valueOf(sc.nextLine()),Integer.valueOf(sc.nextLine()));
                System.out.println("NOD: " + nod);            
            } catch (NumberFormatException | UnsupportedOperationException e) {
                System.out.println(e.getMessage());
            }

        }

        private static int mostCommonMultiple(int x, int y) {
            if (x<=0 || y<=0) throw new UnsupportedOperationException("Incorrect input");        
            while(x!=0 && y!=0){
                if (x>y) x=x%y;
                else y=y%x;
            }
            return x+y;
        }

    }

ответ дан 9 фев 2020 в 17:44

Дмитрий's user avatar

ДмитрийДмитрий

10.2k2 золотых знака10 серебряных знаков26 бронзовых знаков

Tак проще:

public static void main(String[] args) throws Exception {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int count;
    int x = 0;
    int y = 0;

    try {
        x = Integer.parseInt(reader.readLine());
        y = Integer.parseInt(reader.readLine());
    } catch (Exception e){
        System.out.println("Введи с клавиатуры 2 целых положительных числа.");
    } finally {
        reader.close();
    }

    count = Math.min(x, y);

    for (int n = count; n >= 1; n--){
        if (x % n == 0 && y % n == 0){
            count = n;
            break;
        }
    }

    System.out.println(count);
}

0xdb's user avatar

0xdb

51.4k194 золотых знака56 серебряных знаков232 бронзовых знака

ответ дан 10 мар 2022 в 7:09

Viktor Tsiabus's user avatar

Improve Article

Save Article

Like Article

  • Read
  • Discuss
  • Improve Article

    Save Article

    Like Article

    GCD of two numbers is the largest number that divides both of them. A simple way to find GCD is to factorize both numbers and multiply common factors.

    import java.util.*;

    import java.lang.*;

    class GFG {

        public static int gcd(int a, int b)

        {

            if (a == 0)

                return b;

            return gcd(b % a, a);

        }

        public static void main(String[] args)

        {

            int a = 10, b = 15, g;

            g = gcd(a, b);

            System.out.println("GCD(" + a + ", " + b + ") = " + g);

            a = 35;

            b = 10;

            g = gcd(a, b);

            System.out.println("GCD(" + a + ", " + b + ") = " + g);

            a = 31;

            b = 2;

            g = gcd(a, b);

            System.out.println("GCD(" + a + ", " + b + ") = " + g);

        }

    }

    Output:

    GCD(10, 15) = 5
    GCD(35, 10) = 5
    GCD(31, 2) = 1
    

    Time Complexity: O(Log min(a, b))
    Please refer complete article on Basic and Extended Euclidean algorithms for more details!

    Last Updated :
    04 Dec, 2018

    Like Article

    Save Article

    Понравилась статья? Поделить с друзьями:
  • Как надо составить схему слов
  • Minimum hardware check battlefield 1 как исправить
  • Как исправить колесо на мышке
  • Как найти настоящую индивидуалку
  • Как найти угол в градусах на часах