Ошибка.
Попробуйте повторить позже
На вход алгоритма подаётся натуральное число . Алгоритм строит по нему новое число следующим образом.
1. Строится двоичная запись числа .
2. К этой записи дописывается единица.
3. Затем справа дописывается бит чётности: , если в двоичном коде полученного числа чётное число единиц, и , если нечётное.
4. К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа ) является двоичной записью искомого числа . Какое минимальное число , большее , может быть получено в результате работы автомата?
for n in range(1, 100): s = bin(n)[2:] # перевод в двоичную систему s = str(s) s += ’1’ if s.count(’1’) % 2 == 0: s += ’0’ else: s += ’1’ if s.count(’1’) % 2 == 0: s += ’0’ else: s += ’1’ r = int(s, 2) # перевод в десятичную систему if r > 168: print(r) break
Аналитическое решение:
Имеется число . В любом случае к нему дописывается единица, поэтому будем рассуждать, будто бы число и было таким(с дописанной единицей) изначально. Если количество единиц чётно, то и сумма цифр числа чётна, а значит к числу допишется ноль. Если же количество единиц нечётно, то и сумма цифр числа нечётна, а значит к числу допишется единица. Если мы дописали единичку, то количество единиц увеличится на 1, а значит, что после этого сумма будет чётна, и уже в следующем пункте мы допишем нолик. Если мы дописали ноль, то сумма числа не меняется, а значит в следующем пункте мы также допишем нолик. Значит число в 2 СС заканчивается на 100 или 110 (учли, что мы изначально при любых обстоятельствах дописываем единицу, а потом 00 или 10).
Нам необходимо найти число, большее, чем 168, которое в 2 СС заканчивается на 100 или 110. Будем перебирать с минимального.
Подойдет ли число ? Нет, оно кончается на 001.
Подойдет ли число ? Нет, оно кончается на 010.
Подойдет ли число ? Нет, оно кончается на 011.
Подойдет ли число ? Да, так как оно заканчивается на 100. Значит это и есть наш ответ.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!