Часть 3: динамическое программирование.

Важнейшим свойством дерева является то, что оно состоит из непересекающихся поддеревьев. Но что будет, если это ограничение снять, поставив другое, более общее: не должен существовать путь из элемента в самого себя? Исправлять в таком случае придётся только функцию удаления элемента, остальные останутся вполне рабочими. Однако они станут выполнять лишнюю работу: ведь если в один элемент существует два пути, значит, рекурсивная функция минимум дважды зайдёт в каждый элемент и соответственно дважды пройдёт весь путь после него.

Это не единственная задача, в которой рекурсивная функция выполняет много лишней работы, а без рекурсии задача не решается. Для устранения этого недостатка рекурсии существует приём, называемый динамическим программированием.

Для примера рассмотрим простую задачу: вычисление n-ного числа Фибоначчи[38]. Простейшая рекурсивная функция для этого такова:

int fib(int n) {return ((n==1)||(n==2))?1:(fib(n-1)+fib(n-2)); }

Функция эта предельно проста, к тому же не использует даже умножение – только сложение! И тем не менее, расчёт 43его числа на компьютере среднего уровня при минимальном количестве других приложений занимает порядка 20 секунд. Такое время является совершенно неприемлемым. Поэтому функцию надо оптимизировать.

Рассматривая работу этой функции, мы видим, что в каждом её вызове отдельно считается fib(n-1), и отдельно fib(n-2). Это же справедливо и для самих вызовов fib(n-1) и fib(n-2). То есть, каждое число считается несколько раз, и чем больше номер вычисляемого элемента – тем больше для каждого числа ненужных вызовов. Возникает естественное решение: все посчитанные числа Фибоначчи сохранять, чтобы потом их вызывать:

unsigned long int fib(unsigned long int n, unsigned long int* values)

{

if((n==1)||(n==2)) {values[n]=1; return 1;}

if(values[n]) return values[n];

int temp=(fib(n-1, values)+fib(n-2, values));

values[n]=temp;

return temp;

}

Эта функция, прежде чем искать значение числа Фибоначчи, смотрит, нет ли его на соответствующем месте массива values. Для этого сам массив при создании заполняется нулями (значение, которое не может иметь число Фибоначчи):

values=(unsigned long int*)malloc(sizeof(unsigned long int)*(n+1));

for(i=0; i<100; ++i) values[i]=0;

val=fib(n, values);

Какой же выигрыш даёт применение динамического программирования? На компьютере среднего уровня 47ое[39] число Фибоначчи без применения этой технологии считается больше 30 секунд, а с применением – менее, чем за миллисекунду. Вычисления ускорены более чем в 30000 раз.

Такое ускорение требует выделения дополнительной памяти под массив: ради быстродействия мы повысили расход памяти. Эта закономерность – повышение быстродействия повышает требования к памяти – носит неофициальное, но всеобщее название: золотой закон программирования.

Разумеется, все эти выкладки с секундами – не более чем наглядная демонстрация. Существует наука – теория алгоритмов, которая для каждого конкретного алгоритма может определить класс быстродействия, сравнивать алгоритмы по скорости и требованиям к памяти. Но для упрощения и наглядности демонстрации подойдёт и такой способ сравнения: 30000 раз на 47 числе Фибоначчи.

[1] В отечественной номенклатуре в качестве десятичного разделителя принята запятая, а в зарубежной — точка. Язык Си, как и подавляющее большинство языков программирования, использует в качестве разделителя точку. Тем не менее, во всех математических работах, в том числе и переводных, используется запятая. Поэтому в значении «десятичный разделитель» термины «точка» и «запятая» могут чередоваться.

[2] Принятое в компьютерной номенклатуре название порядка числа.

[3] В принципе, указанные здесь размеры не обязательны, это лишь наиболее распространённые. Обязательным является лишь соотношение char ≤ short int ≤ int≤ long int.

[4] Что примерно равно 1,8∙10¹⁹.

[5] В программировании мусор – это термин, означающий абсолютно бессмысленные данные, не соответствующие логике программы. Мусор может получиться как в результате ошибок в программе (в частности, при преобразовании типов), так и в результате действий пользователя, вводящего заведомо абсурдные данные.

