Математика , Работа с числами

[Romtek]

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

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

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

или

if Number and 1 = 0
   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. Ограничения: только для A > 0

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

Факториал ( дополнительная информация: Факториал числа - N! )

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; , то будут генерироваться одни и те же числа.

Сообщение отредактировано: volvo877 - 30.04.08, 05:45

[Romtek]

Как проверить простое ли число?

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;

[tserega]

Более быстрое разложение числа на множители.
В методе, описанном romtek-ом, количество проверок пропорционально 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 : Comp;
Begin
 X:=2 * Trunc(Sqrt(N)) + 1;
 Y:=1;
 R:=Sqr(Trunc(Sqrt(N))) - 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.

PS: источник - D.E. Knuth, The Art of Computer Programming, Vol.2

Сообщение отредактировано: Romtek - 15.02.05, 12:07

[Romtek]

Как узнать из каких цифр состоит целое число?

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

[e-moe]

Как быстро делить/умножать числа на степень двойки?

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

 
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...)!
Если производить эти операции со знаковыми типами, то бит знака тоже сдвигается и в рез-те
число может поменять свой знак!

Сообщения были разделены в тему "Численные методы"

Сообщение отредактировано: e-moe - 02.07.04, 19:14