Приведем 3 программы поиска наибольшего общего делителя двух натуральных чисел, основанных на:
- алгоритме Евклида
- перебора возможных делителей числа
- разложения чисел на простые множители
Что такое наибольший общий делитель двух натуральных чисел m и n, или НОД(m, n)
НОД двух натуральных чисел - это такое наибольшее натуральное число, которое одновременно делит без остатка оба этих числа.
Алгоритм Евклида
Евклид - древнегреческий математик, геометр, автор первого из дошедших до нас теоретических трактатов по математике.
Алгоритм Евклида - один из наиболее ранних численных алгоритмов в истории. Евклид впервые дал описание этого алгоритма в книгах «Начала». Изначально этот алгоритм назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль.
Сформулируем алгоритм
Пусть даны два натуральных числа m и n. Пока числа m и n не равны (или их разница не равна 0), большее число заменить их разницей. В качестве ответа взять любое из чисел.
Пример:
Пусть m = 12, n = 18
12<>18, n = 18 - 12 = 6
12<>6, m = 12 - 6 = 6
6<>6, НОД(12, 18) = 6
Программа на языке программирования Паскаль (алгоритм Евклида)
var m, n:integer;
begin
writeln('Введите два натуральных числа m и n:');
readln(m,n);
while m<>n do
begin
if m>n then m:=m-n
else n:=n-m;
end;
writeln('НОД(m,n): ',m);
end.
Результат запуска программы
Перебор возможных делителей числа
Будем использовать алгоритм, разобранный ранее в этом блоге.
Запустим цикл 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;
begin
writeln('Введите два натуральных числа m и n:');
readln(m,n);
for k:=1 to min(m,n) do
begin
if (m mod k = 0) and (n mod k=0) then p:=k;
end;
writeln('НОД(m,n): ',p);
end.
Функция min будет работать в PascalABC.NET, в случае использования другой среды, нужно до цикла определить наибольшее число из m и n.
Разложение чисел на простые множители
Ранее мы разбирали алгоритм разложения натурального числа на простые множители.
Как связаны простые множители числа и НОД. Приведем пример.
Пусть 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
var nod:List<integer>;
Создание нового пустого списка в теле программы
nod:=new List<integer>;
Добавление значения в конец списка
nod.add(значение);
Создадим два списка (s1 и s2) для хранения множителей числа m и n соответственно. С помощью конструкции вложенных циклов переберем все элементы списков и сравним на равенство, если множители равны, сохраним их в списке nod, а значения элементов списков сделаем равными -1 и -2 соответственно (чтобы далее их повторное сравнение на равенство было ложным) . В качестве ответа возьмем произведение элементов списка nod командой nod.Product.
Программа на языке программирования Паскаль (разложение чисел на простые множители)
var
m, n, k1, k2: integer;
s1, s2, nod: List<integer>;
begin
writeln('Введите два натуральных числа m и n:');
readln(m, n);
s1 := new List<integer>;
s2 := new List<integer>;
nod := new List<integer>;
k1 := 2; k2 := 2;
while (m > 1) or (n > 1) do
begin
while m mod k1 = 0 do
begin
m := m div k1;
s1.Add(k1); //добавить значение в список можно и так: s1+=k1;
end;
k1 += 1;
while n mod k2 = 0 do
begin
n := n div k2;
s2.Add(k2);
end;
k2 += 1;
end;
//writeln(s1, s2);
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] - обращение к элементу списка по его номеру
begin
nod.Add(s1[k1]);
s1[k1]:=-1;
s2[k2]:=-2;
end;
//println(s1,s2,nod);
println('НОД(m,n): ',nod.Product);
end.
Это программа состоит из самого большого количества строк. Насколько она эффективна?
Задача на применение НОД
Даны числа: a = 23 • 310 • 5 • 72 , b = 25 • 3 • 11. Чему равен НОД (a,b)?
Комментариев нет:
Отправить комментарий