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

13. Анализ хода исполнения алгоритма: Сколько существует таких программ, которые преобразуют…

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

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

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

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

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

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

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

Так как все команды только увеличивают число, траектория, содержащая числа $8$ и $10$, разбивается на три части:

$2\rightarrow8\rightarrow10\rightarrow12$.

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

def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0
    return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)

print(f(2, 8) * f(8, 10) * f(10, 12))

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

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

$2\rightarrow8$: $15$,
$8\rightarrow10$: $2$,
$10\rightarrow12$: $2$.
$15\cdot2\cdot2=60$.

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

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

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