РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ И ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ (теория)

§1. Понятие задачи и подзадачи 1

§2. Сведение задачи к подзадачам 2

§3. Понятие рекуррентного соотношения 3

§4. Правильные рекуррентные соотношения 5

§5. Способ организации таблиц 6

5.1. Организация одномерных таблиц 7

5.2. Организация двумерных таблиц 8

§6. Способ вычисления элементов таблицы 9

6.1. Вычисление элементов одномерной таблицы 9

6.2. Вычисление элементов двумерной таблицы 10

6.3. Вычисление элементов двумерной таблицы с дополнительными ограничениями 12

§7. Программы на Паскале 14

1. Понятие задачи и подзадачи

При формулировке любой задачи необходимо определить исходные данные, которые мы будем называть параметрами задачи.

Например, если мы решаем задачу нахождения корней квадратного уравнения ax ² + bx + c = 0, то эта задача определяется тремя параметрами – коэффициентами a, b и c.

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

При этом нас пока не интересует конкретный алгоритм решения задачи. Мы хотим научиться решать задачу, сводя ее к решению подзадач. Здесь удобно думать об алгоритме как о некотором устройстве или некоторой функции, которые преобразуют входные параметры в некоторые выходные данные, являющиеся решением задачи.

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

• количество параметров;

• значения параметров.

Здесь и далее в качестве параметров будут рассматриваться целые неотрицательные числа.

Как правило, одним из аргументов задачи является количество параметров задачи. В том случае, когда по значению этого параметра можно определить конкретные значения других параметров, мы эти параметры будем опускать. Это обычно делается в случае, когда параметры заданы таблицей. Например, если нам необходимо найти сумму первых K элементов таблицы, то для решения задачи достаточно знать один параметр K, а все остальные параметры можно выбрать из таблицы.

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

 Пример 1. Найти самую тяжелую монету из 10 монет. Для формализации задачи определим функцию "Самая тяжелая монета", аргументами которой являются количество монет (10) и масса каждой из монет. Пока нас не интересует конкретный вид этой функции, для нас важнейшим фактором является факт, что она дает правильное решение.

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

• "Самая тяжелая монета" из 1 монеты,

• "Самая тяжелая монета" из 2 первых монет,

• "Самая тяжелая монета" из 3 первых монет,

• ...

• "Самая тяжелая монета" из 9 первых монет.

Таким образом, у нашей функции "Самая тяжелая монета", аргументом является количество имеющихся монет, по которому можно определить конкретный вес каждой

монеты. Следовательно, рассмотренные подзадачи имеют меньшее количество аргументов, чем исходная задача.

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

1. Сведение задачи к подзадачам

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

При этом для решения исходной задачи может потребоваться решение одной или нескольких подзадач.

 Пример 2. Задачу, сформулированную в примере 1, можно свести к различным наборам подзадач, например:

• найти самую тяжелую из 9 монет, а затем найти самую тяжелую из 2 монет (найденной из 9 и оставшейся), или

• найти самую тяжелую из 5 монет, затем самую тяжелую из других 5 монет, а затем самую тяжелую из 2 монет, найденных на преды­дущих шагах.

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

В приведенном примере исходная задача сводится к подзадачам с меньшим числом параметров, в данном случае – с меньшим количеством монет.

Используя этот же принцип можно решить задачу нахождения НОД двух чисел.

 Пример 3. Найти наибольший общий делитель (НОД) двух натуральных чисел N и M.

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

Рассмотрим случай, когда числа не равны. Известно, что

НОД(N, M) = НОД(N, M + N) = НОД(N + M, M).

Кроме того, при N M НОД(N, M) = НОД(N – M, M), а при M N НОД(N, M) = НОД(N, M – N).

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

Таким образом, решение задачи нахождения НОД(N, M) при различных значениях N и M сводится к двум подзадачам:

• НОД(N – M, M), если N M;

• НОД(N, M – N), если M N.

1. Понятие рекуррентного соотношения

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

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

Пример 4. Рассмотрим задачу нахождения суммы N элементов таблицы A.

Пусть функция S(N) соответствует решению нашей исходной задачи. Эта функция имеет один аргумент N – количество суммируемых элементов таблицы A. Понятно, что для поиска суммы N элементов достаточно знать сумму первых N – 1 элементов и значение N-го элемента. Поэтому решение исходной задачи можно записать в виде соотношения

S(N) = S(N – 1) + a_N.

Следует отметить, что это соотношение справедливо для любого количества элементов N 1. Это соотношение можно переписать в виде

