Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

13. Анализ хода исполнения алгоритма: Вычесть 1, Вычесть 2, Найти целую часть от деления на 3

Задание #295584
Решено верно
Решено неверно
Сообщить о проблеме

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

A. Вычесть $1$
B. Вычесть $2$
C. Найти целую часть от деления на $3$

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

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

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

Так как все команды уменьшают число, будем считать количество программ, переводящих число $19$ в число $3$. Числа $9$ и $16$ запрещаем.

def f(x, y):
    if x == y:
        return 1
    if x < y or x == 9 or x == 16:
        return 0
    return f(x - 1, y) + f(x - 2, y) + f(x // 3, y)

print(f(19, 3))

Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $9$ или $16$, такая траектория не подходит. Если значение стало меньше $y$, прийти обратно к $y$ уже невозможно.

Программа выведет: $180$.

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение