На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила ЧаВо (FAQ) разделов Паскаля
В этом разделе разрешено создавать только темы, в которых описано РЕШЕНИЕ какой-либо общей проблемы, или описание какого-либо аспекта языка Паскаль.
Обсуждение уже созданных тем разрешено, но только конструктивное, например указание на ошибку или уточнение имеющегося текста.

Также читать Требования к оформлению статей
Модераторы: Romtek, volvo877
  
    > Математика , Работа с числами
      - Математика и числа -


      Чётность/нечётность чисел
      ExpandedWrap disabled
        if Odd (Number) then
          writeln (Number, ' нечётно')
        else
          writeln (Number, ' чётно')
      или
      ExpandedWrap disabled
        if Number and 1 = 0
           then writeln(Number,' чётно')
           else writeln(Number,' нечётно')

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

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


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


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


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


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

      Если не написать сначала Randomize; , то будут генерироваться одни и те же числа.
      Сообщение отредактировано: volvo877 -
        Как проверить простое ли число?
        ExpandedWrap disabled
          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;


        Разложение числа на множители
        ExpandedWrap disabled
          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;


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


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

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

              ExpandedWrap disabled
                 
                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 -
              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
              0 пользователей:


              Рейтинг@Mail.ru
              [ Script execution time: 0,1546 ]   [ 16 queries used ]   [ Generated: 9.12.24, 15:55 GMT ]