S(i) = S(i – 1) + a_i при i 1.

Однако пока это соотношение не определено при N = 1. К приведенному выше соотношению необходимо добавить соотношение S(1) = a₁.

Заметим, что на практике применяются имеющие тот же смысл соотношения

S(i) = S(i – 1) + a_i при i  1,

S(0) = 0.

Последовательное применение первого соотношения при i = 1, 2, ..., N и используется при вычислении суммы N элементов.

S[0]: = 0

нц для i от 1 до N (4. 1)

 S[i]: = S[i – 1] + a[i]

кц

В S[i] хранится значение функции S(I).

Здесь и далее в круглых скобках будут записываться аргументы функции, а в квадратных – индексы элементов массива. При этом имя функции и имя массива, в котором хранится значение этой функции, могут совпадать.

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

Пример 5 . Вычислить сумму S = 1 + 1/x + 1/x² + ... + 1/x^N при x, не равном 0.

Как и в предыдущем примере можно записать следующее соотношение:

S(i) = S(i – 1) + a(i), i  1, где

a(i) = 1/x ⁱ,

S(0) = 1.

Конечно, можно и эти соотношения использовать для написания программы. При этом у нас возникла новая задача – найти способ вычисления a(i). Для этого можно воспользоваться тем же приемом – попытаться вычислить a(i) через значение a(i – 1). Соотношение между значениями a(i) и a(i – 1) имеет следующий вид:

a(i) = a(i – 1)/x, i  1

a(0) = 1

Поэтому поставленную задачу можно решить следующим образом.

S[0]: = 1

a[0]: = 1

нц для i от 1 до N (4. 2)

 a[i]: = a[i – 1]/x

 S[i]: = S[i – 1] + a[i]

кц

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

Соотношения, связывающие одни и те же функции, но с различными аргументами, называются рекуррентными соотношениями или рекуррентными уравнениями.

1. Правильные рекуррентные соотношения

 Правильными рекуррентными соотношениями ( уравнениями ) будем называть такие рекуррентные соотношения, у которых количество или значения аргументов у функций в правой части соотношения меньше количества или, соответственно, значений аргументов функции в левой части соотношения. Если аргументов несколько, то достаточно уменьшения одного из аргументов.

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

В приведенных примерах соотношения связывали функции только с двумя различными параметрами: S(i) и S(i – 1), а также a(i) и a(i – 1) для любого натурального i. При этом были определены начальные значения S(0) и a(0).

Отметим, что без этих начальных значений рекуррентное соотношение

S(i) = S(i – 1) + a_i, i  1,

было бы неправильным, так как оно не определено при i = 1.

Конечно, могут быть и более сложные соотношения, связывающие более двух функций.

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

F(0) = 1,

F(1) = 1,

F(i) = F(i – 1) + F(i – 2) для натурального i 1.

В этом случае для вычисления значения F(N), которое хранится в F[N], можно воспользоваться следующим алгоритмов.

F[0]: = 1

F[1]: = 1

нц для i от 2 до N (4. 3)

 F[i]: = F[i – 1] + F[i – 2]

кц

При этом в приведенном фрагменте уже нельзя просто опустить индексы, хотя в принципе можно вычислить значение F(N) без использования таблицы, но это уже вопрос способа реализации алгоритма.

Пример такой реализации приводится ниже.

a: = 1

b: = 1

нц для i от 2 до N (4. 4)

 c: = b + a

 a: = b

 b: = c

кц

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

1. Способ организации таблиц

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

Как уже говорилось раньше, подзадача может быть формализована в виде функции, которая зависит от одного или нескольких аргументов. Если мы возьмем таблицу, у которой количество элементов равно количеству всех возможных различных наборов аргументов функции, то каждому набору аргументов может быть поставлен в соответствие элемент таблицы. Вычислив элементы таблицы (решения подзадач), можно найти и решение исходной задачи.

1. Организация одномерных таблиц

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

 Пример 7 . Рассмотрим задачу нахождения произведения 10 элементов таблицы A.

Пусть функция P(10) соответствует решению нашей исходной задачи. В данном случае у функции только один параметр – количество элементов. Для поиска произведения 10 элементов достаточно знать произведение первых 9 элементов и значение 10-го элемента. Поэтому решение исходной задачи можно записать в виде соотношения

P(10) = P(9)*a₁₀.

Следовательно, это соотношение может быть определено

для любого i, 2  i  10:

P(i) = P(i – 1)*a_i