[7] Существуют также логический и циклический сдвиг, но в языке Си они не реализованы.

[8] Сдвиговые операции работают гораздо быстрее умножения и деления, а потому в случае деления и умножения на 2 рекомендуется использовать именно сдвиг.

[9] Существуют две формы записи инкремента и декремента: инфиксная, показанная здесь, и префиксная, когда сначала ставится знак операции, а затем переменная. Они отличаются приоритетом.

[10] Однако, если объявляются несколько указателей, следует писать не int* a, b; а int *a, *b;

[11] Приоритет 13 имеет тернарный условный оператор, о котором сказано в лекции 7.

[12] В отличие от C++

[13] Терминология противоположна математической. В математике говорят, например: синус принимает значения от -1 до 1. Но в программировании функция принимает те значения, которые ей передают. То есть, в случае синуса – все действительные числа. Раз функция что-то принимает, то должна и возвращать. Возвращает она результат своего выполнения. В случае синуса – от -1 до 1.

[14] Разумеется, это абстракция языка Си, ничего операционная система не вызывает. Однако и сам вызов функции – абстракция. А в рамках этой абстракции функцию main следует рассматривать именно как вызываемую операционной системой.

[15] Вообще, GCC позволяет делать это и без применения прототипов: наткнувшись на вызов неизвестной функции, он ищет её то телу программы. Но тут уже играет роль читаемость кода: не надо рыскать по всей программе, чтобы посмотреть, как вызывать ту или иную функцию.

[16] Не во всех языках и не во всех компиляторах. В некоторых все объявляемые переменные сразу инициализируются нулём.

[17] Последним практически всегда является символ перехода на новую строку (клавиша Enter), а потому игнорируется.

[18] Побочный эффект от этого: если вызвать функцию getchar() без считывания возвращаемого значения, то программа будет ожидать нажатия Enter для продолжения.

[19] Тут следует заметить, что чаще всего приходится встречаться именно с такой записью: #include <файл>. Однако в данном случае треугольные скобки имеют то же значение, что и в форме Бэкуса-Наура (БНФ): на место скобок должен быть подставлен какой-то набор символов, смысл которого разъяснён в скобках.

[20] Библиотеки подключаются через их заголовочные файлы, имеющие расширение.h. То есть, для подключения библиотеки <имя> нужно написать #include <<имя>.h>

[21] Нулевой указатель принято обозначать NULL. Строка #define NULL 0 есть во всех стандартных библиотеках.

[22] В языке Паскаль, например, так и сделано: нулевой элемент строки содержит её длину.

[23] Также существует название нуль-терминированная строка.

[24] Совершенно стандартный приём для функций, от которых требуется изменение нескольких значений, или работающих с массивами.

[25] Разумеется, для этого они должны иметь одинаковый тип.

[26] Тем не менее, он работает.

[27] Здесь фигурные скобки являются обязательными.

[28] Это совсем не оптимальная реализация, она нужна только для того, чтобы продемонстрировать особенности работы цикла do{}while()

[29] 2n+2k=2(n+k)

[30] Вообще, структура не обязательно должна иметь имя, но применение структур требуется нечасто.

[31] Лучше все, поскольку тогда можно создавать функции таких типов.

[32] Кстати, этого практически достаточно, чтобы удалить вокальную партию из аудиозаписи.

[33] Имя структуры oneway соответствует английскому термину one-way list.

[34] Хотя, возникновение задачи хранения списка из столь небольших элементов само по себе маловероятно.

[35] Название структуры bidirectional соответствует английскому термину bidirectional list.

[36] Формальное определение: дерево – связный неориентированный граф без циклов.

[37] Это привело бы к возможности удаления корня дерева, что абсурдно с точки зрения логики программы обработки дерева: она не может обрабатывать пустоту.

[38] На практике никто числа Фибоначчи рекурсивно вычислять не будет. Но рассмотрение реальных задач динамического программирования, таких как задача о золотой горе, поиск наибольшей общей подпоследовательности, вычисление расстояния Левенштейна и других требует едва ли не отдельного курса.

[39] Максимальное число Фибоначчи, которое помещается в unsigned long int.

Дата добавления: 2015-11-13