Как найти наименьшее общее кратное на паскале

При программировании на любом языке необходимо знать основные алгоритмы. Они являются как бы «азбукой» для программиста. Сегодня я хочу рассказать про основные алгоритмы в таком языке программирования, как Паскаль.

1. Первый алгоритм, про который я расскажу — это факториал натурального числа Pascal. Факториалом числа (!n) является произведение натуральных чисел от 1 до этого числа включительно. Например, 5!=1*2*3*4*5.

Наша задача — написать программу Pascal, которая находит факториал числа.

Сначала переменной f (сокр. Factorial) присваиваем значение, равное единице, т.к 0! = 1, 1!=1.
Далее идет цикл с параметром от 2 до заданного числа, в котором переменная f умножается на следующее значение после единицы с увеличением на 1 после каждого круга.

Программа нахождения факториала на языке Паскаль:

Скачать: nok.pas

3. Также нужно знать и про НОД двух чисел. НОД — наименьший общий делитель, т. е. Минимальное число, которое нацело делит два и более чисел.

Код нахождения НОД в паскаль:

Содержание

if Odd (Number) then 
  writeln (Number, ' нечётно')
else
  writeln (Number, ' чётно');

if Number mod 3 = 0 then
  writeln (Number, ' делится на 3 без остатка');

Делиться без остатка – означает кратность.

(НОД, англ. Greatest Common Divisor)

{ Евклид (Euclidus) }
function GCD (A: integer;  B: integer): integer;
begin
    while (a <> 0) and (b <> 0) do
       if a >= b then
         a := a mod b
       else 
         b := b mod a;
    GCD := a + b; { один - ноль }
end;

(НОК, англ. Least Common Multiplier)

function LCM (A: integer;  B: integer): integer; 
begin
     LCM := a * b div GCD (a, b)
end;

Для целых чисел

function Power(Base, N: integer): longint;
{ Base - основание , N - степень }
var
   Result: longint;
   i: word;
begin
   Result := 1; { придаём начальное значение }
   for i := 1 to N do
     Result := Result * Base;
 
   Power := Result;
end;

Для вещественных чисел

Возвести A в степень N. Ограничения: [COLOR=red]только для A > 0[/COLOR]

function PowerExp (A, N: real): real;
begin
   if A > 0 then
     PowerExp := Exp ( N * Ln (A) )
   else 
     PowerExp := 0;
end;

function Factorial(N: word): longint;
var
   Result: longint;
   i: word;
begin
   Result := 1;
   for i := 1 to N do 
     Result := Result * N;
 
   Power := Result;
end;

С использованием рекурсии

function Factorial (N: word): longint;
begin
   if N = 0 then
     Factorial := 1 
   else 
     Factorial := N * Factorial (N - 1);
end;

Round – Округляет значение вещественного типа до значения целого типа, округляя.
Trunc – Округляет значение вещественного типа до значения целого типа, отбрасывая дробную часть.
Frac – Возвращает дробную часть аргумента.
Int – Возвращает целую часть аргумента.

   var
       r : real;
     begin
       r := Round ( 123.456);  {    123 }
       r := Round ( 123.778);  {    124 }
       r := Trunc ( 123.456);  {    123 }
       r := Trunc (-123.778);  {   -123 }
       r := Frac  ( 123.456);  {  0.456 }
       r := Int   ( 123.456);  {  123.0 }
       r := Int   (-123.456);  { -123.0 }
     end.

Процедура Randomize – инициализирует генератор чисел.
Функция Random (N) выдает целочисленные значения в диапазоне от 0 до N-1 !
Например, чтобы сгенерировать число X в диапазоне -N..N , пишем так:

  Randomize;
  X := Random (N + 1) - 2 * N;

Если не написать сначала Randomize; , то будут генерироваться одни и те же числа.

function isPrime(X: word): boolean;
var
i: integer;
Begin
     isPrime:=false;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
 
     isPrime:=true;
End;

procedure Factorization(x: word);
var i: word;
 
 procedure DivX; { делим на простое число, пока делится без остатка }
 begin
      while (x>1) and (x mod i = 0) do
      begin
           write(i:4);
           x:= x div i;
      end;
 end;
 