P(1) = a₁.

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

P(i) = P(i – 1)* a_i при i  1,

P(0) = 1.

Приведем алгоритм.

P[0]: = 1

нц для i от 1 до N (4. 5)

 P[i]: = P[i – 1]*a[i]

кц

Так как у нашей функции один аргумент – количество сомножителей, то для решения задачи достаточно использовать одномерную таблицу. При этом количество элементов таблицы определяется количеством различных значений аргумента. В приведенном примере размерность массива равна 10. Если бы мы решали задачу поиска произведения 20 элементов, то для реализации рекуррентного соотношения нам было бы достаточно одномерной таблицы с 20 элементами.

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

1. Организация двумерных таблиц

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

 Пример 8. Для данной прямоугольной таблицы A размера 5x6 построить прямоугольную таблицу B того же размера, элементы которой обладают следующим свойством: элемент B[i, j] равен максимальному из элементов таблицы B, которые расположены левее и выше позиции (i, j), включая также позицию (i, j). При этом считается, что позиция (1, 1) – верхняя левая позиция прямоугольной таблицы (при i = 3 и j = 4 интересующая нас часть показана на Рис. 1).

Рис. 1

Пусть T(i, j), обозначает функцию, вычисляющую элемент B[i, j].

Определим сначала значения элементов таблицы B, расположенных в первой строке и в первом столбце. Получим:

T(1, 1) = A[1, 1],

T(1, j) = max{T(1, j – 1), A[1, j]} при j  2,

T(i, 1) = max{T(i – 1, 1), A[i, 1]} при i  2.

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

При 2  i  5 и 2  j  6 для этой функции можно записать следующее рекуррентное соотношение:

T(i, j) = max{T(i – 1, j), T(i, j – 1), A[i, j]}.

Действительно, величина T(i – 1, j) соответствует максимальной величине элементов таблицы A в той ее части, которая определяется значением индексов i – 1 и j, а величина T(i, j – 1) – максимальной величине элементов таблицы A, определяемой индексами i и j – 1. Поэтому эти величины учитывают значение всех элементов матрицы A в той ее части, которая определяется значением индексов i и j за исключением одного элемента A[i, j].

Для реализации этих рекуррентных соотношений достаточно двумерной (прямоугольной) таблицы, так как у функции T два аргумента. Важно отметить, что при этом мы можем отождествить величины T(i, j) и B[i, j]. Тогда фрагмент алгоритма можно записать следующим образом:

В[1, 1]: = A[1, 1]

нц для j от 2 до 6

 В[1, j] = max(В[1, j – 1], A[1, j])

кц

нц для i от 2 до 5 (4. 6)

 В[i, 1] = max(В[i – 1, 1], A[i, 1])

кц

нц для i от 2 до 5

 нц для j от 2 до 6

  B[i, j] = max(B[i, j – 1], B[i – 1, j])

  B[i, j] = max(B[i, j], A[i, j])

 кц

кц

1. Способ вычисления элементов таблицы

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

1. Вычисление элементов одномерной таблицы

Для одномерной таблицы таким способом обычно является последовательное вычисление элементов, начиная с первого.

 Пример 9. Определить, сколькими различными способами можно подняться на 10-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну.

Пусть K(10) – задача поиска количества способов подъема на 10 ступеньку. Определим i-ю подзадачу нашей задачи как задачу поиска количества способов подъема на i-ю ступеньку.

Исходя из условия задачи, на 10 ступеньку можно подняться непосредственно с 8-й и 9-й ступенек. Поэтому, если мы знаем количество способов подъема K(8) и K(9) на 8 и 9 ступеньки, то количество способов подъема на 10 ступеньку может быть определено как K(10) = K(8) + K(9).

Такое соотношение получается потому, что любой способ подъема на 8-ю ступеньку превращается в способ подъема на 10-ю ступеньку добавлением перешагивания через 9-ю ступеньку, а любой способ подъема на 9-ю ступеньку превращается в способ подъема на 10-ю ступеньку добавлением подъема с 9 на 10-ю ступеньку. Все эти способы различны. Аналогичное соотношение справедливо для любой ступеньки i, начиная с третьей, K(i) = K(i – 2) + K(i – 1).

Осталось определить значения K(1) и K(2), которые равны: K(1) = 1, K(2) = 2.

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

K[1]: = 1

K[2]: = 2

нц для i от 2 до 10 (4. 7)

 K[i]: = K[i – 1] + K[i – 2]

кц

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

