Мы уже не раз складывали два простых числа, две десятичные дроби или даже простое число с десятичной дробью. Однако мир состоит не только из примитивных данных, порой нам приходится работать и с дробями, с обыкновенными дробями.
Обыкновенные дроби
#
сложение дробей
Обыкновенная дробь, как мы знаем из школы, состоит из двух частей: верхней и нижней. Это если не считать чёрточку посередине за часть дроби. Верхнюю часть дроби в математике принято называть числитель, а нижнюю часть знаменатель. В английском соответственно 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);
}
}
Дополнительные ссылки
#
- https://docs.oracle.com/javase/8/docs/api/java/lang/Number.html
- https://habr.com/ru/post/205106/
- 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 из двух неотрицательных целых чисел:
- gcd(0,, gcd(n1,, gcd(0,
- Когда n1 и n2 являются четными целыми числами, то gcd(n1, * gcd(n1/2, n2/2) , так как 2 является общим делителем
- Если n1 четное целое число и n2 нечетное целое число, то gcd(n 1,(n1/2, n2) , так как 2 не является общим делителем и наоборот
- Если 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
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
ДмитрийДмитрий
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
51.4k194 золотых знака56 серебряных знаков232 бронзовых знака
ответ дан 10 мар 2022 в 7:09
Improve Article
Save Article
Like Article
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