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

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

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

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

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

Первая из них уменьшает число на экране на $1$, вторая заменяет число на экране на целую часть от деления числа на $2$.

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

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

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

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

Посчитаем количество программ от $30$ до $10$ и от $10$ до $1$.

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

print(f(30, 10) * f(10, 1))

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

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

$30\rightarrow10$: $12$,
$10\rightarrow1$: $30$.
$12\cdot30=360$.

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

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

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