Структуры данных и алгоритмы. Теория. Рекуррентные уравнения. Динамическое программирование.

January 11, 2007

Формулировка любой задачи сводится к тому, что выполняется отображение одного множества на другое. Множества исходных данных на множество результата. В динамическом программировании решение задачи идет путем ее разбиения на некоторое количество подзадач, поэтому подобная абстрактная модель будет для нас эффективна. После того как задача была формализована в виде функции с некоторым количеством параметров, наступает этап выделения подзадач. Подзадача – это та же задача что и первоначальная, но имеющая меньшее количество параметров, или один из этих параметров имеет меньшее значение (меньшее не в плане абсолютной величины, а в отношении простоты решения задачи). В качестве примера рассмотрим задачу нахождения самой тяжелой монеты из 10. на первом этапе формализации определим, что исходными данными являются количество монет и их вес. Для этой задачи подзадачи будут:
 *	Найти самую тяжелую из 9 монет;
 *	Найти самую тяжелую из 8 монет;
 *	…
 *	Найти самую тяжелую из 1 монет;
В данных подзадачах постоянно уменьшается количество монет – т.е. идет уменьшение количества параметров функции. Важным будет отметить, что не стоит называть подзадачей такие этапы ее работы как ввод данных или вывод.

Одним из основных способов решения задач является их сведение к такому набору подзадач решение которых давало бы решение и самой задачи. Разумеется, что разбиение задачи на подзадачи имеет множественные варианты. Например для приведенного выше примера с монетами. Первой подзадачей может быть: найти самую тяжелую из девяти монет, а затем найти самую тяжелую из двух – оставшейся и самой тяжелой из девяти.

ПРИМЕР: нахождение НОД для натуральных чисел N, M.

Когда числа N, M равны, то НОД равен любому из них, т.е. НОД(N, M) = N.

В случае если числа не равны, то общеизвестно НОД (N, M) = НОД (N+M, M) = НОД (N, M + N). Или что тоже самое, при N>M, НОД (N, M)= НОД (N-M, M), в обратном случае, когда M>N, НОД (N,M)= НОД(N, M – N). таким образом задача сводится к самой себе, но с меньшими значениями аргументов, т.е. более простой, И ТАК необходимо повторять многократно, до тех пор пока решение не станет тривиальным, т.е. N=M.

ПРИМЕР: Рассмотрим решение классической задачи нахождения суммы из N элементов массива. Предположим, S(N) – есть решение нашей задачи, данная функция получает в качестве параметра одно значение – количество элементов подлежащих суммированию. Очевидно, что для нахождения суммы N элементов, необходимо использовать ранее найденную сумму, N-1, и добавить к ней элемент A[N]. Таким образом, данную задачу можно переписать как:
 1)	S(i) = S(i-1) + A[i];
 2)	S(0) = 0.
В качестве упражнения необходимо определить являются ли приведенные ниже уравнения рекуррентными.

При построении рекуррентных соотношений необходимо обязательно следить за тем, чтобы количество или значения аргументов в правой части уравнения были меньше чем в левой. Если аргументов несколько, то достаточно уменьшения только одного из них. Также важно, чтобы соотношения были определены для всех допустимых значений аргументов. Такие рекуррентные соотношения считаются правильными.
 1) D(i) = D(i-1)/a;
 2) S(i) =S(i-1)+S(i+1), для I>=2, S(1) =1;
 3) P(i) = P(i-2)*I, i>=3, P(1)=1, P(2) = 2;
 4) S(i)=S(I div 2) + S(i+1), S(0)=1, i>=2;
 5) S(i) = S(i-1)+1/i,  S(0) = 0, i>=1;
 6) S(i)=S(i-1)+(-1)ixi/I, i>=1, S(0)=1;
 7) F(i)=F(I div 2) + 1, i>=2, F(1)=0;
ЗАДАНИЕ: определите, являются ли следующие рекуррентные соотношения правильными:
 1)	S(i) = S(i-1)+a[i]/2, I – натуральное;
 2)	S(i)= S(i-1)+(S(i-1))I, i>=2, S(1)=1;
 3)	P(i)=P(i-1)*I, i>=2, P(1)=1;
 4)	S(i)=S(I div 2)*a[i], i>=2, S(0)=1;
 5)	S(i)=S(i-1)+S(i-2)/I, i>=2, S(0)=0, S(1)=1;
При решении задач с помощью методов динамического программирования очень важным является вопрос представления данных, и результатов расчета на предыдущих стадиях. Наиболее эффективно использовать многомерный массив, размерность – должна быть равна количеству параметров функции, а размер по каждому из измерений должен быть равен количеству значений данного аргумента.

