Question

ЕГЭ 2019, не могу разобраться, помогите пожалуйста. №22 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 33 и при этом траектория вычислений содержит число 16 и не содержит числа 30? Можете максимально подробно расписать решение, объяснить что к чему? Заранее спасибо.

Answer 1

Ответ:

22

Объяснение:

Понятно, что каждая из команд может только увеличить число.

У нас обязательно есть число 16, из него есть два пути:

1. сделать +1

2. сделать x2

Если мы сделаем +1, то после этого уже точно не сможем сделать x2, т.к. 17 x 2 =  34, а 34 > 33, а уменьшить число мы не сможем. Если мы будем делать постоянно +1, то мы точно пройдём через 30.

Значит не нужно делать +1, когда мы на числе 16, а надо делать x2.

Следовательно, концовка у нас точно будет такая 16 -> 32 -> 33.

Теперь надо посчитать, сколько различных способов получить 16 из 2. К любому такому способу мы допишем нашу концовку и получим программу подходящую под наши условия, и к тому же все программы, подходящие под данные условия, выглядят именно так.

Считать сколькими способами можно получить 16 из 2 будет динамическим программированием.

ans[i] - количество различных программ, которые получают i из 2.

Очевидно, ans[2] = 1 (пустая программа).

ans[3] = 1 (нужно сделать +1)

ans[4] = ans[3] + ans[2] = 2 (можно сделать +1 к 3, а можно x2 к 2)

Далее вычисления всегда следующие:

ans[i] = ans[i - 1] + ans[i / 2] для чётных i (можно либо добавить +1 к числу i - 1, либо сделать x2 для числа i / 2)

ans[i] = ans[i - 1] для нечётных i (можно получить только путём добавления +1 к числу i - 1)

Итак, считаем:

ans[2] = 1

ans[3] = ans[2] = 1

ans[4] = ans[3] + ans[2] = 2

ans[5] = ans[4] = 2

ans[6] = ans[5] + ans[3] = 4

ans[7] = ans[6] = 4

ans[8] = ans[7] + ans[4] = 6

ans[9] = ans[8] = 6

ans[10] = ans[9] + ans[5] = 8

ans[11] = ans[10] = 8

ans[12] = ans[11] + ans[6] = 12

ans[13] = ans[12] = 12

ans[14] = ans[13] + ans[7] = 16

ans[15] = ans[14] = 16

ans[16] = ans[15] + ans[8] = 22

Значит 16 из 2 можно получить 22 способами. И столькими же способами можно получить 33 из 2 выполняя условия задачи.

Answer 2

Давайте рассмотрим эту задачу поэтапно.

У нас есть две команды: увеличение числа на 1 и умножение числа на 2. Мы хотим создать программу для исполнителя Калькулятор, которая начинается с числа 2 и приводит к результату 33, при этом содержит число 16 и не содержит число 30.

Давайте разобьем решение на две части:

1. Найдем количество программ, которые приводят к результату 33 и содержат число 16, но не содержат число 30.

2. Посчитаем количество программ, которые приводят к результату 33 и содержат число 16.

Давайте начнем с первой части.

1. Найдем количество программ, которые приводят к результату 33 и содержат число 16, но не содержат число 30.

Мы можем разбить это на несколько случаев:

а) Если число 16 достигается увеличением числа на 1, то нам необходимо умножить число на 2 еще 17 раз (чтобы достичь числа 33). Это можно сделать 17-ю последовательными командами умножения на 2.

б) Если число 16 достигается умножением числа на 2, то нам нужно умножить число на 2 еще 15 раз (чтобы достичь числа 32), а затем увеличить результат на 1. Это можно сделать 15-ю последовательными командами умножения на 2 и одной командой увеличения на 1.

В обоих случаях мы не должны использовать команду умножения на 2 после достижения числа 16.

Таким образом, общее количество программ, которые приводят к результату 33, содержат число 16 и не содержат число 30, равно 17 + 1 = 18.

2. Теперь посчитаем количество программ, которые приводят к результату 33 и содержат число 16.

Мы уже знаем, что есть два способа достичь числа 16: увеличением числа на 1 или умножением числа на 2. Нам нужно определить, сколько команд умножения на 2 следует перед числом 16.

Если перед числом 16 стоит k команд умножения на 2, то после числа 16 нам нужно умножить результат на 2 еще (15 - k) раз (чтобы достичь числа 32), а затем увеличить результат на 1.

Мы можем выбрать k от 0 до 15 (включительно), так как после k команд умножения на 2 мы достигнем числа 16, а после (15 - k) команд