Задание 22. Умение анализировать алгоритм, содержащий ветвление и цикл: все задания

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

Версия для печати

1. Задание#T30258

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

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

Прибавить 1
Умножить на 2

Первая команда увеличивает число на экране на вторая умножает его на

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

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

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

Показать разбор и ответ

Нужно сначала преобразовать в затем в и в

Пусть

– количество программ, преобразующих исходное число в число Это число равно сумме

для всех из которых можно одной командой получить Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число, – пустая)

Переход от до можно сделать без удвоений – прибавлением по (

) или с однократным удвоением, при этом удвоить можно одно из трёх чисел

или Всего получается способа перехода.

Переход от к можно сделать двумя способами: одним удвоением или многократным прибавлением

Таким образом, на первом этапе есть вариантов действий, на втором – на третьем – На каждом из этих этапов можно выбрать способ преобразования независимо, значит, общее количество вариантов равно

Ответ: 48

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 8 тыс. раз. С ним справились 61% пользователей.

2. Задание#T30175

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

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

Прибавить 1
Умножить на 2

Первая команда увеличивает число на экране на вторая умножает его на Программа для исполнителя РазДва – это последовательность команд.

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

Показать разбор и ответ

Нужно сначала преобразовать в затем в и в

Пусть

– количество программ, преобразующих исходное число в число Это число равно сумме

для всех из которых можно одной командой получить Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число, – пустая)

Переход от до можно сделать тремя способами: прибавлением по (

), удвоением числа ( ) и удвоением числа ( ). Переход от к можно сделать двумя способами: одним удвоением или многократным прибавлением

Ответ: 42

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 5 тыс. раз. С ним справились 73% пользователей.

3. Задание#T29793

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

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

Прибавить 1
Умножить на 2
Умножить на 3

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

Программа для исполнителя РазДваТри – это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 50, и при этом траектория вычислений содержит число 14 и не содержит числа 16?

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 4 траектория будет состоять из чисел 9, 10, 20.

Показать разбор и ответ

Нужно сначала преобразовать 1 в 14, а затем 14 в 50, не заходя в 16.

Пусть F(b) – количество программ, преобразующих исходное число 1 в число Это число равно сумме F(x) для всех из которых можно одной командой получить Будем находить значения F(b) последовательно для всех от 1 до 14:

F(1) = 1 (единственная программа, сохраняющая исходное число, – пустая)

F(2) = F(1) + F(1) = 2 (от 1 можно перейти к 2 двумя способами)

F(3) = F(2) + F(1) = 2 + 1 = 3

F(4) = F(3) + F(2) = 3 + 2 = 5

F(5) = F(4) = 5

F(6) = F(5) + F(3) + F(2) = 5 + 3 + 2 = 10

F(7) = F(6) = 10

F(8) = F(7) + F(4) = 10 + 5 = 15

F(9) = F(8) + F(3) = 15 + 3 = 18

F(10) = F(9) + F(5) = 18 + 5 = 23

F(11) = F(10) = 23

F(12) = F(11) + F(6) + F(4) = 23 + 10 + 5 = 38

F(13) = F(12) = 38

F(14) = F(13) + F(7) = 38 + 10 = 48

Рассмотрим теперь переход от 14 к 50. Чтобы «обойти» число 16, нужно выполнить умножение. Можно умножить 14 на 2 или на 3, получится 28 или 42. В любом из этих случаев дальнейшее умножение невозможно – получится число больше 50, поэтому придётся прибавлять по 1 до 50. Можно увеличить 14 на 1, получится 15, после этого можно выполнить умножение на 2 или на 3 и далее прибавлять по 1 до 50. Всего получается 4 способа перехода от 14 к 50 без захода в 16.

Любой из способов перехода от 1 к 14 можно совместить с любым из способов перехода от 14 к 50, всего получается 48 · 4 = 192 программы.

Ответ: 192

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 3 тыс. раз. С ним справились 53% пользователей.

4. Задание#T29766

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

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

Прибавить 1
Умножить на 2
Умножить на 3

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

Программа для исполнителя РазДваТри – это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 40, и при этом траектория вычислений содержит число 12 и не содержит числа 14?

Показать разбор и ответ

Нужно сначала преобразовать 1 в 12, а затем 12 в 40, не заходя в 14.

Пусть F(b) – количество программ, преобразующих исходное число 1 в число b. Это число равно сумме F(x) для всех x, из которых можно одной командой получить b. Будем находить значения F(b) последовательно для всех b от 1 до 12:

F(1) = 1 (единственная программа, сохраняющая исходное число, – пустая)

F(2) = F(1) + F(1) = 2 (от 1 можно перейти к 2 двумя способами)

F(3) = F(2) + F(1) = 2 + 1 = 3

F(4) = F(3) + F(2) = 3 + 2 = 5

F(5) = F(4) = 5

F(6) = F(5) + F(3) + F(2) = 5 + 3 + 2 = 10

F(7) = F(6) = 10

F(8) = F(7) + F(4) = 10 + 5 = 15

F(9) = F(8) + F(3) = 15 + 3 = 18

F(10) = F(9) + F(5) = 18 + 5 = 23

F(11) = F(10) = 23

F(12) = F(11) + F(6) + F(4) = 23 + 10 + 5 = 38

Рассмотрим теперь переход от 12 к 40. Чтобы «обойти» число 14, нужно выполнить умножение. Можно умножить 12 на 2 или на 3, получится 24 или 36. В любом из этих случаев дальнейшее умножение невозможно – получится число больше 40, поэтому придётся прибавлять по 1 до 40. Можно увеличить 12 на 1, получится 13, после этого можно выполнить умножение на 2 или на 3 и далее прибавлять по 1 до 40. Всего получается 4 способа перехода от 12 к 40 без захода в 14.

Любой из способов перехода от 1 к 12 можно совместить с любым из способов перехода от 12 к 40, всего получается

38 · 4 = 152 программы.

Ответ: 152

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 3 тыс. раз. С ним справились 60% пользователей.

5. Задание#T9803

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

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

Прибавить 1
Умножить на 2

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе траектория будет состоять из чисел

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

Показать ответ

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 5 тыс. раз. С ним справились 73% пользователей.

6. Задание#T9301

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

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

Прибавить 1
Умножить на 2
Прибавить 3

Первая команда увеличивает число на экране на , вторая умножает его на , третья увеличивает на .

Программа для исполнителя РазДваТри – это последовательность команд.

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

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы

при исходном числе траектория будет состоять из чисел , , .

Показать ответ

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 4 тыс. раз. С ним справились 56% пользователей.

7. Задание#T8653

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

Прибавить 3
Умножить на 2

Первая из них увеличивает число на экране на , вторая умножает его на . Программа для Вычислителя – это последовательность команд.

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

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 1212 при исходном числе траектория будет состоять из чисел

Показать ответ

Это задание решали 2 тыс. раз. С ним справились 60% пользователей.

8. Задание#T4914

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

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

Прибавить 1
Умножить на 2
Прибавить 3

Первая команда увеличивает число на экране на , вторая умножает его на , третья увеличивает на .

Программа для исполнителя РазДваТри – это последовательность команд.

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

Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе траектория будет состоять из чисел , , .

Показать разбор и ответ

Указание:

Указание: найдите количество программ, преобразующих в каждое из чисел от до .

Решение:

Пусть

– количество программ, преобразующих исходное число в число . Это число равно сумме

для всех , из которых можно одной командой получить . Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число, – пустая)

(траектория вычислений не должна содержать число )

Ответ: 22

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 6 тыс. раз. С ним справились 47% пользователей.

9. Задание#T4887

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

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

Прибавить 1
Умножить на 2
Прибавить 3

Первая команда увеличивает число на экране на , вторая умножает его на , третья увеличивает на .

Программа для исполнителя РазДваТри – это последовательность команд.

Показать разбор и ответ

Указание:

Найдите количество программ, преобразующих в каждое из чисел от до .

Решение:

Пусть

– количество программ, преобразующих исходное число в число . Это число равно сумме

для всех , из которых можно одной командой получить . Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число, – пустая)

(траектория вычислений не должна содержать число )

(слагаемое

встречается дважды, потому что можно получить из двумя способами: умножением на и прибавлением )

(траектория вычислений не должна содержать число )

Ответ: 26

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 4 тыс. раз. С ним справились 51% пользователей.

10. Задание#T4860

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

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

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

Первая команда увеличивает число на экране на , вторая умножает его на , третья увеличивает на .

Программа для исполнителя РазДваТри – это последовательность команд.

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

Показать разбор и ответ

Указание:

Рассмотрите отдельно переход от до и от до .

Решение:

Пусть

– количество программ, преобразующих число в число . Это число равно сумме

для всех , из которых можно одной командой получить . Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число – пустая)

(слагаемое

встречается дважды, потому что можно получить из двумя способами: умножением на и прибавлением )

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

Всего получается программы перехода от к и программы перехода от к . Любую из первых программ можно совместить с любой из вторых, всего получается

программ.

Ответ: 96

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 4 тыс. раз. С ним справились 48% пользователей.

11. Задание#T4833

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

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

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

Первая команда увеличивает число на экране на , вторая умножает его на , третья увеличивает на .

Программа для исполнителя РазДваТри – это последовательность команд.

Показать разбор и ответ

Указание:

Рассмотрите отдельно переход от до и от до .

Решение:

Пусть

– количество программ, преобразующих число в число . Это число равно сумме

для всех , из которых можно одной командой получить . Будем находить значения

последовательно для всех от до :

(единственная программа, сохраняющая исходное число – пустая)

(слагаемое

встречается дважды, потому что можно получить из двумя способами: умножением на и прибавлением )

Всего получается программ перехода от к и программы перехода от к . Любую из первых программ можно совместить с любой из вторых, всего получается

программа.

Ответ: 81

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 5 тыс. раз. С ним справились 44% пользователей.

12. Задание#T2337

Для некоторого исполнителя, преобразующего число на экране, определены три команды:

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

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

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

, кратные ?

Показать ответ

Это задание составил Дмитрий Богданов специально для Яндекса

Это задание решали 4 тыс. раз. С ним справились 38% пользователей.

13. Задание#T801

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

Прибавить
Умножить на
Прибавить

Первая из них увеличивает число на экране на , вторая умножает его на , третья увеличивает его на .

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

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

Примечание. Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Пример. Для программы

при исходном числе траектория будет состоять из чисел

Показать разбор и ответ

Для решения задачи воспользуемся методом динамического программирования. Выпишем в ряд все числа от до , записывая над каждым количество программ, с помощью которых это число может быть получено:

В частности, количество способов получить число указанными командами равно нулю. Но, например, число могло быть получено командой «прибавить » из числа , командой «умножить на » из числа и командой «прибавить » из числа . При этом число до этого могло было быть получено двумя способами, число — также двумя способами, а число — одним способом, следовательно, общее количество способов получить число равно

Произведём аналогичные действия для чисел от до :

Каждой из десяти траекторий, по которой из числа может быть получено число , подходит любая из десяти траекторий, по которой из числа может быть получено число . По правилу произведения комбинаторики получим ответ

Ответ: 100

Это задание взято из демовариантов ФИПИ 2018-2020

Это задание решали 8 тыс. раз. С ним справились 39% пользователей.

0 баллов сегодня

дней без пропуска

сб

вс

пн

вт

ср

чт

пт