Детальный анализ алгоритмов

На примере задачи "Продвинутый счет" с Турнира юных программистов 2016

Введение

Программировать - значит понимать. (Кристин Нюгард)

Попытаюсь показать на простейшем примере, как можно анализировать алгоритмы и писать программы. Сразу оговорюсь, что конкретно в этой задаче "Продвинутый счет" основательный анализ не нужен - алгоритм довольно простой и легко реализуется, и возможные ошибки в программе легко отловить при тестировании.

Но вообще алгоритмы очень полезно анализировать. Типичное поведение участников олимпиады - прочитал условие задачи, что-то придумал и сразу сел за компьютер писать код.

Если алгоритм, который вы хотите реализовать, простой и понятный - тогда вперед. А если нет? Тогда вы рискуете сами запутаться в своем коде, вам придется перебирать разные варианты, потом пытаться сломать программу на каких-то тестах, но все равно вы не будете уверены, что написали программу правильно. Потому что вы ее плохо понимаете.

Трудности могут возникнуть в алгоритмах с циклами типа while. Вероятно, вы сталкивались с такой ситуацией: вроде бы алгоритм придуман, а как написать условие цикла: i >= 1 или i > 1? Примеры - алгоритм QuickSort, двоичный поиск¹.

Вот для таких случаев и нужен детальный анализ. Если вы полагаете, что код можно написать как попало, а потом посмотреть, что программа выдает на тестах, и исправить ошибки, то вы сильно ошибаетесь. Даже на олимпиадах бывают задачи, в которых вы не сможете узнать правильный ответ к вашим тестам. Например, задачи на геометрию, оптимизацию. Допустим, на олимпиаде вы отправите решение в тестирующую систему, и она его проверит. Но на практике такой системы нет, поэтому вы должны сами написать тесты. А если узнать правильный ответ нельзя? Тогда программу вообще не получится протестировать (кроме, может быть, простейших частных случаев). Иногда возможно протестировать отдельные части программы. Еще полезна пошаговая отладка.

Все равно, чем лучше ты понимаешь алгоритм, тем проще его реализовать на языке программирования.

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

Правильная постановка задачи даже важнее, чем её решение. (Альберт Эйнштейн)

Неформальная

Юный статистик записывает количество объектов $M$ в компактном виде. Сначала он рисует $M$ единиц нулевого уровня (т.е. обычные черточки). Затем он заменяет $a_0$ последовательных единиц 0-го уровня на одну единицу 1-го уровня. Точно так же вместо $a_1$ последовательных единиц 1-го уровня малец рисует одну единицу 2-го уровня. И так далее.

Например, если $a_0 = a_1 = ... = a_{N-1} = B$, то полученный код будет записью числа $M$ в системе счисления по основанию $B$. При этом цифр будет не более $N + 1$, и цифра в старшем разряде может быть сколь угодно большой.

Вычислите для заданного числа $M$ код $k_N\ k_{N-1}\ \ldots\ k_1\ k_0$, где $k_j$ - количество единиц $j$-го уровня.

Формальная

Формальность освобождает. (Популярная у инженеров поговорка)

Дано: натуральные числа $M$, $a_1, a_2, \ldots, a_{N-1}$ ($a_i \geq 2$).

Найти: целые числа $k_0, k_1, \ldots, k_N$ такие, что

$$0 \leq k_i < a_i,\;\; i = 0,1,\ldots, N-1,$$ $$(1)\;\;M = k_0 + a_0\biggl(k_1 + a_1\Bigl(k_2 + a_2\bigl(k_3 + \ldots + a_{N-2}(k_{N-1} + a_{N-1}k_N)\bigr)\Bigr)\biggr).$$ Например, если $N = 3$, $a_0 = a_1 = a_2 = 10$, то $$12345 = \underbrace{5}_{k_0} \;+\; 10 \Bigl(\; \underbrace{4}_{k_1} \; + \; 10 \bigl(\; \underbrace{3}_{k_2} \; + \; 10 \cdot \underbrace{12}_{k_3} \; \bigr)\; \Bigr).$$

Теоретический анализ

Нет ничего практичнее, чем хорошая теория. (Людвиг Больцман)

Исходя из формулы (1), мы можем выписать формулы для нахождения чисел $k_i$².

Положим $M_0 = M$. Нетрудно видеть, что $k_0 = M_0 \bmod a_0$. Обозначим $M_1 = [M_0/a_0]$. Другими словами, $k_0$~--- остаток от деления $M_0$ на $a_0$, а $M_1$~--- неполное частное³.

Тогда формула (1) преобразуется к виду $M_0 = k_0 + a_0M_1$, $$(2)\;\;\; M_1 = k_1 + a_1\Bigl(k_2 + a_2\bigl(k_3 + \ldots + a_{N-2}(k_{N-1} + a_{N-1}k_N)\bigr)\Bigr).$$ И тут мы замечаем, что выражения (1) и (2) абсолютно аналогичны. Рекурсия налицо.

Продолжая этот процесс по формулам $$k_i = M_i \bmod a_i, \quad M_{i+1} = [M_i/a_i],$$ приходим к выражению $$M_{N-1} = k_{N-1} + a_{N-1}k_N,$$ отсюда $$k_{N-1} = M_{N-1} \bmod a_{N-1},\quad k_N = [M_{N-1}/a_{N-1}] = M_N.$$ Теперь мы можем записать общую формулу: $$(3)\;\;\;M_0 = M,$$ $$(4)\;\;\;k_i = M_i \bmod a_i,\quad M_{i+1} = [M_i/a_i], \quad i = 0,1,\ldots,N-1,$$ $$(5)\;\;\;k_N = M_N.$$