1. Вычисление элементов двумерной таблицы

 Пример 10 . В таблице c N строками и M столбцами, состоящей из 0 и 1, необходимо найти квадратный блок максимального размера, состоящий из одних единиц. Под блоком понимается множество элементов соседних (подряд идущих) строк и столбцов таблицы. Интересующая нас часть показана на рис. 2.

рис. 2

Положение любого квадратного блока может быть определено его размером и положением одного из его углов.

Пусть T(i, j) есть функция, значение которой соответствует размеру максимального квадратного блока, состоящего из одних единиц, правый нижний угол которого расположен в позиции (i, j). Функция T(i, j) вычисляет элемент таблицы B[i, j]. Для примера на рис. 2 значения T(i, j) будут иметь вид

Таким образом, наша задача свелась к вычислению максимального значения функции Т при всевозможных значениях параметров i и j. Этой функции может быть поставлена в соответствие таблица размера N*M.

Определим сначала значения элементов таблицы В, расположенных в первой строке и в первом столбце. Получим:

В(1, 1) = А[1, 1],

В(1, j) = А[1, j] при j  2,

В(i, 1) = A[i, 1] при i  2.

Эти соотношения следуют из того факта, что в этих случаях рассматриваемая область матрицы А содержит только один элемент матрицы.

При 2  i  N и 2  j  M для этой функции можно записать следующие рекуррентные соотношения:

B[i, j] = 0, если A[i, j] = 0 и

B[i, j] = min{B[i – 1, j], B[i, j – 1], B[i – 1, j – 1]} + 1, если A[i, j] = 1

Первое соотношение показывает, что размер максимального единичного блока с правым нижним углом в позиции (i, j) равен нулю в случае A[i, j] = 0.

Убедимся в правильности второго соотношения. Действительно, величина B[i – 1, j] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i – 1, j). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i – 1, j] + 1, так как к блоку в позиции (i – 1, j) могла добавиться только одна строка. Величина B[i, j – 1] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i, j – 1). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i, j – 1] + 1, так как к блоку в позиции (i – 1, j) мог добавиться только один

 столбец. Величина B[i – 1, j – 1] соответствует максимальному размеру единичного блока таблицы A с правым нижним углом в позиции (i – 1, j – 1). Тогда размер единичного блока с правым нижним углом в позиции (i, j) не превышает величину B[i – 1, j – 1] + 1, так как к блоку в позиции (i – 1, j – 1) могли добавиться только одна строка и один столбец. Итак, размер единичного блока с правым нижним углом в позиции (i, j) равен min{B[i – 1, j], B[i, j – 1], B[i – 1, j – 1]} + 1.

В[1, 1]: = A[1, 1]

нц для j от 2 до 6

 В[1, j]: = A[1, j]

кц

нц для i от 2 до 5

 В[i, 1]: = A[i, 1]

кц (4. 8)

нц для i от 2 до 5

 нц для j от 2 до 6

  если A[i, j]: = 1

   то

   B[i, j]: = min(B[i, j – 1], B[i – 1, j])

   B[i, j]: = min(B[i, j], B[i – 1, j – 1]) + 1

  иначе

   B[i, j]: = 0

  все

 кц

кц

1. Вычисление элементов двумерной таблицы с дополнительными ограничениями

 Пример 11 . На складе имеется 5 неделимых предметов. Для каждого предмета известна его стоимость (в рублях) и масса (в кг). Величины стоимости и массы являются натуральными числами. Ваша цель состоит в том, чтобы определить максимальную суммарную стоимость предметов, которые вы можете унести со склада при условии, что суммарная масса предметов не должна превышать 16 кг.

Пусть элемент C_i таблицы C соответствует стоимости i-го предмета, а элемент M_i таблицы M – массе i-го предмета. Будем считать, что предметы пронумерованы в порядке их следования в таблицах.

Пусть T обозначает функцию, значение которой соответствует решению нашей задачи. Аргументами у этой функции является количество предметов (по этому аргументу можно определить их стоимости и массы соответствующих предметов), а также максимальная суммарная масса, которую можно унести.

Для нашей задачи T(5, 16) определим подзадачи T(i, j), где i обозначает количество начальных предметов, из которых можно осуществлять выбор, а j определяет максимально возможную суммарную массу уносимых предметов. Отметим, что определенный таким образом первый параметр i определяет как количество предметов для подзадачи, так и значения их стоимостей и масс, определяемых из таблиц C и M.

