Погода
Календарь
Январь 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123456
78910111213
14151617181920
21222324252627
28293031  
Страницы сайта

Оператор присваивания и ветвления. Перебор вариантов, построение дерева.

  • Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
  • Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
  • «подсчитайте количество способов…»;
  • «как оптимально распределить…»;
  • «найдите оптимальный маршрут…».
  • Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.

Разбор 22 задания ЕГЭ по информатике 2017 года ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

Исполнитель Счетчик преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:

  1. Прибавь 5
  2. Умножь на 5

Первая команда увеличивает число на экране на 5, вторая умножает его на 5.
Программа для исполнителя Счетчик — это последовательность команд.

Сколько существует программ, для которых при исходном числе 5 результатом является число 250, и при этом траектория вычислений содержит число 35 и не содержит числа 105?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 9, 45, 50.

Решение:

Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:

  1. 5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
  2. 35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
  3. 35 -> 105 — «ненужная» часть траектории;
  4. 105 -> 250 — тоже «ненужная» часть.
  5. Чтобы вычислить результат, т.е. количество программ, необходимо:
траектория 1 * (траектория 2 - (траектория 3 * траектория 4))

полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий
  • Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5! (5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т. п.).
  • Кроме того, будем использовать метод решения с конца, т. е. двигаясь от наибольших подходящих чисел к наименьшим.
  • Расчет отрезка 1: 5 -> 35
    • Возьмем такое число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
5 не подходит: применимы две команды в интервале до 35:  
5 + 5 = 10 и 5 * 5 = 25
10 подходит: применима только одна команда:
10 + 5 = 15, а 10 * 5 = 50 - больше 35
  • Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):
  • Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):
  • Итого получили две программы.
  • Расчет отрезка 2: 35 -> 250
  • Возьмем такое число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:
55  
т.к. 55 * 5 = 275 - это больше числа 250
  • Затем будем последовательно брать подходящие меньшие числа

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

  • для числа 45 мы взяли результат, полученный для числа 50 (2);
  • для числа 40 мы взяли результат, полученный для числа 45 (3);
  • для числа 35 мы взяли результат, полученный для числа 40 (4);
  • Расчет отрезка 3: 35 -> 105
  • Возьмем такое число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:
35  
т.к. 35 * 5 = 175 - больше числа 105
2

Результат: 1

Расчет траектории 4: 105 -> 250

Результат: 1

Посчитаем результат, согласно полученной формуле:

траектория 1 * (траектория 2 - (траектория 3 * траектория 4)) 
2 * (5 - 1 * 1) = 8

Результат: 8

Top