Наибольший общий делитель. Наименьшее общее кратное
1. Заданы два натуральных числа a и b. Найти НОД(a,b).
Пример ввода: 168 1386
Пример вывода: 42
Решим эту задачу двумя способами:
- используя Алгоритм Евклида;
- через разложение на простые множители.
1 способ
Используем Алгоритм Евклида.
readln(a,b);
while a<>b do
if a>b then a:=a-b else b:=b-a;
nod:=a;
writeln('nod=',nod);
Если числа a и b отличаются сильно, например a=8, b=100, то действуя по алгоритму от числа b двенадцать раз будет отниматься число a. В итоге получаем a=8, b=4. Однако, это то же самое, что и нахождение остатка от деления числа b на число a.
Исходя из этих предположений, строим модернизированный Алгоритм Евклида по остаткам.
readln(a,b);
while (a>0) and (b>0) do
if a>b then a:=a mod b else b:=b mod a;
nod:=a+b;
writeln('nod=',nod);
2 способ
Делим оба числа на одно и то же d ( d вначале равно 2). Если оба числа делятся на d, то nod:=nod*d. Если оба числа не делятся на d, то d увеличиваем на 1. Если только одно какое либо число a или b делится на d, то его уменьшаем в d раз.
readln(a,b);
nod:=1; d:=2;
while (a>1) or (b>1) do
begin
if (a mod d=0) and (b mod d=0) then nod:=nod*d;
if (a mod d<>0) and (b mod d<>0)
then d:=d+1
else begin
if a mod d=0 then a:=a div d;
if b mod d=0 then b:=b div d;
end;
end;
writeln('НОД = ',nod);
Нахождение НОД через алгоритм Евклида предпочтительней, поскольку этот алгоритм короче и работает быстрее алгоритма разложения на простые множители.
Поэтому, во всех последующих задачах будем для нахождения НОД использовать алгоритм Евклида.
2. Заданы два натуральных числа a и b. Найти НОК(a,b).
Пример ввода: 28 42
Пример вывода: 84
Находим НОД(a,b). А затем используем формулу НОК(a,b) · НОД(a,b) = a · b
readln(a,b);
pa:=a; pb:=b;
while (a>0) and (b>0) do
if a>b then a:=a mod b else b:=b mod a;
nod:=a+b;
nok:=(pa div nod)*pb;
writeln('НОК( ',pa,' , ',pb,' ) = ',nok);
3. Заданы два числа a и b. Сократима ли дробь a/b. Если сократима, то найти такие c и d, чтобы a/b=c/d.
Пример ввода: 21 30
Пример вывода: Сократима 21 / 30 = 7 / 10
Для решения задачи проделаем следующие действия:
- находим наибольший общий делитель чисел a и b;
- если НОД>1, то дробь сократима, причём её необходимо сократить на НОД.
readln(a,b);
a1:=a; b1:=b;
while (a>0) and (b>0) do
if a>b then a:=a mod b else b:=b mod a;
nod:=a + b;
if nod=1 then writeln(‘дробь не сократима’)
else begin
c:=a1 div nod;
d:=b1 div nod;
writeln(‘сократима’,’ ‘,a1,’/’,b1,’=’,c,’/’,d);
end;
4. Имеются две ёмкости объёмом V1 и V2. Можно ли путём переливаний жидкости этими ёмкостями получить объем V3 (V1, V2, V3 – натуральные числа).
Пример ввода: V1=7 V2=13 V3=5
Пример вывода: да
Для решения задачи проделаем следующие действия:
- находим наибольший общий делитель чисел V1 и V2 (минимальная ёмкость жидкости, которую можно получить путём переливаний равна НОД(V1,V2);
- проверяем, если число V3 кратно НОД, то ответ: «можно получить», иначе «нельзя».
readln(v1,v2,v3);
while (v1>0) and (v2>0) do
if v1>v2 then v1:=v1 mod v2 else v2:=v2 mod v1;
nod:=v1 + v2;
if v3 mod nod=0 then writeln(‘можно’) else writeln(‘нельзя’);
5. В первой четверти координатной плоскости во всех точках с целочисленными координатами вбиты гвозди. Заданы координаты X, Y некоторого гвоздя. Будет ли он виден из точки с координатами (0,0). Если нет, то гвоздь с какими координатами его закрывает.
Пример ввода:
3 2
2 2
Пример вывода:
будет виден
не виден. Закрывает гвоздь (1 , 1)
Для решения задачи необходимо проверить имеются ли треугольники подобные треугольнику с катетами x и y и меньшие его:
- находим наибольший общий делитель чисел X и Y;
- если НОД(x,y)>1, существуют гвозди, которые закрывают гвоздь с координатами (x, y).
readln(x,y);
xs:=x;ys:=y;
while (x>0) and (y>0) do
if x>y then x:=x mod y else y:=y mod x;
nod:=x + y;
xz:=xs mod nod; yz:=ys mod nod;
if nod=1 then writeln(‘Будет виден’)
else writeln(‘Не виден.Закрывает гвоздь с координатами (’,xz,’, ’,yz,’ )’ );
Задачи для самостоятельного решения
1. Заданы три натуральных числа a, b, c . Найти НОД(a,b,c).
2. Заданы три натуральных числа a, b, c . Найти НОК(a,b,c).
3. Задано число n. Заданы n натуральных чисел a1, a2, a3, ……, an. Найти НОД(a1,a2,a3,……,an).
4. Задано число n. Заданы n натуральных чисел a1, a2, a3, ……, an. Найти НОК(a1,a2,a3,……,an).
5. Выразить в виде несократимой дроби произведение дробей a/b и c/d (a, b, c, d – заданные натуральные числа).
6. Выразить в виде несократимой дроби сумму (разность) дробей a/b и c/d (a, b, c, d – заданные натуральные числа).
7. Заданы два натуральных числа с и d. Найти a и b, для которых с=НОД(a,b) и d=НОК(a,b). Вывести все варианты пар a и b.
8. Для приготовления эликсира бессмертия необходимо его варить ровно t минут. Имеются песочные часы на t1 и t2 минут. Можно ли используя эти часы отмерить t минут.
9. Паук ползет по диагонали прямоугольника ABCD на клетчатом листе бумаги, размером M*N. Составить алгоритм и написать программу, которая определяет: через сколько единичных квадратиков проползет паук, пока доберется из точки A в точку C, считая что: N, M, - натуральные числа, стороны единичных квадратиков параллельны сторонам прямоугольника.