Пусть два начальных числа first и second. Выберем меньшее из них и присвоим значение переменной gcd. Пока first или second не делятся на gcd без остатка, следует выполнять цикл, в котором уменьшаем переменную gcd на единицу. Когда цикл закончится в переменной gcd будет НСД для чисел first и second Напишите программу, которая для двух положительных целых чисел находит НДС. Примечание: Для условия цикла в пункте 3 необходимо помнить, что цикл while выполняется при True, а наш цикл должен закончиться, только если gcd разделил оба числа без остатка. Можно также обьяснение что не так делал
Отслеживать
задан 3 дек 2022 в 23:05
13 5 5 бронзовых знаков
Полагаю опечатались? ибо от перестановки мест делимого и делителя — результат меняется.(внимательно на условие)
3 дек 2022 в 23:20
А где именно опечатался в условие блока if или while?
3 дек 2022 в 23:23
if gcd % first == 0 and gcd % second => if first % gcd == 0 and second % gcd
3 дек 2022 в 23:25
Получаю следующее сообщение: Переменная gcd имеет не верное значение, 374 должно быть: nod=25 first=375 second=575.Очень странно
#37. Алгоритм Евклида для нахождения НОД | Python для начинающих
Источник: ru.stackoverflow.com
Вычисление наибольшего общего делителя двух целых чисел
Напишите программу для вычисления наибольшего общего делителя двух целых чисел. Задачу решим двумя способами: используя оператор repeat, используя оператор while.
Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел m и n называется наибольший из их общих делителей. Обозначение: НОД(m, n).
Например, найдем НОД(12, 8):
Выпишем все делители числа 12: 1, 2, 3, 4, 6, 12;
Выпишем все делители числа 8: 1, 2, 4, 8;
Выпишем все общие делители чисел 12 и 8: 1, 2, 4. Из них наибольшее число – 4. Это и есть НОД чисел 12 и 8.
Решение
Воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:
1) Если m неравно n, перейти к шагу 2, в противном случае вывести m и закончить алгоритм;
2) Если m > n, заменить m на m − n, в противном случае заменить n на n − m;
3) Перейти на шаг 1
Как видим, в шаге 2 большее из двух текущих чисел заменяется разностью большего и меньшего.
Приведем пример для чисел 12 и 8:
1) Так как 12 > 8, заменим 12 на 12 − 8 = 4;
2) Так как 8 > 4, заменим 8 на 8 − 4 = 4;
3) 4 = 4, конец.
Пишем программу: нахождения НОД и НОК двух чисел | Алгоритм Евклида
С использованием оператора while.
Алгоритм на естественном языке:
1) Ввод m и n;
2) Запуск цикла с предусловием m n. В цикле:
Если m > n, то переменной m присвоить m − n, иначе переменной n присвоить n − m;
3) Вывод m:
Код:
program nod1;
var
x, y: integer;
nod: integer;
begin
writeln (‘m=’);
readln (m);
writeln (‘n=’);
readln (n);
while m<>n do
if m>n then m:=m-n
else n:=n-m;
nod:=m;
writeln(‘НОД = ‘, nod)
end.
С использованием оператора repeat.
Код:
program nod2;
var
x, y: integer;
nod: integer;
begin
writeln (‘m=’);
readln (m);
writeln (‘n=’);
readln (n);
repeat
if m>n then m:=m-n;
if m until m=n;
nod:=m;
writeln(‘НОД = ‘, nod)
end.
Источник: infedu.ru
Реализация НОК и НОД на C++ (алгоритм Евклида)
Реализуем алгоритмы из статьи «Алгоритмы вычисления НОД и НОК» на языке С++. Первый (не самый эффективный вариант) вычисления НОД через многократное вычитание меньшего числа из большего:
unsigned int greatest_common_divisor(unsigned int a, unsigned int b) < if (a == b) return a; if (a >b) return greatest_common_divisor(a-b, b); return greatest_common_divisor(a, b-a); >
Более эффективный алгоритм вычисления НОД, использующий остаток от деления:
unsigned int greatest_common_divisor(unsigned int a, unsigned int b) < if (a % b == 0) return b; if (b % a == 0) return a; if (a >b) return greatest_common_divisor(a%b, b); return greatest_common_divisor(a, b%a); >
Функция вычисления НОК:
unsigned int least_common_multiple(unsigned int a, unsigned int b) < return (a*b)/greatest_common_divisor(a,b); >
31.10.2019 в 06:47 #6097
Вычислить НОД можно и без рекурсии. Код, приведнный ниже, был написан как пример к уроку по теме «Циклы в языке С++«. Задача: Реализуйте программу, вычисляющую наибольший общий делитель двух целых чисел (алгоритм Евклида). Решение:
#include using namespace std; int main() < int y, x; cin >> x >> y; while (x != y) < if (x>y) < x = x-y; >else < y = y-x; >> cout
Еще одна реализация алгоритма Евклида использует функцию swap : Перед разбором реализации на Пролог рекомендую посмотреть «Алгоритм Евклида (наибольший общий делитель)«. Ниже реализован вариант алгоритма с делением:
int NOD(int a, int b) < if (a < b) < swap(a, b); >while (a % b != 0) < a = a % b; swap(a, b); >return b; >
Функция swap выполняет обмен значений двух переменных. Она есть в стандартной библиотеке. Если в данный момент не понятно как она работает — замените ее на:
int t = a; a = b; b = t;
21.06.2021 в 19:39 #8105
Задача: Найти наименьшее общее кратное для всех элементов массива — минимальное число, которое делится на все элементы массива без остатка. Также, найти НОД всех элементов массива. Решение: Вот тут приведены алгоритмы расчета НОК и НОД для двух чисел.
Ясно, что наиболее эффективный алгоритм расчета НОК двух чисел — это произведение чисел поделить на их НОД. По содержимому статьи ясно что НОК(а1, а2, а3, . аN) равен НОК(НОК(НОК(А1, А2), А3). АN) . Таким образом, для расчета НОК массива чисел надо многократно расчитывать НОД двух чисел, реализация этой функции на С++ взята тут. Реализация на Си (функции чуть-чуть изменены, так как добавлена самописная функция swap):
#include #include void read_array(int n, int** values) < for (int i = 0; i < n; ++i) < printf(«values[%d] = «, i); scanf(«%d», >> void print_array(int n, int* values) < for (int i = 0; i < n; ++i) < printf(«values[%d] = %dn», i, values[i]); >> void swap(int* a, int* b) < int tmp = *a; *a = *b; *b = tmp; >int gcd(int a, int b) < if (a < b) < swap(b); >while (a % b != 0) < a = a % b; swap(b); >return b; > int gcd_n(int n, int* values) < if (n == 0) return -1; if (n == 1) return values[0]; int gcd_value = gcd(values[0], values[1]); for (int i = 2; i < n; ++i) < gcd_value = gcd(gcd_value, values[i]); >return gcd_value; > int lcm(int a, int b) < return (a*b)/gcd(a, b); >int lcm_n(int n, int* values) < if (n == 0) return -1; if (n == 1) return values[0]; int lcm_value = lcm(values[0], values[1]); for (int i = 2; i < n; ++i) < lcm_value = lcm(lcm_value, values[i]); >return lcm_value; > int main()
Источник: pro-prof.com