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

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

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

Количество программ, проходящих через заданное число

Задание 1 #12803

Ис­пол­ни­тель РЫБИНСК пре­об­ра­зу­ет число на экра­не.

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

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

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

Пер­вая ко­ман­да уве­ли­чи­ва­ет число на экра­не на 1, вто­рая уве­ли­чи­ва­ет его на 2. Про­грам­ма для ис­пол­ни­те­ля РЫБИНСК — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко су­ще­ству­ет про­грамм, для ко­то­рых при ис­ход­ном числе 1 ре­зуль­та­том яв­ля­ет­ся число 14 и при этом тра­ек­то­рия вы­чис­ле­ний со­дер­жит число 9? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 10, 11.

Пусть \(R(n)\) — ко­ли­че­ство про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число n. Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-2)\)

Заполним таблицу по данной формуле до 9:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34\\ \hline \end{array}\]

По формуле \(R(10) = R(9) + R(8) = 55\), но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно \(R(10) = R(9) = 34\).

Заполним таблицу до конца:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 34 & 68 & 102 & 170 & 272\\ \hline \end{array}\]

Отсюда получаем искомое количество программ — 272.

Ответ: 272

Задание 2 #12805

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

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

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

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

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

Первая команда увеличивает число на экране на 2, вторая — на 3, третья — утраивает число на экране. Программа для исполнителя Яблочко — это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 28 и при этом троектория содержит числа 12 и 18? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 9, 12, 14.

Пусть \(R(n)\) — количество программ, которык число 3 преобразуют в число n. Тогда верно следующее утверждение:

\(R(n) = R(n-2) + R(n-3)\) — если число не делится на 3.

\(R(n) = R(n-2) + R(n-3) + R(n:3)\) — если число делится на 3.

Заполним таблицу по данным формулам до 12:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline 1 & 0 & 1 & 1 & 1 & 2 & 3 & 3 & 5 & 6\\ \hline \end{array}\]

По условию дано, что траектория проходит через число 12. Значит \(R(13) = 0\). Продлим таблицу до 18:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18\\ \hline 1 & 0 & 1 & 1 & 1 & 2 & 3 & 3 & 5 & 6 & 0 & 6 & 6 & 6 & 12 & 12\\ \hline \end{array}\]

По условию сказано, что траектория должна проходить через числа 12 и 18. следовательно \(R(19) = 0\), так как число 19 нельзя получить напрямую из 12 или 18. Составим таблицу до конца:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 \\ \hline 1 & 0 & 1 & 1 & 1 & 2 & 3 & 3 & 5 & 6 & 0 & 6 & 6 & 6 & 12 & 12 & 0 & 12 & 12 & 12 & 24 & 24 & 36 & 48 & 60 & 84 \\ \hline \end{array}\]

Отсюда получаем ответ — 84.

Ответ: 84

Задание 3 #12807

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

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая — на 5, третья — удваивает число на экране. Программа для исполнителя Калькулятор — это последовательность команд.

Сколько существует программ, для которых при исходном числе 4 результатом является число 24 и при этом троектория содержит числа 11 и 17 ? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 121 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 13, 14.

Пусть \(R(n)\) — количество программ, которые число 4 преобразуют в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-5)\) — если число не делится на 2.

\(R(n) = R(n-1) + R(n-5) + R(n:2)\) — если число делится на 2.

Заполним таблицу по данным формулам до 11:

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline 1 & 1 & 1 & 1 & 2 & 3 & 5 & 6\\ \hline \end{array}\]

По условию траектория должна проходить через число 11, значит \(R(12) = 6\), так как число 12 можно получить только из числа 11 (соблюдая траекторию). Заполним таблицу до 18:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18\\ \hline 1 & 1 & 1 & 1 & 2 & 3 & 5 & 6 & 6 & 6 & 6 & 6 & 12 & 18 & 24\\ \hline \end{array}\]

Аналагично \(R(19) = 24\), так как число 19 можно получить только из 18, соблюдая траекторию. Заполним таблицу до конца:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\ \hline 1 & 1 & 1 & 1 & 2 & 3 & 5 & 6 & 6 & 6 & 6 & 6 & 12 & 18 & 24 & 24 & 24 & 24 & 24 & 48 & 72\\ \hline \end{array}\]

Отсюда получаем ответ: 72.

Ответ: 72

Задание 4 #12808

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

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

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

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

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

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

Первая команда увеличивает число на экране на 2, вторая – на 3, третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя Школково — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 38 и при этом троектория содержит числа 14 и 29? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 132 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 9, 18, 21.

Пусть \(R(n)\) — количество программ, которые число 2 преобразует в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-2) + R(n-3)\) — если число не делится на 2 и на 3.

\(R(n) = R(n-2) + R(n-3) + R(n:2)\) — если число делится на 2, но не делится на 3.

\(R(n) = R(n-2) + R(n-3) + R(n:3)\) — если число делится на 3, но не делится на 2.

\(R(n) = R(n-2) + R(n-3) + R(n:2) + R(n:3)\) – если число делится и на 2, и на 3.