Определим сначала начальные значения функции T. При нулевых значениях одного из аргументов значение функции равно нулю:

T(0, 0) = 0

T(0, j) = 0 при j  1,

T(i, 0) = 0 при i  1.

Определим возможные значения функции T(i, j) при ненулевых значениях аргументов.

Решение подзадачи, соответствующей функции T(i, j) может быть сведено к двум возможностям: уносится ли при наилучшем решении предмет с номером i или нет.

Если предмет не уносится, то решение задачи с i предметами сводится к решению подзадачи с i – 1 предметами, т. е.

T(i, j) = T(i – 1, j).

Если предмет c номером i уносится, то это уменьшает максимально возможную суммарную массу для i – 1 первых предметов на величину M[i], одновременно при этом увеличивая значение решения для оставшихся предметов T(i – 1, j – M[i]) на величину C[i], т. е.

T(i, j) = T(i – 1, j – M[i]) + C[i].

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

Теперь для получения наилучшего решения нам необходимо выбрать лучшую из этих двух возможностей. Поэтому рекуррентное соотношение при i  1 и j  1 имеет вид

T(i, j) = T(i – 1, j) при j M[i] и

T(i, j) = max(T(i – 1, j), T(i – 1, j – M[i]) + C[i]) при j  M[i].

Пусть заданы следующие значения стоимости и массы для 5 предметов:

C[1] = 5, M[1] = 4; C[2] = 7, M[2] = 5;

C[3] = 4, M[3] = 3; C[4] = 9, M[4] = 7;

C[5] = 8, M[5] = 6.

Таблица значений функции T, которую мы также назовем T, выглядит следующим образом:

Следовательно, решение задачи T(5, 16) = 21, т. е. можно унести предметов на 21 рубль.

T[0, 0]: = 0

нц для j от 1 до 16

 T[0, j] = 0

кц

нц для i от 1 до 5 (4. 9)

 T[i, 0] = 0

кц

нц для i от 1 до 5

 нц для j от 1 до 16

  если j = M[i]

   то

   T[i, j] = max(T[i – 1, j], T[i – 1, j – M[i]] + C[i])

   иначе

   T[i, j] = T[i – 1, j]

  все

 кц

кц

1. Программы на Паскале

S[0]:=0;

for i:=1 to N do (4. 1)

S[i]:=S[i-1]+a[i];

———————————————————————————————

S[0]:=1;

a[0]:=1;

for i от 1 to N do (4. 2)

begin

a[i]:=a[i-1]/x;

S[i]:=S[i-1]+a[i];

end;

———————————————————————————————

F[0]:=1;

F[1]:=1;

for i:=2 to N do (4. 3)

F[i]:=F[i-1]+F[i-2];

———————————————————————————————

a:=1;

b:=1;

for i:=2 to N do (4. 4)

begin

c:=b+a;

a:=b;

b:=c;

end;

———————————————————————————————

P[0]:=1;

for i:=1 to N do (4. 5)

P[i]:=P[i-1]*a[i];

———————————————————————————————

B[1,1]:=A[1,1];

for j:=2 to 6 do

B[1,j]:=max(В[1,j-1], A[1,j]);

for i:=2 to 5 do (4. 6)

B[i,1]:=max(В[i-1,1], A[i,1]);

for i:=2 to 5 do

for j:=2 to 6 do

begin

B[i,j]:=max(B[i,j-1],B[i-1,j]);

B[i,j]:=max(B[i,j],A[i,j]);

end;

———————————————————————————————

K[1]:=1;

K[2]:=2;

for i:=2 to 10 do (4. 7)

K[i]:=K[i-1]+K[i-2];

———————————————————————————————

В[1,1]:=a[1,1];

for j:=2 to 6 do

В[1,j]:=A[1,j];

for i:=2 to 5 do (4. 8)

В[i,1]:=A[i,1];

for i:=2 to 5 do

for j:=2 to 6 do

if A[i,j]:=1 then

begin

B[i,j]:=min(B[i,j-1],B[i-1,j]);

B[i,j]:=min(B[i,j],B[i-1,j-1])+1;

end

else

B[i,j]:=0;

———————————————————————————————

T[0,0]:=0;

for j:=1 to 16 do

T[0,j]:=0;

for i:=1 to 5 do (4. 9)

T[i,0]=0;

for i:=1 to 5 do

for j:=1 to 16 do

if j=M[i] then

T[i,j]:=max(T[i-1,j],T[i-1,j-M[i]]+C[i])

else

T[i,j]:=T[i-1,j];