Итерационный алгоритм

Формулы (3)--(5) легко преобразуются в псевдокод алгоритма:

Input: $M$, $a_0, a_1, \ldots, a_{N-1}$

Output: $k_0, k_1, \ldots, k_{N}$

$M_0 \leftarrow M$;

for $i \leftarrow 0,1,\ldots, N-1$ do

   $k_i \leftarrow M_i \bmod a_i$;

   $M_{i+1} \leftarrow [M_i / a_i]$;

endfor

$k_N \leftarrow M_N$;

В данном псевдокоде не используются переменные, которые бы изменяли свое значение несколько раз.

Заменим последовательность $M_i$ на одну переменную $M$, но тогда ввеем инвариант цикла.

Input: $M$, $a_0, a_1, \ldots, a_{N-1}$

Output: $k_0, k_1, \ldots, k_{N}$

for $i \leftarrow 0,1,\ldots, N-1$ do

  // $M = M_i$

   $k_i \leftarrow M \bmod a_i$;

   $M \leftarrow [M / a_i]$;

  // $M = M_{i+1}$

endfor

$k_N \leftarrow M$;

В комментариях указано утверждение, которое выполняется в данном месте алгоритма.

Поскольку условие в конце цикла такое же, как в начале, только вместо $i$ там $i+1$, то (по индукции) на следующей итерации цикла инвариант сохраняется.

Теперь, когда мы проанализировали алгоритм и записали псевдокод⁴, его нетрудно записать на любом языке программирования.

     //на входе: M, a[0...N-1]
     for i := 0 to N - 1 do
     begin
       k[i] := M mod a[i];
       M := M div a[i];
     end;
     k[N] := M;
     //вывести k[N], ..., k[0]

Рекурсивный алгоритм

Тот же алгоритм можно записать в рекурсивной форме. Вместо инварианта цикла~--- спецификация рекурсивной процедуры.

Процедура с входным параметром $i$ должна найти числа $k_i, k_{i+1}, \ldots, k_N$ такие, что $$0 \leq k_j < a_j,\;\; j = i,i+1,\ldots, N-1,$$ $$M = k_i + a_i\Bigl(k_{i+1} + a_{i+1}\bigl(k_{i+2} + \ldots + a_{N-2}(k_{N-1} + a_{N-1}k_N)\bigr)\Bigr).$$ Рекурсивный алгоритм сводит указанную задачу к такой же задаче, в которой $i$ на единицу больше.

Input: $M$, $a_0, a_1, \ldots, a_{N-1}$

Output: $k_0, k_1, \ldots, k_{N}$

function Rec($M$, $i$)

// Разложить число $M$ с коэффициентами $a_i, a_{i+1}, \ldots, a_{N-1}$

   if $i = N$

     $k_N \leftarrow M$

   else

     $k_i \leftarrow M \bmod a_i$

     Rec($[M/a_i],\, i+1$);

   endif

endfunction

Rec($M$, 0);

Программная реализация:

     procedure Rec(M, i: integer);
     begin
       if (i = N) then
         k[N] := M
       else
       begin
         k[i] := M mod a[i];
         Rec(M div a[i], i + 1);         
       end;         
     end;

     begin
       //на входе: M, a[0...N-1]     
       Rec(M, 0);
       //вывести k[N], ..., k[0]
     end.

Итог

Итак, мы рассмотрели методику анализа алгоритмов на простейшем примере. С одной стороны, на олимпиаде подробнейшим образом расписывать все эти формулы не нужно, тем более в такой простой задаче. С другой стороны, если вы в процессе учебы попробуете детально расписать решение одной-двух задач, то такой подход пригодится вам при построении более сложных алгоритмов, для которых тестирование может быть просто невозможным.

Выделим этапы решения задачи:

1. Внимательно прочитать условие и попытаться его формализовать.
2. Провести теоретический анализ задачи. Вывести математические формулы, позволяющие построить вычислительный алгоритм.
3. Сформулировать алгоритм на удобном для вас языке (псевдокод, блок-схема, словесное описание). Проанализировать отдельные блоки алгоритма. При необходимости записать инварианты циклов⁵ и убедиться, что они сохраняются от итерации к итерации.
4. Включить компьютер и спокойно написать программу.

Хочу напомнить, что программирование - это не только алгоритмы. Это также структуры и абстрактные типы данных, но самое главное - это структура ("архитектура") вашей программы, потому что на практике программы не ограничиваются парой сотней строк, как на олимпиадах. Следовательно, нужно продумывать, как будет устроена вся программная система в целом. И эту структуру тоже не мешало бы аккуратно записать на бумажке (ну или в специальном формате на компьютере), чтобы понять, что вы хотите получить в итоге. А иначе вы сядете писать код, напишете что попало и расстроитесь.

¹. Если в алгоритме только циклы for и условия, то все более-менее понятно - что написано, то и выполняется. ↩

². Не код, а сначала формулы! Потом мы переведем их в код. ↩

³. которое в народе называется div ↩

⁴. возможно, кому-то удобнее рисовать блок-схему ↩

⁵. Иногда бывает полезно записать в некоторых местах алгоритма те утверждения, которые должны выполняться в данном месте (например, x = 0). То есть как инвариант цикла, только в любом месте алгоритма. ↩