Тема 23. Оператор присваивания и ветвления

23.04 Количество программ из A в B где траектория вычислений НЕ содержит число(-а)

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела оператор присваивания и ветвления
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#6068

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

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

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

2. умножить на 2,

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

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

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

Показать ответ и решение

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

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

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

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

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

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

|1-|2-|3-|4-|5-|-6--|7--|8--|
|--|--|--|--|--|----|---|---|
-1--2--3--5--5--10---10--15--
Так как по условию сказано, что траектория не должна содержать число 9, значит R (9) = 0  . Продолжим заполнять таблицу:

|--|--|--|--|--|----|---|---|--|---|---|----|---|---|---|----|---|---|---|---|----|---|---|
|1-|2-|3-|4-|5-|-6--|7--|8--|9-|10-|11-|-12-|13-|14-|15-|16--|17-|18-|19-|20-|21--|22-|23-|
-1--2--3--5--5--10---10--15--0---5---5---20--20--30--35--50---50--60--60--70--80---85--85--
Аналогично R (24) = 0  . Продолжим заполнять таблицу:

|---|---|----|---|---|---|----|---|---|
|23-|24-|25--|26-|27-|28-|29--|30-|31-|
-85---0---0---20--20--50--50---90--90--
Аналогично R (32) = 0  . Заполним таблицу до конца:

|----|---|---|---|----|----|----|-----|
|31--|32-|33-|34-|35--|36--|37--|-38--|
|90  |0  |5  |55 |55  |135 |135 |195  |
--------------------------------------
Отсюда получем ответ — 195
Ответ: 195

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!