Нахождение НОД и НОК двух чисел — Pascal(Паскаль)

Вариант 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. 

Leave a Comment