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

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

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

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

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

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

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

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

Так как все команды только уменьшают число, любая траектория, содержащая $13$, разбивается на две части: $19\rightarrow13\rightarrow2$.

Посчитаем количество программ от $19$ до $13$ и от $13$ до $2$. Число $7$ запрещаем.

def f(x, y):
    if x == y:
        return 1
    if x < y or x == 7:
        return 0
    return f(x - 1, y) + f(x - 4, y) + f(x // 3, y)

print(f(19, 13) * f(13, 2))

Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $7$, такая траектория не подходит.

Количество путей:

$19\rightarrow13$: $4$,
$13\rightarrow2$: $17$.
$4\cdot17=68$.

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

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

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