Заполним таблицу по данным формулам до 14:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline 1 & 0 & 2 & 1 & 3 & 3 & 6 & 6 & 10 & 12 & 21 & 22 & 36\\ \hline \end{array}\]

По условию траектория должна проходить через число 14, значит \(R(15) = 0\), так как мы никак не можем получить число 15, чтобы траектория проходила через число 14. Продолжим заполнять таблицу:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29\\ \hline 36 & 0 & 36 & 36 & 36 & 72 & 72 & 108 & 144 & 180 & 252 & 324 & 432 & 576 & 756 & 1008\\ \hline \end{array}\]

Аналогично \(R(30) = 0\), так как число 30 никак нельзя получить, чтобы траектория проходила через число 29. Заполним таблицу до конца:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38\\ \hline 1008 & 0 & 1008 & 1008 & 1008 & 2016 & 2016 & 3024 & 4032 & 5040\\ \hline \end{array}\]

Отсюда получаем ответ: 5040.

Ответ: 5040

Задание 5 #12809

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

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

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая — на 2, третья — удваивает число на экране, четвертая — утраивает число на экране. Программа для исполнителя Ребус — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 27 и при этом троектория содержит числа 13 и 19 ? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 132 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 16, 18.

Пусть \(R(n)\) — количество программ, которые число 2 преобразуют в число \(n\). Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-2)\) — если число не делится на 2 и на 3.

\(R(n) = R(n-1) + R(n-2) + R(n:2)\) — если число делится на 2, но не делится на 3.

\(R(n) = R(n-1) + R(n-2) + R(n:3)\) — если число делится на 3, но не делится на 2.

\(R(n) = R(n-1) + R(n-2) + R(n:2) + R(n:2)\) — если число делится и на 2, и на 3.

Используя данные формулы, заполним таблицу до 13:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\ \hline 1 & 1 & 3 & 4 & 9 & 13 & 25 & 39 & 68 & 107 & 187 & 294\\ \hline \end{array}\]

По условию траектория должна проходить через число 13, значит \(R(14) = 294\), так как число 14 мы можем полчить только командой 1 из числа 13, чтобы траектория проходила через число 14. Продолжим заполнять таблицу:

\[\begin{array}{|c|c|c|c|c|c|c|} \hline 13 & 14 & 15 & 16 & 17 & 18 & 19\\ \hline 294 & 294 & 588 & 882 & 1470 & 2352 & 3822\\ \hline \end{array}\]

Аналогично \(R(20) = 3822\). Заполним таблицу до конца:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27\\ \hline 3822 & 3822 & 7644 & 11466 & 19110 & 30576 & 49686 & 80262 & 129948\\ \hline \end{array}\]

Отсюда получаем ответ – 129948.

Ответ: 129948

Задание 6 #13344

Исполнитель ПЕЧЕНЬКА преобразует число, записанное на экране.

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

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

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

Первая команда увеличивает число на экране на 1, вторая — удваивает его. Про­грам­ма для ис­пол­ни­те­ля ПЕЧЕНЬКА — это по­сле­до­ва­тель­ность ко­манд.

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

Пусть \(R(n)\) — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:

\(R(n) = R(n-1)\) — если число n не делится на 2.

\(R(n) = R(n-1) + R(n:2)\)

Заполним таблицу по данной формуле до 10:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text{1}& 1 & 2 & 2 & 3 & 3 & 5 & 5 & 7 \\ \hline \end{array}\] Заметим, что количество программ изменяется только на четных n. Значит следующее число, на котором изменится количество программ — 12. По условию нам дано, что траектория должна содержать число 10, значит — \(R(12) = R(11)\). Далее данное значение не будет меняться, так как тогда траектория не будет проходить через число 10.

В итоге получаем ответ — 7

Ответ: 7

Задание 7 #13351

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

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

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

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

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

Первая команда увеличивает число на экране на 1, вторая — на 3, третья — удваивает число на экране. Программа для исполнителя Студент — это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 17 и при этом троектория содержит число 10? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 123 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 8, 11, 22.

Пусть \(R(n)\) — количество программ, которык число 2 преобразуют в число n. Тогда верно следующее утверждение:

\(R(n) = R(n-1) + R(n-2)\) — если число не делится на 2.

\(R(n) = R(n-1) + R(n-2) + R(n:2)\) — если число делится на 2.

Заполним таблицу по данным формулам до 10:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text {1}& 1 & 2 & 3 & 5 & 7 & 12 & 17 & 27 \\ \hline \end{array}\]

По условию сказано, что траектория должна проходить через число 10, значит \(R(11) = 30\), так как число 11 мы можем получить (проходя через число 10) только командой 1. Заполним таблицу до конца:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline \text {1}& 1 & 2 & 3 & 5 & 7 & 12 & 17 & 27 & 27 & 27 & 54 & 81 & 108 & 162 & 243\\ \hline \end{array}\]

Отсюда получаем ответ — 243.

Ответ: 243