Приведем 3 программы поиска наибольшего общего делителя двух натуральных чисел, основанных на:
- алгоритме Евклида
- перебора возможных делителей числа
- разложения чисел на простые множители
Что такое наибольший общий делитель двух натуральных чисел m и n, или НОД(m, n)
НОД двух натуральных чисел — это такое наибольшее натуральное число, которое одновременно делит без остатка оба этих числа.
Алгоритм Евклида
Евклид — древнегреческий математик, геометр, автор первого из дошедших до нас теоретических трактатов по математике.
Алгоритм Евклида — один из наиболее ранних численных алгоритмов в истории. Евклид впервые дал описание этого алгоритма в книгах «Начала». Изначально этот алгоритм назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль.
Сформулируем алгоритм
Пусть даны два натуральных числа m и n. Пока числа m и n не равны (или их разница не равна 0), большее число заменить их разницей. В качестве ответа взять любое из чисел.
Наибольший общий делитель. 5 класс.
Пусть m = 12, n = 18
12<>18, n = 18 — 12 = 6
12<>6, m = 12 — 6 = 6
Программа на языке программирования Паскаль (алгоритм Евклида)
writeln(‘Введите два натуральных числа m и n:’);
writeln( ‘НОД(m,n): ‘, m);
Результат запуска программы
Перебор возможных делителей числа
Будем использовать алгоритм, разобранный ранее в этом блоге.
Запустим цикл for с счетчиком k от 1 до n, будем проверять условие: если число n делится на значение счетчика k без остатка (n mod k = 0), то значение счетчика k — это делитель числа n, значение k можно вывести на экран или сохранить в отдельной переменной.
Поскольку нам нужен наибольший общий делитель чисел m и n, поэтому запустим цикл до минимального из чисел m и n (другое будет лишним), и будем проверять условие: если число m делится на значение счетчика цикла k без остатка и число n делится на значение счетчика цикла k без остатка одновременно (воспользуемся операцией and), это и будет их общий делитель.
Программа на языке программирования Паскаль (перебор возможных делителей числа)
var m, n, k, p:integer;
writeln(‘Введите два натуральных числа m и n:’);
for k:=1 to min(m,n) do
if (m mod k = 0) and (n mod k=0) then p:=k ;
Функция min будет работать в PascalABC.NET, в случае использования другой среды, нужно до цикла определить наибольшее число из m и n.
Разложение чисел на простые множители
Ранее мы разбирали алгоритм разложения натурального числа на простые множители.
#37. Алгоритм Евклида для нахождения НОД | Python для начинающих
Как связаны простые множители числа и НОД. Приведем пример.
Пусть m = 18, n = 12
Выполним разложение на простые множители.
Множители числа m: 2 3 3
Множители числа n: 2 2 3
Выделим их общие простые множители — это числа 2 и 3. В качестве наибольшего общего делителя нужно взять из произведение: 2 * 3 = 6. НОД(12, 18) = 6.
Пусть m = 36, n = 48
Множители числа m: 2 2 3 3
Множители числа n: 2 2 2 2 3
Общие простые множители — это числа 2 2 3. Произведение этих множителей равно 12. НОД(36, 48) = 12.
Для нахождения НОД двух чисел нужно выполнить их разложение на простые множители и в качестве ответа взять произведение их общих множителей.
Как будем решать задачу
Для хранения множителей числа воспользуемся списком (PascalABC.NET), в него легко добавлять значение командой add.
Описание списка с именем nod в блоке var
Создание нового пустого списка в теле программы
Добавление значения в конец списка
Создадим два списка (s1 и s2) для хранения множителей числа m и n соответственно. С помощью конструкции вложенных циклов переберем все элементы списков и сравним на равенство, если множители равны, сохраним их в списке nod, а значения элементов списков сделаем равными -1 и -2 соответственно (чтобы далее их повторное сравнение на равенство было ложным) . В качестве ответа возьмем произведение элементов списка nod командой nod.Product.
Программа на языке программирования Паскаль (разложение чисел на простые множители)
m, n, k1, k2: integer;
writeln(‘Введите два натуральных числа m и n:’);
while (m > 1) or (n > 1) do
while m mod k1 = 0 do
s1.Add(k1); //добавить значение в список можно и так: s1+=k1;
while n mod k2 = 0 do
for k1:=0 to s1.Count-1 do //элементы списка нумеруются с 0, длина списка s1.count
for k2:=0 to s2.Count-1 do
if s1[k1]=s2[k2] then //s1[k1] — обращение к элементу списка по его номеру
Это программа состоит из самого большого количества строк. Насколько она эффективна?
Задача на применение НОД
Даны числа : a = 2 3 • 3 10 • 5 • 7 2 , b = 2 5 • 3 • 11 . Чему равен НОД (a,b)?
Источник: reshupascal.blogspot.com
Нахождение НОД и НОК двух чисел — Pascal(Паскаль)
Пусть a и b — целые числа, тогда верны следующие утверждения:
Все общие делители пары a и b являются также общими делителями пары a — b, b;
И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b; НОД(A, B) = НОД(A — B, B), если A > B; НОД(A, 0) = A.
Если t — произвольный общий делитель a и b, то он делит и разность a — b. Действительно, из a = t * u и b = t * v следует, что a — b = t * u — t * v = t * (u — v). То есть t — также общий делитель а — b и b. Обратно, если t — произвольный делитель общий делитель a — b и b, то он делит и их сумму a — b + b = a. Это можно доказать аналогично предыдущему.
Поэтому t — также общий делитель a и b. Делаем вывод, что множество общих делителей a и b совпадает с множеством делителей a — b и b. В частности, совпадают и наибольшие общие делители этих пар. Наибольшее целое, на которое делится число a, есть само число а. Число 0 делится на любое число. Отсюда наибольший общий делитель а и 0 равен а. Доказанная формула(3) позволяет свести вычисление наибольшего делителя одной пары к вычислению наибольшего общего делителя другой пары, в которой числа уже меньше. Очевидная же формула (4) дает нам понять, когда надо остановиться.
var a, b: integer; begin write(‘a = ‘); readln(a); write(‘b = ‘); readln(b); while a <> b do if a > b then a := a — b else b := b — a; writeln(‘NOD = ‘, a); end.
Вариант 5 Алгоритм Евклида с делением
Пусть a и b — целые числа, а r — остаток от деления a на b. Тогда НОД(a, b) = НОД(b, r). Эта формула также позволяет свести вычисление наибольшего общего делителя одной пары чисел к вычислению наибольшего обшего делителя другой пары чисел.
var a, b: integer; begin write(‘a = ‘); readln(a); write(‘b = ‘); readln(b); while (a <> 0) and (b <> 0) do if a >= b then a := a mod b else b := b mod a; write(a + b) end.
Program test2(input,output); Const N = 5; Var С: array[1..5] of integer; A,B:integer; function HOК (A, В:integer):integer; begin HOK:=A*B/ HOD(A,B); end; function НОD(А, В:integer):integer; var X,Y:integer; begin X:= A; Y: = В; 1:IF X = Y THEN HOD:=X; IF X > Y THEN begin X:= X – Y;goto 1; end; IF Y > X THEN begin Y:= Y – X;goto 1; end; end; Begin FOR i= 1 ТО N READ (C[i]); A:= С ([l]) FOR i = 1 TO N–1 begin B:=С[i + 1]; A:= HOK(A,B); end; writeln («HOK=»; A); end.
Program N_O_D (Input, Output); Var A, B: LongInt; NOD : LongInt; Begin WriteLn (‘PASCAL: Нахождение Н.О.Д. двух заданных чисел.’); Writeln (‘Введите числа, для которых ищется НОД:’); Write(‘Первое число: ‘);ReadLn (A); Write(‘Второе число: ‘);ReadLn (B); If (A < B)ThenNOD := A Else NOD := B; While Not( (A mod NOD = 0) and (B mod NOD = 0) ) do NOD := NOD — 1; WriteLn (‘НОД = ‘,NOD); ReadLn; End.
Program N_O_D (Input, Output); Var A, B: LongInt; NOK, NOD : LongInt; Begin WriteLn (‘PASCAL: Нахождение Н.О.К. двух заданных чисел.’); WriteLn (‘Введите числа, для которых ищется НОК:’); Write (‘Первое число: ‘);ReadLn (A); Write (‘Второе число: ‘);ReadLn (B); If (A < B)ThenNOD := A Else NOD := B; While Not ( (A Mod NOD = 0) And (B Mod NOD = 0) ) Do NOD := NOD — 1; A := A Div NOD; B := B Div NOD; NOK := A * B * NOD; WriteLn (‘НОК = ‘, NOK); ReadLn; End.
Похожие записи/страницы:
- Дана последовательность из n неотрицательных целых чисел. На каждом шагу эти числа упорядочивают по возрастанию и каждые…
- Разработать рекурсивный алгоритм и программу решения задачи, в которой вычислить : f(n)=(n+2)!/(n+4)!. Исходные данные…
- Числом Смита называется число,у которого сумма своих цифр равна сумме цифр всех простых делителей с учетом их кратностей…
- Написать калькулятор геометрических фигур — Pascal(Паскаль)
- Составить программу для перевода натуральных чисел из системы счисления с основанием 2 в десятеричную систему счисления…
- Дана последовательность К чисел. определить, сколько чисел этой последовательности содержит в своей записи все цифры…
- Задана последовательность чисел N1,N2,N3,N4. Составить программу вычисления количества (K) положительных чисел,…
- В 1202г. Итальянский математик Леонард Пизанский (Фибоначчи) предложил такую задачу: пара кроликов каждый месяц дает…
Источник: retrolib.ru
Упражнение JavaScript | Наибольший общий делитель двух положительных целых чисел
Напишите программу на JavaScript для вычисления наибольшего общего делителя (НОД) двух положительных целых чисел.
Выполнить код » Скрыть результаты
Есть другой способ решить эту задачу? Разместите свой код (и комментарии) через Disqus.
Комментарии
пожелания к комментариям…
- Приветствуются комментарии, соответствующие теме урока: вопросы, ответы, предложения.
- Одну строчку кода оборачивайте в тег , несколько строчек кода — в теги . ваш код. .
- Допускаются ссылки на онлайн-песочницы (codepen, plnkr, JSBin и др.).
Источник: www.wm-school.ru