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

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

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

Смешанные задачи

Задание 1 #13346

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

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

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

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

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

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

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

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

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

\[\begin {array}{|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 \\ \hline \end{array}\] По условию сказано, что траектория должна содержать число 8, значит \(R(9) = 21\), так как число 9 можем получить только первой командой.

Продолжим заполнять таблицу:

\[\begin {array}{|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 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 21 & 42 & 63 & 105 & 168\\ \hline \end{array}\] В условии сказано, что траектория не содержит число 14. Значит \(R(14) = 0\).

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

\[\begin {array}{|c|c|c|c|c|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 & 15 & 16 & 17 & 18 & 19 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 21 & 42 & 63 & 105 & 168 & 0 & 168 & 168 & 336 & 504 & 840\\ \hline \end{array}\] Отсюда получаем ответ — 840.

Ответ: 840

Задание 2 #13347

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 2 результатом является число 33 и при этом траектория вычислений содержит число 12 и не содержит число 27? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 231 при исходном числе 6 траектория будет состоять из чисел 9, 27, 28.

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

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

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

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

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

Продолжим заполнять таблицу:

\[\begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{11}& 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 \\ \hline \text{24}& 37 & 37 & 37 & 74 & 111 & 148 & 222 & 333 & 481 & 703 & 1036 & 1517 & 2220 & 3256 & 4773 \\ \hline \end{array}\] По услолвию сказано, что траектория не должна содержать число 27. Значит \(R(27) = 0\).

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

\[\begin {array}{|c|c|c|c|c|c|c|c|} \hline \text{26}& 27 & 28 & 29 & 30 & 31 & 32 & 33 \\ \hline \text{4773}& 0 & 3256 & 8029 & 8029 & 11285 & 19314 & 27343 \\ \hline \end{array}\] Отсюда получаме ответ — 27343

Ответ: 27343

Задание 3 #13348

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

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

Прибавить 2,

Прибавить 3,

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

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 6 и 9, но не содержит число 13? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 123 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 9, 12, 24.

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

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

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

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

\[\begin {array}{|c|c|c|c|c|c|} \hline \text{1} & 2 & 3& 4 & 5 & 6 \\ \hline \text{1} & 1 & 1 & 3 & 2 & 5 \\ \hline \end{array}\] Так как по условию сказано, что траектория должна содержать число 6, значит последующие числа мы можем получать только из 6. Продолжим заполнять таблицу:

\[\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 & 1 & 3 & 2 & 5 & 0 & 5 & 5 \\ \hline \end{array}\] Аналогично с 9. Сразу можно сказать, что число 13 нельзя никак получить, так как по условию траектория не должна через него проходить. Значит \(R(13) = 0\). Заполним таблицу до конца:

\[\begin {array}{|c|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 & 15 \\ \hline \text{1} & 1 & 1 & 3 & 2 & 5 & 0 & 5 & 5 & 0 & 5 & 5 & 0 & 10 & 5\\ \hline \end{array}\]

Ответ: 5

Задание 4 #13349

Геральт копит чеканные монеты, количество которых записано на экране.

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

1. Прибавить 5 монет, убив утопца,

2. Прибавить 10 монет, выполнив заказ на призрака,

3. Увеличить количество монет в 2 раза, сыграв в гвинт.

Первый вариант учеличивает количество монет на 5, второй — на 10, третий — умножает количество монет на 2. Программа для Геральта из Ривии — это последовательность вариантов.

Геральту нужно накопить 100 монет, чтобы выкупить Лютика из плена эльфов.

Сколько существует программ, для которых при исходном количестве монет 15 является результатом 100 монет. При этом траектория вычислений содержит любимое число Геральта — 50 и не содержит числа 25 и 40? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 123 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 12, 22, 44.

Составим формулы:

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

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

Заметим, что количество программ будет меняться только на числах кратных 5. Заполним таблицу по данным формулам, учитывая условия траектории:

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{15} & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 & 75 & 80 & 85 & 90 & 95 & 100 \\ \hline \text{1} & 1 & 0 & 2 & 2 & 0 & 2 & 4 & 2 & 4 & 6 & 10 & 16 & 26 & 42 & 68 & 110 & 180 \\ \hline \end{array}\]

Лютик точно будет спасён!

Ответ: 180

Задание 5 #13350

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

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

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

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

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

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

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 32 и при этом траектория вычислений содержит число 13 и 25, но не содержит 28 и 31? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 1423 при сиходном числе 5 траектория будет состоять из чисел 6, 12, 15, 20.

Составим формулы для решения этой задачи:

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

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

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

\[\begin{array}{|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 \\ \hline \text{1} & 2 & 2 & 5 & 7 & 12 & 19 & 33 & 50 & 83 & 128 & 209 & 325 \\ \hline \end{array}\]

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

\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{13} & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline \text{325} & 325 & 325 & 650 & 975 & 1625 & 2600 & 3900 & 6175 & 9750 & 15275 & 24050 & 37700 \\ \hline \end{array}\]

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

\[\begin{array}{|c|c|c|c|c|c|c|c|} \hline \text{25} & 26 & 27 & 28 & 29 & 30 & 31 & 32 \\ \hline \text{37700} & 37700 & 37700 & 0 & 37700 & 113100 & 0 & 75400 \\ \hline \end{array}\]

Ответ: 75400

Задание 6 #12679

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

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

Прибавить 4,

Прибавить 5,

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

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

Сколько существует программ, для которых при исходном числе 3 результатом является число 23 и при этом траектория вычислений содержит число 11, но не содержит число 13 и 18? Траек­то­рия вы­чис­ле­ний про­грам­мы — это по­сле­до­ва­тель­ность ре­зуль­та­тов вы­пол­не­ния всех ко­манд про­грам­мы. На­при­мер, для про­грам­мы 123 при ис­ход­ном числе 7 тра­ек­то­рия будет со­сто­ять из чисел 11, 16, 32.

Составим фомулы для решения этой задачи:

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

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

Заметим, что число 3 мы получаем одним способом — пустой программой. Числа 4, 5 мы получить не можем данными командами. Заполним таблицу:

\[\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} \hline \text{3} & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ \hline \text{1} & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2 & 0 & 0 & 0 & 2 & 2 & 0 & 0 & 2 & 4 & 2 & 2 & 2 \\ \hline \end{array}\]

Ответ: 2

Задание 7 #12680

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

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

Прибавить 1,

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

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

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

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

Составим формулы для решения этой задачи:

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

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

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

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

Заполним таблицу по данным формулам и со всеми условиями траектории.

\[\begin{array}{|c|c|c|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 & 15 & 16 & 17 \\ \hline \text{1} & 2 & 3 & 5 & 5 & 10 & 10 & 15 & 18 & 23 & 0 & 15 & 15 & 0 & 5 & 20 & 20\\ \hline \end{array}\]

Так как траектория должна проходить через число 17, то последующие числа мы можем получить только командой 1. Количество программ изменится только на \(17 \cdot 2 = 34\). Отсюда следует, что ответ 20.

Ответ: 20