Подсчитывая варианты

В прошлом номере мы с Вами рассмотрели один из очень
полезных методов решению задач, который называется методом
динамического программирования. Сводя решение задачи к реше-
нию подзадач этот метод иногда позволяет достаточно просто и
красиво решать задачи. Проиллюстрируем на следующих примерах
его применение.
Задача 1. Фишка может двигаться по полоске длины N кле-
ток только вперед. Сначала фишка стоит в первой клетке. Дли-
на хода фишки не более K клеток. Найти число различных пу-
тей, по которым фишка может пройти поле от начала до конца.
Пример. N=4, K=2, количество различных путей 3.
Действительно, возможные пути:
1,1,1
1,2
2,1.
Очевидное решение задачи предполагает разложение числа
(N-1) на всевозможные суммы таким образом, чтобы каждое сла-
гаемое в сумме не превосходило k, и затем подсчета количест-
ва таких разложений. Таких разложений очень много, особенно
если учитывать, порядок слагаемых в разложении существенен,
так как он соответствует различной последовательности ходов
фишки.
Поскольку в задаче не требуется отыскивать все возмож-
ные пути, а нужно только указать их количество, попытаемся
применить метод динамического программирования.
При N=1 будем считать количество путей равным 1 (фишка
уже находится в последней клетке).
При N=2 задача имеет единственное решение, которое мож-
но найти без особых проблем. Количество всевозможных путей
равно 1.
Обозначим через S(i) количество различных путей, по ко-
торым фишка может пройти полоску от начала до позиции с но-
мером i. Предположим теперь, что для любого j от 1 до i из-
вестны значения величин S(j). Задача состоит в определении
правила вычисления значения S(i+1), используя значения вы-
численных ранее величин. Легко заметить, что в позицию с но-
мером i+1 фишка может попасть из позиций с номерами не мень-
шими, чем i-k. Следовательно, в случае i>k справедлива сле-
дующая формула:
S(i+1)=S(i)+S(i-1)+…+S(i-k).
Для случая i<=k формулу получите самостоятельно. Вычислим последовательно значения величин S(1), S(2),…, S(N) по описанному выше правилу. Значение S(N) и будет общим количеством различных путей, по которым фишка может пройти полоску от начала до конца. Задача 2. Среди всех N-битных двоичных чисел указать количество тех, у которых в двоичной записи нет подряд иду- щих k единиц. Сами числа выдавать не надо! N и k — натураль- ные, k<=N<=30. Пример: N=3, k=2, количество чисел равно пяти. Действительно, вот эти числа: 000, 001, 010, 100, 101. Как и в предыдущей задаче перебор всех N-битных чисел и подсчет количества тех, которые удовлетворяют условию зада- чи, не является достаточно хорошим решением (почему?). Будем решать задачу для случая k=2. При N=1 количество таких чисел равно 1, при N=2 сущест- вуют два числа. Обозначим через F(i) количество i-битных двоичных чи- сел, у которых в двоичной записи нет двух подряд идущих еди- ниц. Число, удовлетворяющее данному свойству, будем называть допустимым. Получить допустимое i-битное число мы можем дву- мя способами: 1) поставив 0 перед любым допустимым (i-1)-битным чис- лом; 2) поставив 10 перед любым допустимым (i-2)-битным чис- лом. Действительно, других вариантов быть не может. Первая цифра в i-битном числе может быть либо 0 либо 1. После нуля должно стоять допустимое (i-1)-битное число. После 1, по ус- ловию задачи, может стоять только 0, за которым опять же должно стоять допустимое число из (i-2) бит. Итак, F(i)=F(i-1)+F(i-2) для i>2, F(1)=1, F(2)=2.
Полученная последовательность называется последователь-
ностью Фибоначчи.
Для k>2 проведите аналогичные рассуждения и получите
решение самостоятельно.
Задача 3. Покупатель имеет купюры достоинством A(1), …,A(n), а продавец — B(1), .. ,B(m). Необходимо найти максимальную стоимость товара Р, которую покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег на покупку этого товара достаточно.
Если покупатель отдаст все свои купюры продавцу, то по-
нятно, что для решения исходной задачи необходимо найти раз-
мер минимальной сдачи, которую продавец не может вернуть,
используя любые имеющиеся теперь у него купюры C 4i 0 (его и по-
купателя). Для этого удобно отсортировать купюры согласно их
достоинства в порядке неубывания.
Предположим, что продавец может вернуть любую сдачу от
1 до S, используя только первые i купюр. Для следующей (i+1)
-ой купюры достоинства C 4i+1 0 возможны 2 ситуации.
1. C 4i+1 0<S+2. Тогда понятно, что продавец может вернуть любую сдачу от 1 до C 4i+1 0+S, т.к. любая из этих сумм предста- вима либо первыми i купюрами, либо (i+1)-ой купюрой вместе с некоторыми из первых i купюр. 2. C 4i+1 0>S+1. В этом случае продавец не может вернуть
сдачу S+1.
Опишем алгоритм вычисления S.
S:=0;
i:=1;
нц пока (i<=N) и (C[i]<=S+1) ? S:=S+C[i]; ? i:=i+1 кц Если значение S не меньше суммарного количества денег покупателя, то покупатель может купить товар любой доступной ему стоимости, точно рассчитавшись за покупку. Иначе P=A 41 0+…+A 4N 0-S. Задача 4. Задан массив М[1:N] натуральных чисел, упо- рядоченный по неубыванию, то есть M[1]<=M[2]<=…<=M[N]. Найти первое натуральное число, не представимое суммой никаких элементов этого массива, при этом сумма может состо- ять и из одного слагаемого, но каждый элемент массива может входить в нее только один раз. Решим чуть более общую задачу: найдем все непредстави- мые с помощью данных чисел суммы на промежутке от 0 до P=M[1]+ M[2]+ …+M[N]. Заведем массив A[0..P] натуральных чисел. Элемент A[i]=1, если мы можем составить сумму i (т.е. существует набор чисел с суммой i), и A[i]=0 иначе. Будем строить всевозможные суммы, используя последова- тельно из 0, 1, 2, …, N чисел. Очевидно, что сумма из ноля чисел — это ноль, поэтому сначала A[0]=1. Предположим, что мы нашли всевозможные суммы, которые можно составить, используя не более (k-1)-ого числа M[1],…, M[K-1]. Добавим еще одно число M[k]. Теперь мы можем получить следующие суммы: 1) Все суммы, которые можно было составить с помощью чисел M[1], … , M[K-1]. 2) Все суммы, которые можно было составить с помощью чисел M[1], … , M[K-1], увеличенные на M[K]. Расстановка новых пометок в массиве A может выглядеть следующим образом: for i:=P-M[K] downto 0 do if A[i]=1 then A[i+M[K]]:=1; Мы проходим по массиву справа налево для того, чтобы не использовать повторно впервые образованную на данном шаге сумму. После N проходов по массиву алгоритм заканчивает работу. Остается только найти такой минимальный индекс i, для которого выполняется равенство A[i]=0. Если в массиве все элементы ненулевые, то минимальное число есть P+1. Задача 5. Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a1, либо a2, либо … aS бананов (а1

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>