23.08 Прочие прототипы
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует двоичное число на экране. У исполнителя есть две команды:
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])
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
