Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

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

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

Решение заданий

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

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

  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

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

1. Прибавить 1

2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?

Решение:

  1. у нас в задании две особые точки – числа 14 (через которое должна проходить траектория) и 25 (а сюда она попасть НЕ должна)
  2. сначала, так же, как и в задачах,  рассмотренных ниже, составляем рекуррентную формулу, по которой будем вычислять количество  обозначить количество разных программ для получения числа N из начального числа 1:
  3. число N могло быть получено одной из двух операций:
  4. увеличением на 1 числа N-1;
  5. умножением на 2 числа N/2 (только для N, которые делятся на 2);

 для нечётных чисел

 для чётных чисел

  • для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; .
  • составляем таблицу до первой особой точки – числа 14:

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

  • поскольку траектория не может проходить через 25, для N = 25 принимаем KN = 0 (в таблице эта ячейка выделена красным цветом)
  • дальше заполняем оставшиеся ячейки второй части таблицы обычным способом (см. задачи ниже):

Ответ: 13.

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

1. прибавь 1

2. прибавь 2

3. прибавь следующее

Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья прибавляет к числу на экране число, большее на 1 (к числу 3 прибавляется 4, к числу 9 прибавляется 10 и т. д.). Программа для исполнителя Калькулятор– это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 10?

Решение:

  1. заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
  2. для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через KN обозначить количество разных программ для получения числа N из начального числа 2, то K2=1 .
  3. теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую KN с предыдущими элементами последовательности K1,K2,…,KN-1 , то есть с решениями таких же задач для меньших N
  4. число N могло быть получено одной из трёх операций сложения:
  5. увеличением на 1 числа N-1;
  6. увеличением на 2 числа N-2;
  7. из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа;

поэтому

 для чётных чисел

 для нечётных чисел

  • остается по этой формуле заполнить таблицу для всех значений от 2 до 10:

Ответ –  47.

Задание 4. Исполнитель Май4 преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 2 3. прибавь 4 Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья – на 4. Программа для исполнителя Май4 – это последовательность команд. Сколько есть программ, которые число 21 преобразуют в число 30?

Решение:

  1. заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
  2. все числа, меньшие начального числа 21, с помощью этого исполнителя получить нельзя, для них количество программ будет равно 0
  3. для начального числа 21 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через KN обозначить количество разных программ для получения числа N из начального числа 21, то
    K21 = 1.
  4. теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую KN с предыдущими элементами последовательности K1,K2,…,KN-1 , то есть с решениями таких же задач для меньших N
  5. любое число N > 21 могло быть получено одной из трёх операций сложения соответственно из чисел N-1, N-2 и N-4, поэтому
  • остается по этой формуле заполнить таблицу для всех значений от 21 до 30:

Ответ — 96

Задание 5. У исполнителя Калькулятор две команды:

1. прибавь 3

2. вычти 2

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить  из числа 1 с помощью программы, которая содержит ровно 5 команд?

Решение (1 способ, построение полного графа решения):

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

теперь посмотрим, что удается получить за 2 шага; учитывая, что (-2+3)=(+3-2), одно из значений повторяется: мы можем получить -1 + 3 = 2 и 4 – 2 = 2, то есть получается не дерево, а граф:

так с помощью программ, содержащих ровно 2 команды, можно получить 3 различных числа 

строим еще уровень: программы из 3-х команд дают 4 разных числа:

обратим внимание, что числа на каждом уровне отличаются друг от друга на 5 =(+3-(-2), то есть они не могут повторяться

четвертый уровень дает 5 различных чисел:

и пятый – 6 решений:

Ответ: 6.

Решение (2 способ, краткий):

как следует из приведенных построений, если система команд исполнителя состоит из двух команд сложения/ вычитания, то все возможные программы, содержащие ровно N команд , дают N+1 различных чисел

Ответ: 6.

Решение (3 способ, Л.В. Зенцова, лицей № 36 ОАО «РЖД» г.Иркутска):

для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения

поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки):
11111
11112
11122
11222
12222
22222

Ответ: 6.

Top