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

Java Basic: упражнение 157 с решением

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

Согласно Википедии «Алгоритм Евклида основан на том принципе, что наибольший общий делитель двух чисел не изменяется, если большее число заменяется его разностью с меньшим числом. Например, 21 — это НОД 252 и 105 (поскольку 252 = 21 × 12 и 105 = 21 × 5), и то же число 21 также является НОД 105 и 252 — 105 = 147. Поскольку эта замена уменьшает большее из двух чисел , повторение этого процесса дает последовательно уменьшающиеся пары чисел до тех пор, пока два числа не станут равными. Когда это произойдет, они будут НОД исходных двух чисел. Путем обращения шагов, НОД можно выразить как сумму двух исходных чисел каждое. умноженное на положительное или отрицательное целое число, например 21 = 5 × 105 + (−2) × 252. Тот факт, что НОД всегда можно выразить таким образом, известен как тождество Безу «.

Графическая презентация:

Пример решения:

Код Java:

  import java.util.Scanner; общедоступный класс Solution {public static int  евклид (int x, int y) {if (x == 0 ||  y == 0) {return 1;} if (x  

Пример вывода:

 result: 24result: 1 

Блок-схема:

Редактор кода Java:

Предыдущий: Напишите программу Java, которая возвращает наибольшее целое число, но не больше логарифма с основанием 2 данного целого числа.
Далее: Напишите программу на Java для создания двухмерного массива (mxm) A [] [], такого что A [i] [j] истинно, если I и j простые числа и не имеют общих делителей, в противном случае A [i] [j] становится ложным.

Оцените статью
nanomode.ru
Добавить комментарий