begin
     i:=2;
     DivX;
     i:=3;
     while (i < x div 2) do
     begin
           DivX;
           inc(i,2); { <=> i:=i+2; только нечётные числа }
     end;
     if x>1 then writeln(x:4);
end;

VAR p,q,qmax:integer;
    d, r, min: real;
BEGIN
   write('r, qmax=');
   readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) }
   p:=0; q:=1; min:=r;
   REPEAT
     IF p / q < r
          THEN inc(p)
          ELSE inc(q);
     d:=abs(r-p/q);
     IF d < min THEN
     BEGIN
          min:=d;
          writeln(p:7,'/',q)
     END
   UNTIL (q >= qmax) OR (d = 0);
   readln;
END.

FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит }
BEGIN 
     isBitOn:=((n SHR b) AND 1) = 1
END;
 
PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит }
BEGIN
     N:= N OR (1 SHL b)
END;
 
PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит }
BEGIN
     N:= N XOR (1 SHL b)
END;

Var X : Integer;
Begin
 X:=12345;
 Writeln('Число состоит из таких цифр:');
 While X <> 0 Do
  Begin
   Writeln(X Mod 10);
   X:=X Div 10;
  End;
End.

Как известно, опрерации умножения и деления занимаю много машинного времени. Если требуется скорость, то целесообразно использовать логические сдвиги:

i:=i shl 1; { i:=i * 2^1}
i:=i shl 2; { i:=i * 2^2}
{и т.д.}
i:=i shr 1; { i:=i div 2^1}
i:=i shr 2; { i:=i div 2^2}
{и т.д.}

Примечание: корректно работает только с целыми беззнаковыми типами (word, byte…)!
Если производить эти операции со знаковыми типами, то бит знака тоже сдвигается и в результате
число может поменять свой знак!

В методе, описанном ранее, количество проверок пропорционально sqrt(N), т.е. для разложение числа порядка 10¹² потребуется около 10⁶ операций, причем используется деление!
Существуют методы поиска делителей, которые справляются со своей задачей намного быстрее (без операций деления).
В методе Ферма предполагается, что N – нечетное число, причем N = uv. Попробуем подобрать такие числа X и Y, что будет выполняться:
N = p² – q². Обозначим u = (p + q) / 2 и v = (p – q) / 2.
Будем пытаться приблизить числа p и q с разных сторон, чтобы выполнялось N = p² – q².
Итак, сам алгоритм:

• Присвоим x = 2 * trunc(sqrt(N)) + 1, y = 1, r = sqr(trunc(sqrt(N))) – N (во время выполнения алгоритма числа x, y и r будут соответствовать 2p + 1, 2q + 1 и p² – q² – N)

• Если r = 0, то выполнение алгоритма заканчивается. Имеем N = ((x-y)/2)((x+y-2)/2) и (x-y)/2 – наибольши делитель числа N.

• Присвоить r = r + x, x = x + 2 (шаг по x)

• Присовить r = r – y, y = y – 2 (шаг по y). Делать этот шаг, пока r > 0.

• Перейти к проверке r = 0

Так как все действия алгоритма – это сложения и вычитания, то они на компьютере выполняются очень быстро. В результате работы алгоритма будет получено одно число – наибольший делитель числа N. Замечание: данный алгоритм лучше использовать для поиска больших делителей, нежели для маленьких!

{$N+, E+}
 
function FermaFactorization (N : Comp) : Comp;
 
var
  X, Y, R, Z, ZZ : Comp;
 
begin
 Z := Sqrt(N);
 ZZ := Trunc (Z);
 X := 2 * ZZ + 1;
 Y := 1;
 R := Sqr (ZZ) - N;
 while (R <> 0) do
  begin
   R := R + X;
   X := X + 2;
   repeat
    R := R - Y;
    Y := Y + 2;
   until R <= 0;
  end;
 FermaFactorization := (X - Y) / 2;
end;
 
begin
 Writeln (FermaFactorization(917979909) : 0 : 0);
end.