Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

22. Линейные программы и ветвление

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения
Задание 1 #13361

Исполнитель УВЕЛИЧИТЕЛЬ9000 преобразует целое число, записанное на экране.

У исполнителя три команды. Каждой команде присвоен номер:

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

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

3. Умножить на 4

Первая из них увеличивает число на экране на 1, второе - увеличивает его на 2, третья - увеличивает его в 4 раза.

Программа для УВЕЛИЧИТЕЛЯ9000 - это последовательность команд.

Сколько есть программ, которые преобразуют число 2 в число 17?

Количество программ, которые преобразуют число 2 в число n, обозначим R(n). Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 4, то оно может быть получено командами 1 и 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-1) + R(n-2)\).

Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда \(R(n) = R(n-1) + R(n-2) + R(n:4)\). Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 14 & 22 & 36 & 58 & 95 & 153 & 248 & 401 & 651 & 1052 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 1052.

Ответ: 1052

Задание 2 #9791


Исполнитель МЕГАТРОН преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2.
Программа для МЕГАТРОНа — это последовательность команд.
Сколько есть программ, которые преобразует число 1 в число 9?


Количество программ, которые преобразуют число 1 в число \(n,\) обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 2 и 3 — \(R(4) = R(2) + R(3) = 3.\) Можем заметить, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ \hline \end{array}\] Отсюда видим, что имеем 34 возможных программ для получения числа 9.

Ответ: 34

Задание 3 #9792


Исполнитель Калькулятор преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 3.
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 42?


Количество программ, которые преобразуют число 2 в число \(n,\) обозначим \(R(n).\) Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2).\)
Если число на три делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда \(R(n) = R(n-2) + R(n:3).\) Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 & 42 \\ \hline \text{1}& 1 & 2 & 2 & 2 & 3 & 3 & 3 & 5 & 5 & 5 & 7 & 7 & 7 & 9 & 9 & 9 & 12 & 12 & 12 & 15 \\ \hline \end{array}\] Отсюда видим, что всего программ 15.

 

Ответ: 15

Задание 4 #9793


Исполнитель ХЛЕБУШЕК преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2,
3. Прибавь 3.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2, третья — увеличивает его на 3.
Программа для ХЛЕБУШКа — это последовательность команд.
Сколько есть программ, которые преобразуют число 1 в число 14?


Количество программ, которые преобразуют число 1 в число n, обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 1, 2 и 3 — \(R(4) = R(1) + R(2) + R(3) = 6.\) Заметим, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-3) + R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline \text{1}& 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274 & 504 & 927 & 1705 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 1705.

Ответ: 1705

Задание 5 #9795


Исполнитель ЕЩЕНКО преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 10.
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 10 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 40?


Количество программ, которые преобразуют число 2 в число n, обозначим \(R(n).\) Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на десять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2).\)
Если число делится на 10, то вариантов последней команды два: прибавь 2 и умножь на 10, тогда \(R(n) = R(n-2) + R(n:10).\) Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 \\ \hline \text{1}& 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 3 & 4 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 4.

 

Ответ: 4

Задание 6 #9796


Исполнитель Прибавлялка имеет две команды, которым присвоены номера:
1. Прибавь 1,
2. Увеличь старшую цифру числа на 1.
Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 63 с помощью такой команды превратится в число 73. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным.
Программа для Прибавлялки — это последовательность команд.
Сколько есть программ, которые число 31 преобразуют в число 53?


Обе команды увеличивают исходное число. Старшая цифра — 3, следовательно, использовать команду 2 более двух раз бессмысленно.
Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.
Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 31 число 41, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 53. Таким образом, получаем программы: \(211\dots1,\) \(121\dots1,\) и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).
Существует лишь одна программа, в которой команда 2 не используется: \(111\dots1.\)
Таким образом получаем \(6 + 13 + 1 = 20.\)

 

Ответ: 20

Задание 7 #9798


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


Обозначим число программ, преобразующих число 2 в число n как \(R(n).\) Тогда число \(n\) может быть получено либо прибавлением к \(n-1,\) либо к \(n-2,\) либо из некоторого числа \(х\) увеличением на \(x-1,\) так что \(n = x + x - 1,\) откуда \(x = \frac{n + 1}{2};\) так могут быть получены только нечетные числа.
Тогда для четных чисел \(R(n) = R(n-1) + R(n-2),\) а для нечетных — \(R(n) = R(n-1) + R(n-2) + R(\frac{n + 1}{2}\)). Заполним таблицу по данным формулам:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text{1}& 1 & 3 & 4 & 10 & 14 & 28 & 42 & 80 & 122 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 122.

Ответ: 122