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

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

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

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

A. Прибавь $1$
B. Поменяй местами

Первая из этих команд увеличивает число на экране на $1$. Вторая команда применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в разряде единиц, и действует, заменяя число на экране числом, в котором цифры двух младших разрядов поменялись местами.

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

Сколько существует программ, для которых при исходном числе $100$ результатом является число $141$?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе $13$ траектория состоит из чисел $14$, $41$, $42$.

Для решения используем рекурсивную функцию. Команда A переводит число $x$ в $x+1$.

Для команды B найдём цифру десятков $a$ и цифру единиц $b$. Если $a<b$, меняем эти цифры местами.

def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0

    k = f(x + 1, y)

    a = x // 10 % 10
    b = x % 10

    if a < b:
        z = x - 10 * a - b + 10 * b + a
        k += f(z, y)

    return k

print(f(100, 141))

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

Переменная $a$ — цифра десятков, $b$ — цифра единиц. Если $a<b$, команда B разрешена. Число $z$ получается перестановкой двух последних цифр числа $x$.

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

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

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