Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > Pascal: Математика > Математика


Автор: romtek 05.04.04, 23:02
- Математика и числа -


Чётность/нечётность чисел
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    if Odd (Number) then
      writeln (Number, ' нечётно')
    else
      writeln (Number, ' чётно')
или
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    if Number and 1 = 0
       then writeln(Number,' чётно')
       else writeln(Number,' нечётно')

Делимость (кратность) чисел
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    if Number mod 3 = 0 then
      writeln (Number, ' делится на 3 без остатка');
Делиться без остатка - означает кратность.

Наибольший Общий Делитель (НОД, англ. Greatest Common Divisor)
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    { Евклид (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)
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    function LCM (A: integer;  B: integer): integer;
    begin
         LCM := a * b div GCD (a, b)
    end;


Степень
Для целых чисел
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    function PowerExp (A, N: real): real;
    begin
       if A > 0 then
         PowerExp := Exp ( N * Ln (A) )
       else
         PowerExp := 0;
    end;


Факториал ( дополнительная информация: Факториал числа - N! )
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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;


С использованием рекурсии
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    function Factorial (N: word): longint;
    begin
       if N = 0 then
         Factorial := 1
       else
         Factorial := N * Factorial (N - 1);
    end;


Вещественный и целый типы
Round - Округляет значение вещественного типа до значения целого типа, округляя.
Trunc - Округляет значение вещественного типа до значения целого типа, отбрасывая дробную часть.
Frac - Возвращает дробную часть аргумента.
Int - Возвращает целую часть аргумента.
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
       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 , пишем так:
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
      Randomize;
      X := Random (N + 1) - 2 * N;

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

Автор: romtek 05.04.04, 23:11
Как проверить простое ли число?
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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;


Разложение числа на множители
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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;


Приближённое представление числа в виде дроби
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
     
    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.


Как работать с отдельными битами?
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    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 06.04.04, 08:15
Более быстрое разложение числа на множители.
В методе, описанном romtek-ом, количество проверок пропорционально 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. Замечание: данный алгоритм лучше использовать для поиска больших делителей, нежели для маленьких!
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    {$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 11.06.04, 09:37
Как узнать из каких цифр состоит целое число?
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    Var X : Integer;
    Begin
     X:=12345;
     Writeln('Число состоит из таких цифр:');
     While X <> 0 Do
      Begin
       Writeln(X Mod 10);
       X:=X Div 10;
      End;
    End.

Автор: e-moe 02.07.04, 19:05
Как быстро делить/умножать числа на степень двойки?

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

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

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

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)