DEMO вариант:
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
- Прибавить 1
- Умножить на 2
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
РЕШЕНИЕ:
Проверим решение программой (Python)
Количество программ с обязательным этапом
Исполнитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
———————- Прибавить 1 (увеличивает число на экране на 1)
- Прибавить 2 (увеличивает его на 2)
- Умножить на 2 (умножает его на 2)
Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
РЕШЕНИЕ:
Решение.
Искомое количество программ равно произведению количества программ, получающих из числа 3 число 10, на количество программ, получающих из числа 10 число 12.
Пусть R(n) — количество программ, которые число 3 преобразуют в число n, а P(n) — количество программ, которые число 10 преобразуют в число n.
Для всех n > 5 верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(n — 1) + R(n — 2), так как существует два способа получения n — прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n — 1) + P(n — 2)
2. Если n делится на 2, тогда R(n) = R(n — 1) + R(n — 2) + R(n / 2). Аналогично P(n) = P(n — 1) + P(n — 2) + P(n / 2)
Последовательно вычислим значения R(n):
R(3) = 1
R(4) = R(3) = 1
R(5) = R(4) + R(3) = 1 + 1 = 2
R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4
R(7) = R(6) + R(5) = 4 + 2 = 6
R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11
R(9) = R(8) + R(7) = 11 + 6 = 17
R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30
Теперь вычислим значения P(n):
P(10) = 1
P(11) = P(10) = 1
P(12) = P(11) + P(10) = 2
Таким образом, количество программ, удовлетворяющих условию задачи, равно 30 · 2 = 60.
Ответ: 60.
Количество программ с избегаемым этапом
Исполнитель преобразует число на экране.
У исполнителя две команды, которым присвоены номера:
—————
- Прибавь 1 (увеличивает число x на экране на 1)
- Сделай нечётное (вторая переводит число x в число 2x+1, переводит 10 в 21)
Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.
Количество программ с избегаемым этапом
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
———————
- Прибавить 1
- Прибавить 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 20 и при этом траектория вычислений содержит число 9 и не содержит числа 15?
Траектория вычислений — это последовательность результатов выполнения всех команд программы.
Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.
Поиск количества программ по заданному числу
У исполнителя две команды. Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.Командам присвоены номера:
—————-
- Прибавь 2
- Умножь на 5
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые число 2 преобразуют в число 50?
Не содержит чисел 5 и 10
Исполнитель РазДваТри преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.
Программа для исполнителя РазДваТри — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 14 и при этом траектория вычислений не содержит чисел 5 и 10?
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.
Поиск количества чисел по заданному числу команд
У исполнителя Калькулятор две команды.
Первая из них увеличивает число на экране на 2, вторая — утраивает его.
—————
- прибавь 2
- умножь на 3
Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 3 команды?
- Создаем пустой список, чтобы складывать в него полученные числа.
- Функция принимает на вход два аргумента: n — число, которое будет увеличиваться, k — количество команд
- Если команд ровно 10, текущее число добавляем в список, функцию прерываем.
- Если команд больше 10, функцию прерываем
- Продолжаем рекурсию, но на этот раз результаты функций не складываем, а объединяем оператором «или» (OR)
- Вызываем функцию с начальным значением 2 и числом команд 0
- Выводим длину множества чисел списка буз повторов
Поляков ЕГЭ
(№ 5012) (М. Фирсов)
- Прибавь 4
- Прибавь 7
- Раздели нацело на 2
