Вычислительные стратегии. 23 задание.

Введение

Динамическое программирование! Страшно звучит? Если Вы не знакомы с этим понятием, то может показаться, что это что-то сложное и (скорее всего) бесполезное. На самом же деле - это очень полезный метод, который помогает решать множество задач, связанных с комбинаторикой, статистикой, теорией игр. Но ГЛАВНОЕ – с помощью ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ мы сможем решить 23 задание из ЕГЭ.

Что же такое динамическое программирование? Представим, что Вам задали решить какую-то ОЧЕНЬ СЛОЖНУЮ задачу для данного числа N. И один из друзей знает ответ на эту задачу, но только для числа N-1. Сосед по парте недавно посчитал ответ для N-2. А пару дней назад вы с преподавателем разбирали решение данной задачи для числа N-3. Собрав круглый стол по решению НЕИМОВЕРНО СЛОЖНОЙ ЗАДАЧИ по программированию, вы несколько часов ломали голову. Пока вдруг не разложили сложную задачу для числа N на комбинацию из более простых решений данной задачи для N-1, N-2, N-3 (ответ для которых вам уже известен). Поздравляю! Вы воспользовались идеей динамического программирования. Вы свели одну СЛОЖНУЮ задачу к решению нескольких ПРОСТЫХ. А ведь решать несколько простых задач ГОРАЗДО легче, чем одну сложную.

Поскорее перейдем к примерам. Что нам понадобится для решения задачи №23? Умения аккуратно складывать числа должно хватить. Это задание не относится к разряду сложных, наоборот – если разобраться с теорией и аккуратное посчитать, то заветный первичный балл твой! Главное лишь желание и чуть-чуть знаний.

Задача №1

Для начала, поймем самое главное – как решить нашу задачу для какого-либо числа N. То есть мы хотим понять, сколько всего существует способов преобразовать данное число 30 в N. Посмотрим, каким образом мы сможем получить число 30:

1) «Прыгнуть» в число N из числа N-1, прибавив к последнему единицу (с помощью команды 1)

2) «Прыгнуть» в число N из числа N-4, прибавив к последнему четверку (с помощью команды 4)

3) «Прыгнуть» в число N из числа N-5, прибавив к последнему пятерку (с помощью команды 5)

Теперь мы сделаем самый важный вывод, который нам поможет нам найти желаемый ответ! Решение данной задачи для некого числа N является суммой решений данной задачи для чисел N-1, N-4 и N-5. Последнее утверждение легко объяснить с помощью простенькой задачи. Представим, что у нас три побочные дороги объединяются в одну главную. По первой дороге идет 10 человек, по второй дороге идет 16 человек, а по третьей дороге идет 3 человека, сколько всего людей будут идти по главной дороге? Нетрудно понять, что ответом будет сумма 3+16+10 = 29. Грубо говоря, три разных потока объединились в одну большую реку. В нашей задаче аналогично – три маленьких ответа для N-1, N-4 и N-5 объединяются в один большой ответ для N.

Запишем результат наших рассуждений в виде рекуррентной формулы F(N) = F(N-1) + F(N-4) + F(N-5), где F(N) – ответ на поставленную задачу для числа N. Многие из вас еще не раз встретятся с похожей записью в будущем (например, решая задание №11).

В самом начале задачи у нас есть одно единственное число 30 – начало нашего пути. Сколькими способами мы можем попасть в число 30? Одним, оно ведь у нас уже дано. То есть, решение задачи для N=30 – один (F(30) = 1). Очень важно отметить еще один факт, что для чисел МЕНЬШЕ 30 решений не существует (их НОЛЬ). Это объясняется тем, что ни одна из представленных операций не позволяет получить число меньше данного.

Все вступительные слова сказаны – переходим к решению! Нам очень поможет табличка, где в первой строке будут перечислены все N, а во второй строке будут записаны F(N). И самым первым шагом – запишем в F(30) единичку (нам ведь это уже известно).

Далее посчитаем F(31). По формуле описанной выше получаем F(31) = F(31-1)+F(31-4)+F(31-5). Чуть-чуть упростив выражение, получаем – F(31) = F(30) + F(27) + F(26). Значение F(30)=1 (мы об этом уже не раз упоминали выше). F(27) и F(26) равны 0. В итоге получили, что F(31) = 1 + 0 + 0. Рассуждая аналогично, найдем ответы для N=32 и N=33.

F(32) = F(32-1) + F(32-4) + F(32-5) = F(31) + F(28) + F(27) = 1 + 0 + 0 = 1

F(33) = F(33-1) + F(33-4) + F(33-5) = F(32) + F(29) + F(28) = 1 + 0 + 0 = 1

Для N = 34 задача становится сложнее, так как у нас уже будет два ненулевых слагаемых.

F(34) = F(34-1) + F(34-4) + F(34-5) = F(33) + F(30) + F(29) = 1 + 1 + 0 = 2

Ну и наконец, для N = 35 все три слагаемых уже не равны нулю.

F(35) = F(35-1) + F(35-4) + F(35-5) = F(34) + F(31) + F(30) = 2 + 1 + 1 = 4

И не забываем заполнять табличку!!!

Надеюсь, что довести задачу до логического конца не составит для вас большой проблемы. Ниже будет СПОЙЛЕР к решению – итоговая таблица. Стоит лишь отметить, что наш ответ содержится в F(46), так как F(46) – количество способов получить из числа 30 число 46.

Подводные камни.

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

1) Траектория вычислений НЕ содержит число Х . В данном случае вначале решения задачи необходимо поставить в F(X) ноль и не пересчитываем его в будущем. Таким образом, мы говорим, что у нас ровно 0 способов получить число Х и в дальнейшем мы его использовать не будем.

Задача №2

Данная задача решается аналогично предыдущей, но только необходимо учесть дополнительное условие. Так как траектория вычислений НЕ содержит число 40, то мы можем сказать, что F(40) = 0. И в самом начале вспомогательная таблица будет принимать следующий вид:

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

2) Траектория вычислений содержит число Х. Данное ограничение учитывается очень просто – в тот момент, когда мы посчитали F(X), необходимо зачеркнуть ту часть таблицы, которая находится правее F(X). Иначе говоря - при подсчете ответа для всех чисел, которые больше Х – мы не должны использовать любой из ответов, полученных для чисел, которые меньше Х.

Задача №3

Воспользуемся таблицей, полученной ранее.

Мы посчитали F(40). Далее мы вычеркиваем все столбцы, левее последнего, который мы заполнили.

И решаем аналогичную задачу только для «усеченной» таблицы.

Ну а задачи подобного рода мы с Вами уже научились решать выше! Стоит также отметить, что иногда в условии говорится о том, что траектория должна содержать не одно число, а несколько. В данном случае задача решается аналогично, необходимо последовательно «отсекать» правые части таблицы в тот момент, когда мы дойдем до заданного числа.

Итог

Я надеюсь, что после прочтения данной статьи – каждый из вас убедился, что 23 задание не требует от вас каких-то непостигаемых знаний. Главное в данном задании – ПРАКТИКА. Чем больше Вы нарешаете подобных задач, тем выше Ваши шансы получить заветный балл.

ОТВЕТ НА ЗАДАЧУ №2

ОТВЕТ НА ЗАДАЧУ №3

Источник: m.vk.com

Комментарии: