Исполнитель Щелчок преобразует двоичное число на экране. У исполнителя есть две команды:
1. Приписать 1 справа (1 
11)
2. Приписать бит четности справа, если это 0, слева, если это 1 (бит четности — количество нулей в числе по модулю 2, 10 
110, 100 
1000)
Программа для исполнителя — это последовательность команд.
Сколько существует различных программ, которые переводят 1 в 95 в двоичной системе счисления.
Решение 1 (Рекурсия)
def f(st, fn):
if st == fn:
return 1
if len(st) > len(fn):
return 0
x = f(st + "1", fn)
if st.count("0") % 2 == 0:
y = f(st + "0", fn)
else:
y = f("1" + st, fn)
return x + y
print(f("1", "1011111"))
Решение 2 (Динамика)
def to_bin(n): # перевод из десятичной СС в двоичную
a = ""
while n > 0:
a = str(n % 2) + a
n //= 2
return a
# Если s="1010", то команда n=int(s, base=2) переводит число 1010
# из 2-й СС в 10-ю СС
a = [0] * 96
a[1] = 1
for i in range(1, 95):
cur_num = to_bin(i)
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:
new_num = int("1" + cur_num, base=2)
else:
new_num = int(cur_num + "0", base=2)
if new_num < 96:
a[new_num] += a[i]
print(a[95])