ПРИМЕР: Для заданной прямоугольной матрицы A, размером 5*6. Необходимо построить прямоугольную таблицу B, того же размера. Каждый элемент которой должен быть равен B[i][j] = max A[y][x], где y=[1..i] x=[1..j].

Для решения обозначим через T(i,j) – искомое значение B[i][j]. Очевидно что T(1,1)=A[1][1]. Также легко вычисляется набор значений для первой строки и первого столбца матрицы B.
 
 T(i,1) = max (T(i-1,1) , A[i][1]);
 T(1,j) = max (T(1, j-1) , A[1][j]);
 T(I,j) в случае i>=2, j>=2 вычисляется по рекуррентной формуле:
 T(i,j) = max (T(i, j-1) , T(i-1,j) ,  A[i][j]);

ЗАДАНИЯ:



1) Определите количество способов, которыми можно подняться на 10 ступеньку лестницы, если можно подниматься, переступая одна за одной, перепрыгивая через одну или через две ступеньки.

2) Таблица размером n*m, заполнена 0 или 1. Необходимо найти наибольший квадратный блок, который состоит только из единиц.

3) На складе есть N неделимых предметов, для каждого предмета известна его масса и стоимость, необходимо найти максимальную стоимость предметов, которые можно вынести со склада при условии, что их стоимость не превышает M килограммов. Вес товаров и их стоимость – являются натуральными.

4) Трамвайные билеты имеют шестизначные номера, считается, что билет – счастливый, если сумма первых трех цифр совпадает с суммой последних трех. Найдите количество всех счастливых билетов.

5) Фишка может перемещаться по полю длиной N только вперед. Размер каждого шага не должен превышать K. Найдите количество способов которыми фишка может пройти от поля под номером 1 к полю N.

6) Покупатель имеет купюры ценностью A1, …, AN рублей, а продавец – B1,…,BM. Необходимо найти максимальную стоимость товара P, которую покупатель не сможет купить из-за невозможности точно рассчитаться с продавцом, хотя денег на его покупку достаточно.

7) Дана таблица натуральных чисел A[1..N][1..M]. За каждый проход по клетке (I,J) засчитывается штраф A[i][j], необходимо с наименьшим штрафом:
 • Пройти из какой-нибудь клетки первого ряда в последний ряд, при этом можно переходить из текущей клетки 
 только в одну из трех соседних в нижнем ряду. 
 • Реализовать предыдущее задание, но необходимо пройти из клетки с координатами (1,1) в клетку (N,M).
8) Многоугольник с N-вершинами (N>=3) задан с помощью координат своих вершин в порядке обхода по контуру. Необходимо разбить его на треугольники с помощью (N-3) диагоналями, которые не пересекаются, кроме как на концах, таким образом чтобы:
 •	сумма из длин должна быть минимальной;
 •	максимальная из диагоналей должна иметь наименьшую длину.
9) Даны две строки символов X, Y, строка X состоит из N символов, а строка Y – из M символов. Обозначим через D(X,Y) – минимальное количество операций преобразования которые необходимы для перевода строки X в строку Y. В качестве операций преобразования можно использовать операцию удаления произвольного символа, вставки в любую позицию строки нового символа, замены одного символа на другой. Для заданных значений X,Y необходимо найти D(X,Y).

10) Известно, что при умножении матрицы размером N*M, и матрицы размером M*K, необходимо выполнить N*K*M операций, и в результате получится матрица размером N*K. Необходимо определить минимальное количество операций, которые потребуются для перемножения S матриц A1,…,AS, для которых задан их размер в виде вектора N(i), M(i), где I ? [1..S]. помните, что при перемножении матриц количество столбцов первой и количество строк второй матрицы должны совпадать. Предполагается что в исходной последовательности вектором N, M порядок соблюдается, т.е. не требуется выполнять перемены местами сомножителей.

11) В заданной числовой последовательности A[1..N] необходимо вычеркнуть минимальное количество элементов так чтобы оставшиеся числа образовывали строго возрастающую последовательность.

12) Из заданной последовательности чисел необходимо построить новую путем вычеркивания наименьшего количества элементов так чтобы оставшиеся удовлетворяли соотношению: каждый последующий нацело делится на предыдущий.

13) Даны две последовательности символов X, Y. можно ли получить из последовательности X строку Y путем вычеркивания некоторого количества символов.

14) В массиве A (n) найти наибольшую по длине возрастающую последовательность получающуюся путем удаления наименьшего количества “лишних” чисел.

15) Из элементов массива A(2N) сформировать два «почти ортогональных массива B(N) и C(N), скалярное произведение которых было бы наиболее близко к нулю.

16) Имеется N костей домино, необходимо выстроить правильную последовательность максимальной длины.