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

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

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

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

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

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

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

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

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

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

$2\rightarrow14\rightarrow30$.

Посчитаем количество программ от $2$ до $14$ и от $14$ до $30$. Число $25$ запрещаем.

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

print(f(2, 14) * f(14, 30))

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

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

$2\rightarrow14$: $13$,
$14\rightarrow30$: $2$.
$13\cdot2=26$.

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

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

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