23.08 Прочие прототипы

Решение рекурсией

Мы используем рекурсию для подсчёта всех возможных программ. Идея заключается в том, что мы создаём функцию f(st, fn), где st — текущее двоичное число в виде строки, fn — целевое число в двоичной системе.

1. Проверяем, достигли ли мы цели:

- Если st == fn, значит последовательность команд привела к целевому числу, возвращаем 1.

2. Проверяем невозможные ситуации:

- Если длина строки st больше длины целевого числа fn, дальнейшие команды не могут привести к цели, возвращаем 0.

3. Иначе считаем два возможных хода:

- Первый ход: приписать 1 справа, формируем новую строку st + "1" и рекурсивно вызываем функцию.

- Второй ход: определяем бит четности (количество нулей в st по модулю 2).

      - Если количество нулей чётное, приписываем 0 справа и рекурсивно вызываем функцию для st + "0".

      - Если количество нулей нечётное, приписываем 1 слева и рекурсивно вызываем функцию для "1"+ st.

4. Складываем результаты обоих ходов, чтобы получить общее количество программ, которые переводят st в fn.

# Определяем рекурсивную функцию f(st, fn)
def f(st, fn):
    # Если текущее число совпало с целевым, возвращаем 1
    if st == fn:
        return 1
    # Если длина текущей строки больше длины целевого числа, путь невозможен
    if len(st) > len(fn):
        return 0
    # Считаем путь, где мы приписываем 1 справа
    x = f(st + "1", fn)
    # Считаем путь с использованием команды "бит четности"
    if st.count("0") % 2 == 0:
        # Если количество нулей чётное, приписываем 0 справа
        y = f(st + "0", fn)
    else:
        # Если количество нулей нечётное, приписываем 1 слева
        y = f("1" + st, fn)
    # Складываем оба возможных пути
    return x + y

# Запускаем функцию от "1" до "1011111" (95 в двоичной)
print(f("1", "1011111"))

—

Решение динамикой

Мы используем динамику, чтобы последовательно подсчитать количество программ для каждого числа от 1 до 95.

1. Сначала создаём функцию to_bin(n), которая переводит число из десятичной системы в двоичную:

- Инициализируем пустую строку a.

- Пока число :

      - Берём остаток от деления на 2 и добавляем его слева к строке a.

      - Делим на 2 целочисленно.

- Возвращаем строку a, которая является двоичным представлением числа.

2. Создаём массив a размером 96 (для чисел от 0 до 95), изначально заполненный нулями.

3. Устанавливаем a[1] = 1, так как стартуем с числа 1, существует один способ быть в этом состоянии.

4. Для каждого числа i от 1 до 94:

- Переводим его в двоичное представление cur_num = to_bin(i).

- Применяем первую команду: приписываем 1 справа, получаем новое число new_num = int(cur_num + "1base=2).

- Если new_num < 96, увеличиваем a[new_num] на количество программ для i.

- Определяем бит четности chet_bit = cur_num.count("0") % 2.

      - Если chet_bit == 1, приписываем 1 слева, иначе приписываем 0 справа.

      - Получаем новое число new_num и, если оно меньше 96, увеличиваем a[new_num] на количество программ для i.

5. В ячейке a[95] хранится общее количество программ, которые переводят число 1 в 95.

# Функция для перевода десятичного числа в двоичное
def to_bin(n):
    a = ""
    while n > 0:
        a = str(n % 2) + a
        n //= 2
    return a

# Массив для хранения количества программ для каждого числа
a = [0] * 96
# Начальное число 1, один способ
a[1] = 1

# Перебираем все числа от 1 до 94
for i in range(1, 95):
    # Переводим число i в двоичное представление
    cur_num = to_bin(i)
    # Применяем команду "приписать 1 справа"
    new_num = int(cur_num + "1", base=2)
    if new_num < 96:
        a[new_num] += a[i]
    # Определяем бит четности
    chet_bit = cur_num.count("0") % 2
    if chet_bit:
        # Если бит нечётный, приписываем 1 слева
        new_num = int("1" + cur_num, base=2)
    else:
        # Если бит чётный, приписываем 0 справа
        new_num = int(cur_num + "0", base=2)
    if new_num < 96:
        a[new_num] += a[i]

# Выводим количество программ, которые переводят 1 в 95
print(a[95])