Вариант 1
var a,b:longint; function NOD(x,y:longint):longint; { функция поиска наиб. общ. делителя } begin if x<>0 then NOD:=NOD(y mod x,x) else NOD:=y; end; function NOK(x,y:longint):longint; { функция поиска наим. общ. кратного } begin NOK:=( x div NOD(x,y) ) * y; end; begin { основная программа } readln(a,b); writeln( 'НОД этих чисел = ', NOD(a,b) ); writeln( 'НОК этих чисел = ', NOK(a,b) ); end.
Вариант 2 Переборный алгоритм
var a, b, d: integer; begin write('Введите два числа: '); readln(a, b); if a < b then d := a + 1 else d := b + 1; {так как мы используем цикл с постусловием, необходимо минимальное значение увеличить на один, иначе цикл repeat, в силу своих конструктивных особенностей, не учтет это минимальное число и не сделает его кандидатом в НОД. Например, 5 и 25.} repeat d := d - 1 until (a mod d = 0) and (b mod d = 0); write('NOD = ', d) end.
Вариант 3
var m,n,r:integer; label lb; begin write('Введите первое число:');readln(m); write('Введите второе число:');readln(n); lb:r:=m mod n; if r=0 then writeln('НОД = ',n) else begin m:=n; n:=r; goto lb; end; end.
Вариант 4 Алгоритм Евклида с вычитанием
Пусть 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.
Вариант № 6
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.
Вариант 7
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.
Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу
Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: А*В = НОД(А, В)*НОК(А, В).
Program zad_3_nica;
var A, B, C: real;
begin
write (‘Введите A: ‘);
read (A);
write (‘Введите B: ‘);
read (B);
C:=A*B;
while (A<>B)
do begin
if A>B
then A:=A-B
else B:=B-A
end;
C:=C/A;
writeln (‘НОК(A,B)=’, C)
end.
var
x, y, p: Integer;
begin
Writeln(‘Введите два числа’);
Readln(x, y); {вводим два целых числа}
p := x * y;
repeat
if x > y Then x := x Mod y
Else y := y Mod x
until (x = 0) Or (y = 0);
{до тех пор, пока одно из чисел не станет равно нулю}
Writeln(‘НОK=’, p / (x + y)); {вывод НОД — без условного оператора, так как одно из чисел обязательно равно нулю}
end.
Ответ оставил Гость
Uses crt;
var n,m,p : real;
nod,nok : real;
begin
clrscr;
write(n=);readln(a);
write(j=);readln(b);
p:=n*m;
while n<>m do
if n>m then n:=n-m
else m:=m-a;
nod:=n;
nok:=p/nod;
writeln(НОД:,n);
write(НОК:,nok);
readln;
end.
Оцени ответ
Здесь приведен код программы на языке Паскаль. Программа вычисляет НОД и НОК с использованием алгоритма Евклида. Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Приведем пример: для чисел 70 и 105 наибольший общий делитель будет равен 35. НОД существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n. Например, для 3 и 5, НОК равен 15, а для 2 и 4 НОК равен 4.
program nodnok;
var a,b:longint;
function NOD(x,y:longint):longint;
begin
if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y;
end;
function NOK(x,y:longint):longint;
begin
NOK:= (x div NOD(x,y)) * y;
end;
Begin
Write('Введите a и b: ');
Readln(a,b);
Writeln('НОД ',a,' и ',b,' = ', NOD(a,b));
Writeln('НОК ',a,' и ',b,' = ', NOK(a,b));
Readln;
End.
Похожие публикации: Pascal