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

14.03.2022
Задание 23. Умение анализировать результат исполнения алгоритма: все задания Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

DEMO вариант:

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

————————
  1. Прибавить 1
  2. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

РЕШЕНИЕ:

Проверим решение программой (Python)

Количество программ с обязательным этапом

Исполнитель  преобразует число, записанное на экране.

У исполнителя есть три команды, которым присвоены номера:

———————
  1. Прибавить 1 (увеличивает число на экране на 1)
  2. Прибавить 2 (увеличивает его на 2)
  3. Умножить на 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. Прибавь 1 (увеличивает число x на экране на 1)
  2. Сделай нечётное (вторая переводит число x в число 2x+1, переводит 10 в 21)

Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые число 1 преобразуют в число 27, причём траектория вычислений не содержит число 26?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Количество программ с избегаемым этапом

Исполнитель преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:
———————

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

Программа для исполнителя — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 20 и при этом траектория вычислений содержит число 9 и не содержит числа 15?

Траектория вычислений — это последовательность результатов выполнения всех команд программы.
Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 9, 10, 12.

Поиск количества программ по заданному числу

У исполнителя две команды. Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.Командам присвоены номера:
—————-

  1. Прибавь 2
  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, вторая — утраивает его.
—————

  1. прибавь 2
  2. умножь на 3

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

  1. Создаем пустой список, чтобы складывать в него полученные числа.
  2. Функция принимает на вход два аргумента: n — число, которое будет увеличиваться, k — количество команд
  3. Если команд ровно 10, текущее число добавляем в список, функцию прерываем.
  4. Если команд больше 10, функцию прерываем
  5. Продолжаем рекурсию, но на этот раз результаты функций не складываем, а объединяем оператором «или» (OR)
  6. Вызываем функцию с начальным значением 2 и числом команд 0
  7. Выводим длину множества чисел списка буз повторов

Поляков ЕГЭ

(№ 5012) (М. Фирсов)

Исполнитель Счеты преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
  1. Прибавь 4
  2. Прибавь 7
  3. Раздели нацело на 2
Первая команда увеличивает число на экране на 4, вторая увеличивает его на 7, третья делит на 2 нацело (остаток отбрасывается). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые состоят из 10 команд и при исходном числе 1 результатом является 1?