Математика и числа

Чётность/нечётность чисел

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), т.е. для разложение числа порядка 1012 потребуется около 106 операций, причем используется деление! Существуют методы поиска делителей, которые справляются со своей задачей намного быстрее (без операций деления). В методе Ферма предполагается, что N - нечетное число, причем N = uv. Попробуем подобрать такие числа X и Y, что будет выполняться: N = p2 - q2. Обозначим u = (p + q) / 2 и v = (p - q) / 2. Будем пытаться приблизить числа p и q с разных сторон, чтобы выполнялось N = p2 - q2. Итак, сам алгоритм:

  • Присвоим x = 2 * trunc(sqrt(N)) + 1, y = 1, r = sqr(trunc(sqrt(N))) - N (во время выполнения алгоритма числа x, y и r будут соответствовать 2p + 1, 2q + 1 и p2 - q2 - 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.
 
pascal/math.txt · Последние изменения: 2006/05/10 14:12 (внешнее изменение)
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki