Записи теоретических кусков

Арифметика

Проверка на простоту

Рассмотрим множество натуральных чисел (с нулём) $\{0,\,1,\,2,\,3,\,\ldots\}$. В дальйнейшем под числами будем понимать именно натуральные числа (с нулём). Говорят, что число $n$ делится на число $d$, если найдётся такое число $k$, что $n = kd$. Число $n \ge 2$ называется простым, если оно делится только на само себя и на $1$. В противном случае число $n \ge 2$ называется составным.

Рассмотрим следующую задачу. На вход программе подаётся число $n \ge 2$. Требуется вывести prime, если оно является простым, и composite, если оно является составным.

Эту задачу можно решать, действую «по определению». Это означает, что мы явно проверим, на сколько чисел от $1$ до $n$ делится число $n$. Если делителей окажется ровно $2$, то перед нами простое число, а иначе — составное.

Приведём соответствующий код.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var
  n, num_divisors, i: integer;

begin
  read(n);
  num_divisors := 0; // количество делителей
  
  for i := 1 to n do 
    if n mod i = 0 then
      num_divisors := num_divisors + 1;
  
  if num_divisors = 2 then
    writeln('prime')
  else
    writeln('composite');
end.

Нетрудно понять, что наш алгоритм совершает порядка $n$ действий. Как говорят программисты, наш алгоритм работает за $O(n)$.

Оказывается, что можно существенно уменьшить количество действий, необходимых для проверки числа на простоту.

Теорема. Если число $n$ является составным, то у него имеется делитель $d$ такой, что $2 \le d \le \sqrt{n}$.

Доказательство. Предположим, что утверждение теоремы неверно. Это значит, что есть такое составное число $n$, все делители которого не лежат среди чисел $2,\,3,\,\ldots,\,\sqrt{n}$. Поскольку число $n$ составное, то найдутся такие $a$ и $b$, что $n = ab$. По предположению, $a \gt \sqrt{n}$ и $b \gt \sqrt{n}$, откуда $ab \gt \sqrt{n} \cdot \sqrt{n}$, т. е. $ab \gt n$. Мы пришли к противоречию.

Доказанная нами теорема позволяет вести цикл в строке 8 нашего алгоритма от 2 до $\sqrt{n}$. Таким образом, время работы нашего оптимизированного алгоритма составит $O(\sqrt{n})$, что позволит быстро проверять на простоту числа порядка $10^{16}$. Напомним, что для хранения таких чисел в Паскале следует использовать тип int64, а в C++ — long long.

Алгоритм Евклида

Определение. Число $d$ называется наибольшим общим делителем двух чисел $a$ и $b$, если $d$ делит $a$ и $b$, причём является наибольшим из подобных чисел. Обычно пишут $d = $ НОД$(a, b)$.

Пример:

Квадратичные сортировки

Постановка задачи

Например, пусть у нас имеется массив из $n$ чисел. Напомним, что объявление и считывание массива на паскале выглядит как-то так:

1
2
3
4
5
6
7
8
9

var
  a: array [1..1000] of integer; 
  // массив из не более чем 1000 целых чисел
  n, i: integer;

begin
  read(n); // считываем количество чисел
  for i := 1 to n do 
    read(a[i]); // считываем элементы массива

Итак, пусть нам ввели какие-нибудь числа. Скажем, 4 -5 9 2 7 1 6. При этом a[1] = 4, a[2] = -5 и т. д.

Наша задача: переупорядочить числа таким образом, чтобы они шли по возрастанию, если читать их слева направо. Иными словами, нам нужно написать код, после которого числа массива a будут лежать в такой последовательности: -5 1 2 4 6 7 9.

Сортировка выбором

Проиллюстрируем сказанное выше кодом.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

var
  a: array [1..1000] of integer; 
  n, i, min_element: integer;

begin
  // предположим, что массив a уже считан
  min_element := a[1];
  for i := 2 to n do 
    if min_element > a[i] then 
      min_element := a[i];
  writeln('Minimum in array: ', min_element);

Используя сакральное знание о том, как искать минимум, мы можем предложить следующий алгоритм сортировки:

• находим минимальное значение в массиве;
• производим обмен этого значения со значением на первой неотсортированной позиции;
• теперь сортируем таким же образом весь массив, исключив из рассмотрения уже отсортированные элементы.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var
  a: array [1..1000] of integer;
  i, j, index_of_min_element, n: integer;
  temp: integer; // временная переменная для обмена значениями

begin
  read(n);
  for i := 1 to n do
    read(a[i]);
  
  for i := 1 to n - 1 do begin 
    // необходимо n - 1 раз выбрать минимум среди элементов 
    // a[i], a[i + 1], ..., a[n] и обменять его с элементом a[i] местами
    index_of_min_element := i;
    for j := i + 1 to n do
      if a[index_of_min_element] > a[j] then
        index_of_min_element := j;
    temp := a[index_of_min_element];
    a[index_of_min_element] := a[i];
    a[i] := temp;
  end;

  for i := 1 to n do
    write(a[i], ' ');
  writeln;
end.

Сортировка пузырьком

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var
  a: array [1..1000] of integer;
  i, j, n: integer;
  temp: integer; // временная переменная для обмена значениями

begin
  read(n);
  for i := 1 to n do
    read(a[i]);
  
  for i := 1 to n - 1 do begin 
    for j := 1 to n - 1 do 
      if a[j] > a[j + 1] then begin
        temp := a[j];
        a[j] := a[j + 1];
        a[j + 1] := temp;
      end;
  end;

  for i := 1 to n do
    write(a[i], ' ');
  writeln;
end.

Приведём венгерский народный танец «сортировка пузырьком», который иллюстрирует рассматриваемый нами алгоритм.

Время работы

Сортировка подсчётом

Сортировка подсчётом

Как мы выяснили, сортировка пузырьком умеет сортировать массив за $O(n^2)$. Сейчас мы научимся сортировать массивы специально вида гораздо быстрее.

Итак, предположим, что у нас имеется массив целых чисел из некоторого диапазона $[MINVALUE,\,MAXVALUE]$. Пусть также диапазон не слишком велик. Например, пусть $MAXVALUE - MINVALUE \le 10^7$. В этом случае мы можем подсчитать, сколько раз каждое значение из диапазона встречается в массиве. Затем мы можем по этой информации выписать исходный массив в отсортированном порядке.

Приведём код, который сортирует массив. Отметим, что такие параметры алгоритма, как MINVALUE и MAXVALUE, лучше выносить в секцию констант. В программировании принято имена констант записывать большими буквами.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

const 
  MINVALUE = 0;
  MAXVALUE = 1000 * 1000;
  MAXN     = 1000 * 1000;

var
  n, i, j, k: longint;
  a: array [1..MAXN] of longint;
  count: array [MINVALUE..MAXVALUE] of longint;

begin
  read(n);

  for i := 1 to n do 
    read(a[i]);

  // обнуляем массив count
  for j := MINVALUE to MAXVALUE do
    count[j] := 0;

  for i := 1 to n do 
    count[a[i]] := count[a[i]] + 1;

  i := 1; // позиция ячейки в массиве чисел, 
          // которая будет заполняться следующей
  for j := MINVALUE to MAXVALUE do
    for k := 1 to count[j] do begin
      a[i] := j;
      i := i + 1;
    end;

  for i := 1 to n do
    write(a[i], ' ');
end.

Оценим время работы этой программы. Обозначим размер диапазона за $m$, т. е. $m := MAXVALUE - MINVALUE + 1$. Цикл в строчках 18-19 выполняется за $O(m)$. Цикл в строчках 21-22 выполняется за $O(n)$. В строках 26-30 суммарно совершается $n + m$ операций. Итого время работы сортировки подсчётом составляет $O(n + m)$, где $n$ — размер массива, а $m$ — размер диапазона чисел. Серьёзное улучшение по сравнению с алгоритмом сортировки пузырьком!