Черепашка
Эта задача является классикой динамического программирования. Ни одно печатное или электронное пособие по решению задач не обходится без разбора “Черепашки”. Рассмотреть все возможные маршруты и просчитать их невозможно. Но можно свести задачу к аналогичной. Пусть нам известен “максимальный” путь для всех клеток, кроме правой нижней (функция F(X, Y)). Все нужные маршруты проходят через одну из клеток, смежных с этим углом (их всего две). Максимальный же маршрут проходит через ту клетку из двух, для которой значение функции F больше. Остается только правильно выполнить отсечение:
Function F(x,y:integer):longint;
begin
if B[x, y] = –1 then
if F(x-1, y) > F(x, y - 1)
then B[x, y] := F(x - 1, y) + A[x, y]
else B[x, y] := F(x, y - 1) + A[x, y];
F := B[x, y]
end;
Теперь необходимо подумать о граничных условиях. Логически правильнее было бы просчитать нашу функцию для левой и верхней границы. Это делается легко, так как для этих клеток существует только один маршрут (непосредственно вдоль границы). Но еще проще ввести в рассмотрение фиктивные нулевые строку и столбец и присвоить им нулевые значения. Действительно, эти клетки, в принципе, недостижимы, поэтому максимальная сумма равна нулю.
Итеративное заполнение массива также довольно просто. После введения граничных условий (любых из рассмотренных выше) дальнейшее заполнение осуществляется двойным циклом:
for i:=1 to N do
for j:=1 to N do
if B[i - 1, j] > B[i, j - 1]
then B[i, j] := B[i - 1, j] + A[i, j]
else B[i, j] := B[i, j - 1] + A[i, j];
к занятию № 2
Конец формы
|
|
Взрывоопасность При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более двух контейнеров типа A. Для заданного количества контейнеров N определить число безопасных стопок. Формат входных данных Одно число 0 < N < 31. Формат выходных данных Одно число — количество безопасных вариантов формирования стопки.
[посмотреть подсказку]
Взрывоопасность
Если в предыдущей задаче нам удалось использовать рекурсивное решение, то здесь придется обходиться итеративным. Как обычно, будем искать число опасных стопок для произвольного N. Сложность в том, что стопки сами по себе разные. Разобьем их на 4 класса:
Тип 1 - опасные, содержат три или более контейнера A подряд. Тип 2 - не опасны, но наверху лежат два контейнера А. Тип 3 - не опасны, но наверху лежат один контейнер А (а под ним, если есть, B). Тип 4 - не опасны, с контейнером B наверху.
Теперь перейдем к стопкам размером N + 1. Каждая стопка из рассмотренных ранее классов породит 2 стопки, причем несложные логические рассуждения (возьмите карандаш) показывают, что:
из стопки 1-го класса получится 2 стопки 1-го класса; из стопки 2-го класса получится по стопке 1-го и 4-го класса; из стопки 3-го класса получится по стопке 2-го и 4-го класса; из стопки 4-го класса получится по стопке 3-го и 4-го класса;
Теперь о граничных (вообще-то, для итеративных схем лучше говорить "о начальных") условиях. Их можно написать как для N = 1 (по одной стопке типа 3 и 4), так и для N = 0 (одна стопка типа 4 - собственно, стопок нет вообще). Заметим, что как и в предыдущей задаче, нам достаточно знать количества стопок высоты на единицу меньшей текущей. После этого решение становится совсем простым.
к занятию № 2
Конец формы
[посмотреть подсказку] K-ичные числа
Эта задача почти не отличается от предыдущей, если число представить как стопку, а нули — как контейнеры типа A. Очевидно, что все числа разбиваются на три класса. Остается только прописать переходы при добавлении одной цифры. Лучше (привычнее) сделать это в десятичной системе счисления, а затем заменить девятки (количество ненулевых цифр) на K – 1, а десятки — на K. В результате основной цикл будет выглядеть так:
for i := 2 to N do
begin
OTZ := TZ; OZ := Z; ONZ := NZ;
TZ := OTZ * K + Z; {TZ — два нуля}
Z := ONZ; {Z — один ноль}
NZ := OZ * (K - 1) + ONZ * (K - 1) {NZ — в конце не ноль}
end;
к занятию № 2
Конец формы
|
|
К-ичные числа Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Ограничения: 2 <= K <= 10, N + K <= 18. Формат входных данных Числа N и K в десятичной записи, разделенные пробелом или переводом строки. Формат выходных данных Искомое число в десятичной записи.
[посмотреть подсказку]
Подпалиндром
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. Например, HELOLEH является подпалиндромом строки HTEOLFEOLEH. Напишите программу, находящую в данной строке подпалиндром максимальной длины. Формат входных данных Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита. Формат выходных данных В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них.
[посмотреть подсказку] Подпалиндром
Эта задача является своеобразным водоразделом. Задачи, рассмотренные ранее, были достаточно простыми. Теперь начинается если не “высший пилотаж”, то уж никак не “обязательная программа”. Если Вам не удаётся их решить, то не стоит отчаиваться — с помощью таких задач определяются победители областных олимпиад.
Итак, мы имеем строку длины N. Будем искать палиндромы для подстроки с i-го символа по j-ый включительно, то есть писать функцию F(I, J). Хотелось бы, что она возвращала сам палиндром, но это невозможно из-за нехватки памяти. Ограничимся одной длиной. Массив целых 100 * 100 в памяти помещается свободно. Размещаем граничные случаи: F(I, I) = 1 и F(I, J) = 0, если I > J. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпалиндрома — тогда F(I, J) = F(I + 1, J). Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция K), тогда F(I, J) = 2 + F(I + 1, K – 1). Надо предусмотреть еще случай I = K, а затем отсекать рекурсию известным способом. Получается примерно следующее:
Function F(i, j : Integer) : Integer;
var Ch : Char; R1, R2 : Integer; k : byte;
begin
if Mat[i, j] = -1 then
BEGIN
k := j;
while Inp[i] <> Inp[k] do dec(k);
R1 := F(i + 1, j);
if i <> k then R2 := F(i + 1, k - 1) + 2 else R2 := 1;
if R1 > R2 then Mat[i, j] := R1 else Mat[i, j] := R2
END;
F := Mat[i, j]
end;
Итеративно заполнять массив тоже можно, но при этом “стандартный” двойной цикл от 1 до N не годится. Попробуйте, такое решение тоже существует…
Первая, наиболее сложная, часть задачи решена (достаточно вызвать F(1, N)). Решение второй части тоже интересная задача, но здесь не рассмотрено (в архиве предложено полное решение задачи).
Примечание только для профессионалов: можно решать задачу и “в лоб” — переворачиваем введенную строку и используем на двух строках (исходной и полученной) алгоритм Нудельмана-Фишнера.
к занятию № 2
Конец формы