№5 ЕГЭ по информатике?

Question

[SSSXXX]

Пытался решить задачу, но выдает ошибку при переводе в 10-ичную сс. Помогите, пожалуйста, решить задачу.

Автомат обрабатывает десятичное натуральное число N по следующему алгоритму:
1) Строится двоичная запись числа N.
2) К полученному числу справа дописывается 0, если в числе единиц больше, чем нулей; иначе дописывается 1.
3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное.
4) Результат переводится в десятичную систему.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 11 = 10112
2) Единиц больше, чем нулей, новая запись 101102.
3) Длина начётная, удаляем три средних разряда, новая запись 102.
4) Десятичное значение полученного числа 2.
Сколько различных значений может получиться на отрезке [50; 100] в результате работы автомата?

cnt = 0
for n in range(1, 1000):
    s = bin(n)[2:]
    if s.count('1') > s.count('0'):
        s += '0'
    else:
        s+= '1'
    m = len(s) // 2 ## округляется по меньшему числу
    if len(s) % 2 == 0:
        s = s[:m-1] + s[m+1:]
    else:
        s = s[:m-1] + s[m+2:]
    r = int(s, 2)
    if 50 <= r <= 100:
        cnt += 1
print(cnt)

Ошибка

Traceback (most recent call last):
line 13, in <module>
    r = int(s, 2)
ValueError: invalid literal for int() with base 2: ''

Comments

[Модератор]

Скриншот фрагмента кода удалён модератором.
Фрагменты кода надо размещать в виде текста и оборачивать тэгом code для корректного отображения. Удобно делать кнопкой </>
Это обязательно, см.п.3.8 Регламента.
Сюда же относится traceback, ввод и вывод в консоли и другая структурированная текстовая инфа.

[Модератор]

Не надо ставить как можно больше тэгов. Лучше оставить один, но конкретный, с которым проблема.
См.п.3.1 Регламента. Также обратите внимание на п.3.6

[Алан Гибизов]

Рекомендую добавить в текст вопроса сообщение об ошибке (полностью, обернуть тэгом code и спрятать под спойлер.

[Lynn «Кофеман»]

Хм, я вообще задание прочитал как «применить алгоритм для чисел от 50 до 100 и посчитать количество различных результатов».

[Bright144]

3) Из середины двоичного числа убирается 2 разряда, если количество разрядов получилось четным, и 3 разряда, если нечетное.

Если убрать 2 разряда из '11' остается пустая строка. Твой третий алгоритм чета не стыковывается, по его условии тебе придется по любому убрать минимум 2 разряда.
Тебе придется проверить перед преобразование бинарного число str в 10-ный. Проблема в этом:

cnt = 0
for n in range(1, 1000):
    s = bin(n)[2:]
    if s.count('1') > s.count('0'):
        s += '0'
    else:
        s+= '1'
    m = len(s) // 2 ## округляется по меньшему числу
    if len(s) % 2 == 0:
        s = s[:m-1] + s[m+1:]
    else:
        s = s[:m-1] + s[m+2:]
    if s:
        r = int(s, 2) #здесь сработает исключение из-за пустого строки
    else:
        r = 0 #не знаю правильно ли это
    if 50 <= r <= 100:
        cnt += 1
print(cnt)

Ты либо не правильно описываешь алгоритм или тебе объяснили задачу не полностью. Потому что в алгоритме должен быть какой-то предусмотрение для таких случи.

[kisaa]

Bright144, потому что, как верно уже заметили выше, гонять этот алгоритм надо не на отрезке 1..1000, а на 50..100, тогда и не будет двоичных значений короче 6 символов.

[Bright144]

kisaa, У него результат должен быть в диапазоне 50-100. Если я правильно понял.

[kisaa]

Bright144, на каких входных данных? Неограниченных? Тогда и выходной список будет неограниченный, верно? А я так понял, что входные данные - [50..100], а результат - одно число. Кстати, в программе ТС-а полностью игнорируется пункт "различных значений".
А [1..1000] вообще с потолка взяты.

[Bright144]

kisaa, не знаю, в коде у него счетчик считывает результаты который находится в диапазоне 50-100 . Я уже решил его. Только при -1 и 0 сработает исключение ValueError: negative shift count. Остальными числами работает отлично.

[Lynn «Кофеман»]

Bright144, Даже если нам нужны значения на отрезке 50-100, то перебирать надо числа от 64 до 255.

[Bright144]

Lynn «Кофеман»,

от 64 до 255

Почему от 64 до 255?

[Lynn «Кофеман»]

Bright144,
потому что у чисел < 64 длина 6 бит. Добавляем 1 и убираем 3 получается 4 бита, что максимум 15.
Числа > 255 имеют 9 бит, добавляем 1 убираем 2 получаем 8 бит, минимум 128.

[Bright144]

Lynn «Кофеман», да точно. Автор чета не договаривает. Задал вопрос и сам исчез.

Answer 1

[Bright144]

Вот решение:

cnt = 0
for n in range(1, 1000):
    n = n << 1 ^ (n.bit_count() > n.bit_length() - n.bit_count()) #добавляем в конец 1 или 0
    bit_l = n.bit_length()              #длина битов
    del_bit_l = 2 + bit_l%2               #длина удаляемого бита
    l_r = int((bit_l - del_bit_l)/2)    #длина левого и правого бита
    l_bit = n >> bit_l - l_r << l_r     #левый бит
    r_bit = n&2**l_r - 1                   #правый бит
    r = l_bit|r_bit
    if 50 <= r <= 100:
        cnt += 1
print(cnt)

Тут главное n не должен быт 0 или -1. Но это тоже можно решать поставив условие. В r получаешь выходной данный который описал в алгоритме.

Comments

[Bright144]

def automat(n):
    n = n << 1 ^ (n.bit_count() > n.bit_length() - n.bit_count())
    bit_l = n.bit_length()              #длина битов
    del_bit_l = 2 + bit_l%2             #длина удаляемого бита
    l_r = int((bit_l - del_bit_l)/2)    #длина левого и правого бита
    l_bit = n >> bit_l - l_r << l_r     #левый бит
    r_bit = n & 2**l_r - 1              #правый бит
    return l_bit | r_bit


cnt = 0
for n in range(1, 1000):
    if 50 <= automat(n) <= 100:
        cnt += 1
print(cnt)