Двоичная запись числа —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#56306

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

Строится двоичная запись числа N.
К этой записи дописываются ещё несколько разрядов по следующему правилу: если N чётное, то к нему справа дописывается $01$ , если N нечетное – слева дописывается $11$ и справа $0$ ;
Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = $13$ . Алгоритм работает следующим образом:

Двоичная запись числа N: $1101$ .
Число нечетное, следовательно слева дописываем $11$ , справа $0$ $→$ $1111010$ .
На экран выводится число $122$ .

В результате работы автомата на экране появилось число, большее $1021$ . Для какого наименьшего значения N данная ситуация возможна?

Показать ответ и решение

for i in range(1, 10000):
    if i % 2 == 0:
        i1 = bin(i)[2:] + ’01’
    else:
        i1 = ’11’ + bin(i)[2:] + ’0’
    if int(i1, 2) > 1021:
        print(i)
        break

Ответ: 127

Ошибка.
Попробуйте повторить позже

Задача 2#33499

На вход алгоритма подаётся натуральное число $N > 1$ . Алгоритм строит по нему новое число $R$ следующим образом.

1) Строится двоичная запись числа $N$ .

2) Эта запись изменяется по следующим правилам:

Если сумма цифр в двоичной записи числа четная, то справа дописывается $0$ , а первые два левых разряда заменяются на $10$ ;

Если сумма цифр в двоичной записи числа нечетная, то справа дописывается $1$ , а первые два левых разряда заменяются на $11$ ;

Например, запись $11100$ преобразуется в $111001$ .

Полученная таким образом запись (в ней на один разряд больше, чем в записи исходного числа $N$ ) является двоичной записью искомого числа $R$ .

Укажите максимальное число $N$ , для которого результат работы алгоритма меньше $24$ . В ответе это число запишите в десятичной системе.

Показать ответ и решение

for i in range(2, 24):
    x = bin(i)[2:]
    if x.count("1") % 2 == 0:
        x = "10" + x[2:] + "0"
    else:
        x = "11" + x[2:] + "1"
    if int(x, 2) < 24:
        print(i)

Ответ: 15

Ошибка.
Попробуйте повторить позже

Задача 3#30300

МС получает на вход натуральное число $N > 1$ и строит по нему новое число $R$ следующим образом:

Строится двоичная запись числа $N$ .
Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже.
Шаг $2$ повторяется еще два раза.
Результат переводится в десятичную систему счисления.

При каком наибольшем исходном числе $N < 1024$ в результате работы алгоритма получается нечетное число, которое делится на $7$ ?

Показать ответ и решение

Решение 1

for i in range(1023, 1, -1):
    s = bin(i)[2:] # Внизу отказ от ИВ
    s += s[-1] * (s.count(’0’) == s.count(’1’)) + \
    ’1’ * (s.count(’1’) < s.count(’0’)) + ’0’ * (s.count(’0’) < s.count(’1’))
    s += s[-1] * (s.count(’0’) == s.count(’1’)) + \
    ’1’ * (s.count(’1’) < s.count(’0’)) + ’0’ * (s.count(’0’) < s.count(’1’))
    s += s[-1] * (s.count(’0’) == s.count(’1’)) + \
    ’1’ * (s.count(’1’) < s.count(’0’)) + ’0’ * (s.count(’0’) < s.count(’1’))
    if int(s, 2) % 2 != 0 and int(s, 2) % 7 == 0:
        print(i)
        break

Решение 2

for i in range(1023, 1, -1):
    s = bin(i)[2:]
    for j in range(3):
        k = s.count(’1’) - s.count(’0’)
        if (k < 0):
            s += ’1’
        elif (k > 0):
            s += ’0’
        else:
            s += s[-1]
    if int(s, 2) % 2 != 0 and int(s, 2) % 7 == 0:
        print(i)
        break

Ответ: 914

Ошибка.
Попробуйте повторить позже

Задача 4#30299

Автомат обрабатывает натуральное число N по следующему алгоритму:

1. Строится двоичная запись числа $N$ .

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на $2$ .

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

4. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число $N = 13$ . Алгоритм работает следующим образом:

1. Двоичная запись числа $N : 1101$ .

2. Сумма цифр двоичной записи $3$ , остаток от деления на $2$ равен $1$ , новая запись $11011$ .

3. Сумма цифр полученной записи $4$ , остаток от деления на $2$ равен $0$ , новая запись $110110$ .

4. На экран выводится число $54$ .

Какое наименьшее число, большее вашего балла на ЕГЭ ( $100$ ), может появится на экране в результате работы автомата?

Показать ответ и решение

for i in range(1000000):
    s = bin(i)[2::]
    s += str(s.count(’1’) % 2)
    s += str(s.count(’1’) % 2)
    if int(s, 2) > 100:
        print(int(s, 2))
        break

Аналитическое решение:

Имеется число $N$ . Все числа в двоичной записи складываются и добавляется остаток от деления на 2 этой суммы, то есть цифра 0 или 1, значит если сумма чётна, то дописываем 0, иначе 1. Если мы дописали единичку, то количество единиц увеличится на 1, а значит, что после этого сумма будет чётна, и уже в следующем пункте мы допишем нолик. Если мы дописали ноль, то сумма числа не меняется, а значит в следующем пункте мы также допишем нолик. Значит число в 2 СС заканчивается на 00 или 10.

Нам необходимо найти число, большее, чем 100, которое в 2 СС заканчивается на 00 или 10. Будем перебирать с минимального.

Подойдет ли число $10110 = 11001012$ ? Нет, оно кончается на 01.

Подойдет ли число $10210 = 11001102$ ? Да, так как оно заканчивается на 10. Значит это и есть наш ответ.

Ответ: 102

Ошибка.
Попробуйте повторить позже

Задача 5#30298

Автомат обрабатывает натуральное число $N$ по следующему алгоритму:

Строится двоичная запись числа $N$ .
Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на $2$ .
Предыдущий пункт повторяется для записи с добавленной цифрой.
Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число $N = 13$ . Алгоритм работает следующим образом:

Двоичная запись числа $N : 1101$ .
Сумма цифр двоичной записи $3$ , остаток от деления на $2$ равен $1$ , новая запись $11011$ .
Сумма цифр полученной записи $4$ , остаток от деления на $2$ равен $0$ , новая запись $110110$ .
На экран выводится число $54$ .

Какое наименьшее число, большее $1024$ , может появиться на экране в результате работы автомата??

Показать ответ и решение

for i in range(1000000):
    s = bin(i)[2:]
    s += str(s.count(’1’) % 2)
    s += str(s.count(’1’) % 2)
    if int(s, 2) > 1024:
        print(int(s, 2))
        break

Ответ: 1026

Ошибка.
Попробуйте повторить позже

Задача 6#30297

На вход алгоритма подаётся натуральное число $N$ . Алгоритм строит по нему новое число $R$ следующим образом.

Строится двоичная запись числа $N$ .
Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы цифр на $2$ .
Предыдущий пункт повторяется для записи с добавленной цифрой.
Результат переводится в десятичную систему и выводится на экран.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа $N$ ) является двоичной записью искомого числа $R$ .

Укажите такое наименьшее число $R$ , которое превышает $50$ и может являться результатом работы этого алгоритма. В ответе это число запишите в десятичной системе счисления.

Показать ответ и решение

for i in range(1000000):
    s = bin(i)[2::]
    s += str(s.count(’1’) % 2)
    s += str(s.count(’1’) % 2)
    if int(s, 2) > 50:
        print(int(s, 2))
        break

Ответ: 54

Ошибка.
Попробуйте повторить позже

Задача 7#30296

На вход алгоритма подаётся натуральное число $N$ . Алгоритм строит по нему новое число $R$ следующим образом.

Строится двоичная запись числа $N$ .
Складываются все цифры двоичной записи, и остаток от деления суммы цифр на $2$ дописывается в конец числа (справа). Например, запись $11100$ преобразуется в запись $111001$ ;
Шаг $2$ повторяется еще один раз. Например, запись $111001$ преобразуется в запись $1110010$ ;

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа $N$ ) является двоичной записью искомого числа $R$ .

Укажите минимальное число $R$ , которое превышает $166$ и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Показать ответ и решение

for i in range(1, 1000000):
    s = bin(i)[2:]
    s += str(s.count(’1’) % 2)
    s += str(s.count(’1’) % 2)
    if int(s, 2) > 166:
        print(int(s, 2))
        break

Ответ: 170

Ошибка.
Попробуйте повторить позже

Задача 8#30295

Алгоритм получает на вход натуральное число $N > 1$ и строит по нему новое число $R$ следующим образом:

Строится двоичная запись числа $N$ .
В конец записи (справа) дописывается конъюнкция двух правых крайних цифр двоичной записи числа $N$ .
В конец записи (справа) дописывается конъюнкция двух левых крайних цифр двоичной записи числа $N$ .
Результат переводится в десятичную систему.

Пример. Дано число $N = 23$ . Алгоритм работает следующим образом:

Двоичная запись числа $N : 10111$ .
Конъюнкция двух правых крайних цифр $1$ , новая запись $101111$ .
Конъюнкция двух левых крайних цифр $0$ , новая запись $1011110$ .
Результат работы алгоритма $R = 94$ .

При каком наименьшем числе $N$ в результате работы алгоритма получится $R > 55$ ? В ответе запишите это число в десятичной системе счисления.

Показать ответ и решение

for i in range(2, 10000):
    s = bin(i)[2:]
    s += str(int(s[-2]) & int(s[-1]))
    s += str(int(s[0]) & int(s[1]))
    if int(s, 2) > 55:
        print(i)
        break

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 9#30294

Алгоритм получает на вход натуральное число $N > 1$ и строит по нему новое число $R$ следующим образом:

Строится двоичная запись числа $N$ .
В этой записи последний встречаемый ноль заменяется на первые две цифры полученной записи. Если нуля нет в записи числа, алгоритм аварийно завершается.
Запись записывается справа налево (в обратную сторону).
Результат переводится в десятичную систему счисления.

Для скольких значений $N$ в результате работы алгоритма получится число $255$ ?

Показать ответ и решение

Решение 1

ans = 0
for i in range(2, 10000):
    s = bin(i)[2:]
    if s.count(’0’) > 0:
        ind = ’’
        for j in range(len(s) - 1, -1, -1):
            if s[j] == ’0’:
                ind = j
                break
        x = s[:ind] + s[0] + s[1] + s[ind + 1:]
        x = x[::-1]
        if int(x, 2) == 255:
            ans += 1
print(ans)

Решение 2

ans = 0
for i in range(2, 10000):
    s = bin(i)[2:]
    if s.count(’0’) > 0:
        s = s[::-1].replace(’0’, s[0:2][::-1], 1)
        if int(s, 2) == 255:
            ans += 1
print(ans)

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 10#30293

Автомат обрабатывает натуральное число $N$ $(1 ≤ N ≤ 255)$ по следующему алгоритму:

Строится восьмибитная двоичная запись числа $N$ .
Удаляется последняя цифра двоичной записи.
Запись «переворачивается», то есть читается справа налево.
Полученное число переводится в десятичную запись и выводится на экран.

Каково наименьшее число, меньшее $100$ , которое после обработки автоматом не изменится?

Показать ответ и решение

for i in range(1, 100):
    s = ’0’ * (8 - len(bin(i)[2:])) + bin(i)[2:]
    s = s[:len(s) - 1]
    s = s[::-1]
    if int(s, 2) == i:
        print(i)
        break

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 11#30292

Автомат обрабатывает натуральное число $N < 128$ по следующему алгоритму:

1) Строится восьмибитная двоичная запись числа $N$ .

2) Инвертируются разряды исходного числа (0 заменяется на 1, 1 на 0).

3) К полученному двоичному числу прибавляют единицу.

4) Полученное число переводится в десятичную систему счисления.

Для какого числа N результат работы алгоритма равен 130?

Показать ответ и решение

for i in range(1, 128):
    s = ’0’ * (8 - len(bin(i)[2::])) + bin(i)[2::]
    x = ’’
    for j in range(len(s)):
        if s[j] == ’1’:
            x += ’0’
        else:
            x += ’1’
    if (int(x, 2) + 1) == 130:
        print(i)

Аналитическое решение:

Необходимо найти такое $N$ , что после работы алгоритма мы получим 130. Давайте размотаем алгоритм с конца: в конце алгоритм добавляет единицу, а значит отнимём её и получим число $12910$ . В 2 СС это число выглядит так $100000012$ . Инвертируем биты обратно, получим число $011111102$ , ведущий ноль не отбрасываем, так как алгоритм строил восьмибитную(то есть состояющую из 8 цифр в двоичной СС) запись. Значит изначальное число равнялось $011111102 = 12610$ .

Ответ: 126

Ошибка.
Попробуйте повторить позже

Задача 12#30291

Автомат Алиса-007 обрабатывает натуральное число N по следующему алгоритму:

1) Строится двоичная запись числа N.

2) Запись «переворачивается», то есть читается справа налево. Если при этом появляются ведущие нули, они отбрасываются.

3) Полученное число переводится в десятичную запись и выводится на экран. Какое наименьшее число, превышающее 765, после обработки автоматом даёт результат 23?

Показать ответ и решение

for i in range(766, 10000000):
    s = bin(i)[2::]
    s = str(int(s[::-1]))
    if int(s, 2) == 23:
        print(i)
        break

Ответ: 928

Ошибка.
Попробуйте повторить позже

Задача 13#30290

На вход алгоритма подаётся натуральное число $N$ . Алгоритм строит по нему новое число $R$ следующим образом.

Строится двоичная запись числа $N$ .
К этой записи дописывается (дублируется) последняя цифра.
Затем справа дописывается $0$ , если в двоичном коде числа $N$ чётное число единиц, и $1$ , если нечётное.
К полученному результату справа дописывается $1$ , если количество единиц получившегося числа нечётно, иначе дописывается $0$ .

Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа $N$ ) является двоичной записью искомого числа $R$ . Укажите минимальное число $N$ , после обработки которого автомат получает число, большее $120$ . В ответе это число запишите в десятичной системе.

Показать ответ и решение

for n in range(1, 1000):
    r = bin(n)[2:]
    r += r[-1]
    if bin(n)[2:].count(’1’) % 2 == 0:
        r += ’0’
    else:
        r += ’1’
    if r.count(’1’) % 2 == 0:
        r += ’0’
    else:
        r += ’1’
    if int(r, 2) > 120:
        print(n)
        break

Ответ: 15

Ошибка.
Попробуйте повторить позже

Задача 14#30289

На вход алгоритма подаётся натуральное число $N$ . Алгоритм строит по нему новое число $R$ следующим образом.

Строится двоичная запись числа $N$ .
К этой записи справа дописывается единица.
Затем справа дописывается бит чётности: $0$ , если в двоичном коде полученного числа чётное число единиц, и $1$ , если нечётное.
К полученному результату дописывается ещё один бит чётности.

Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа $N$ ) является двоичной записью искомого числа $R$ . Какое минимальное число $R$ , большее $212$ , может быть получено в результате работы автомата?

Показать ответ и решение

Решение программой:

for i in range(1, 1000000):
    s = bin(i)[2::]
    s += ’1’
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    # второй if не нужен, потому что всегда будет дописываться 0
    # подумайте почему)
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    if int(s, 2) > 212:
        print(int(s, 2))
        break

Аналитическое решение:

Каким бы не было число, на втором шаге к нему всегда дописывается единица, так что давайте называть это число «изначальным».

Если изначальное число $N$ имеет чётное количество единиц, то после добавления нуля количество единиц не изменится, а потому на следующем шаге также добавится ноль. Итого к числу допишут два нуля.

Если изначально число $N$ имеет нечётное количество единиц, то после добавления единицы количество единиц увеличится на $1$ , что означает, что количество единиц станет чётным числом, а значит на следующем шаге уже будут добавлять ноль. Итого к числу допишут единицу и ноль.

Значит мы будем проверять только числа, которые кончаются на $100$ или $110$ .

Могло ли получиться число $213$ ? Нет, в двоичной СС оно выглядит как $110101012$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $214$ ? В двоичной СС оно выглядит как $11010110 2$ . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число $110102$ , добавим к нему единицу и получим число $1101012$ , у него чётное число единиц, а значит после работы алгоритма к нему дописали бы два нуля, но мы откинули $110$ , а значит это не то число, которое нам нужно.

Могло ли получиться число $215$ ? Нет, в двоичной СС оно выглядит как $110101112$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $216$ ? Нет, в двоичной СС оно выглядит как $110110002$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $217$ ? Нет, в двоичной СС оно выглядит как $110110012$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $218$ ? Нет, в двоичной СС оно выглядит как $110110102$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $219$ ? Нет, в двоичной СС оно выглядит как $110110112$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $220$ ? В двоичной СС оно выглядит как $110111002$ . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число $110112$ , добавим к нему единицу и получим число $1101112$ , у него нечётное число единиц, а значит после работы алгоритма к нему дописали бы единицу и ноль, но мы откинули $100$ , а значит это не то число, которое нам нужно.

Могло ли получиться число $221$ ? Нет, в двоичной СС оно выглядит как $110111012$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $222$ ? В двоичной СС оно выглядит как $110111102$ . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число $110112$ , добавим к нему единицу и получим число $1101112$ , у него нечётное число единиц, а значит после работы алгоритма к нему дописали бы единицу и ноль, а мы откинули как раз $110$ , значит $222$ – это интересующее нас число.

Ответ: 222

Ошибка.
Попробуйте повторить позже

Задача 15#30278

Автомат обрабатывает натуральное число $N$ по следующему алгоритму:

Строится двоичная запись числа $N$ .
В конец двоичной записи добавляются две цифры: $11$ — если $N$ четное, $00$ — если $N$ нечетное.
Результат переводится в десятичную систему, затем от числа отнимается минимальное количество бит, которым можно закодировать $N$ чисел.
Полученное число выводится на экран.

Пример. Дано число $N = 56.$ Алгоритм работает следующим образом:

Двоичная запись числа $N : 111000.$
В конец добавляются цифры $11$ , так как $1110002 = 5610$ — четное число. Получается $11100011$ .
Результат переводится в десятичную систему. $111000112 = 22710$ . От $227$ отнимается число $6$ , так как это минимальное количество бит, которым можно закодировать $56$ чисел.
На экран выводится 221.

Укажите минимальное $N$ , при котором автомат выведет на экран число $126$ .

Показать ответ и решение

for i in range(10000):
    s = bin(i)[2::]
    if i % 2 == 0:
        s += ’11’
    else:
        s += ’00’
    x = int(s, 2) - len(bin(i-1)[2::])
    # n - натуральные
    # Например, n = 5
    # 000 = 1; 001 = 2; 010 = 3;
    # 011 = 4; 100 = 5
    if x == 126:
        print(i)

Ответ: 32

Ошибка.
Попробуйте повторить позже

Задача 16#30272

На вход алгоритма "КХЪ" подаётся натуральное число $Y.$ Алгоритм строит по нему новое число $X$ следующим образом:

1. Строится двоичная запись числа $Y.$

2. В конец двоичной записи дописываются две первые цифры этой записи в обратном порядке.

3. В начало двоичной записи дописывается единица.

4. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число $Y = 5.$ Алгоритм работает следующим образом:

1. Двоичная запись числа $Y :$ $101$ .

2. В конец записи добавляются цифры $01$ – первые две цифры в обратном порядке (сначала вторая, затем первая), получается $10101$ .

3. В начало записи добавляется цифра $1$ , получается $110101$ .

4. На экран выводится число $53$ .

Полученная таким образом запись является искомым числом $X.$ Укажите минимальное число $X,$ которое превышает число $50$ и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Показать ответ и решение

for i in range(3, 1000):
    s = bin(i)[2::]
    s += s[1] + s[0]
    s = ’1’ + s
    if int(s, 2) > 50:
        print(int(s, 2))
        break

Ответ: 53

Ошибка.
Попробуйте повторить позже

Задача 17#30271

Алгоритм получает на вход натуральное число $N > 1$ и строит по нему новое число R следующим образом.

1) Число N переводим в двоичную запись.

2) К этой записи справа дописывается один разряд по следующему правилу: если количество единиц в двоичной записи числа больше количества нулей, то справа дописывается единица, иначе дописывается 0.

3) К полученной записи повторно применяется алгоритм из п.2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите наибольшее число R, меньшее 99, которое может быть получено в результате работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Показать ответ и решение

for i in range(1, 1000):
    s = bin(i)[2::]
    if s.count(’1’) > s.count(’0’):
        s += ’1’
    else:
        s += ’0’
    if s.count(’1’) > s.count(’0’):
        s += ’1’
    else:
        s += ’0’
    if int(s, 2) < 99:
        print(int(s, 2))

Аналитическое решение:

Заметим, что алгоритм добавляет ту цифру, которых больше у числа (если количество равно, то добавляется нуль). Если у числа $N$ было какое-то количество нулей и какое-то количество единиц, то добавляя какую-то цифру, их количество только увеличивается, а значит и на следующем шаге добавят эту же цифру. Значит к числу добавят $11$ или $00$ .

Нам нужно найти наибольшее число $R$ , которое могли получить после работы данного алгоритма. Могло ли получиться число $98 = 1100010 10 2$ ? Нет, так как оно кончается на 10, а мы знаем, что такое число не могло получиться после этого алгоритма.

Могло ли получиться число $9710 = 11000012$ ? Нет, так как оно кончается на 01, а мы знаем, что такое число не могло получиться после этого алгоритма.

Могло ли получиться число $9610 = 11000002$ ? Такое число могло получиться после этого алгоритма, но давайте проверим какое число тогда было бы без добавленных нулей – если уберём два нуля, то получим число $110002$ , количество нулей больше, чем количество единиц, а значит к такому числу после работы алгоритма действительно добавляются два нуля, а значит 96 это наибольшее $R$ , которое могли получить после работы алгоритма.

Ответ: 96

Ошибка.
Попробуйте повторить позже

Задача 18#30270

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1)Строится двоичная запись числа N.

2)К этой записи дописываются справа ещё два разряда по следующему правилу:

а)Дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное;

б)К полученному результату дописывается ещё один бит чётности

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 78. В ответе это число запишите в десятичной системе.

Показать ответ и решение

for i in range(1, 1000):
    s = bin(i)[2::]
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    if int(s, 2) > 78:
        print(i)
        break

Аналитическое решение:

Если изначальное число $N$ имеет чётное количество единиц, то после добавления нуля количество единиц не изменится, а потому на следующем шаге также добавится ноль. Итого к числу допишут два нуля.

Если изначально число $N$ имеет нечётное количество единиц, то после добавления единицы количество единиц увеличится на 1, что означает, что количество единиц станет чётным числом, а значит на следующем шаге уже будут добавлять ноль. Итого к числу допишут единицу и ноль.

Значит мы будем проверять только числа, которые кончаются на $00$ или $10$ .

Могло ли получиться число $79$ ? Нет, в двоичной СС оно выглядит как $10011112$ , а значит получиться после алгоритма не могло.

Могло ли получиться число 80? В двоичной СС оно выглядит как $10100002$ . Так что вполне возможно. Если откинем последние две цифры, то у нас останется число $101002$ , у него чётное число единиц, а значит после работы алгоритма к нему дописали бы два нуля, но это как раз те самые цифры, которые мы откинули, значит $101002 = 2010$ и есть искомое число.

Ответ: 20

Ошибка.
Попробуйте повторить позже

Задача 19#30269

Алгоритм получает на вход натуральное число $N > 1$ и строит по нему новое число $R$ следующим образом:

Строится двоичная запись числа $N$ .
В конец записи (справа) дописывается вторая слева цифра двоичной записи.
В конец записи (справа) дописывается вторая справа цифра двоичной записи числа $N$ .
Результат переводится в десятичную систему.

Пример. Дано число $N = 18$ . Алгоритм работает следующим образом:

Двоичная запись числа $N : 10010$ .
Вторая слева цифра $0$ , новая запись $100100$ .
Вторая справа цифра $1$ , новая запись $1001001$ .
Результат работы алгоритма $R = 73$ .

При каком наибольшем числе $N$ в результате работы алгоритма получится $R < 90$ ? В ответе запишите это число в десятичной системе счисления.

Показать ответ и решение

ans = 0
for i in range(2, 1000):
    s = bin(i)[2::]
    x = s
    x += s[1] + s[-2]
    if int(x, 2) < 90:
        ans = i
print(ans)

Ответ: 22

Ошибка.
Попробуйте повторить позже

Задача 20#30268

Алгоритм получает на вход натуральное число $N > 1$ и строит по нему новое число R следующим образом:

1. Строится двоичная запись числа $N$ .

2. Вместо последней (самой правой) двоичной цифры дважды записывается вторая слева цифра двоичной записи.

3. Результат переводится в десятичную систему.

Пример. Дано число $N = 19$ . Алгоритм работает следующим образом:

1. Двоичная запись числа $N : 10011$ .

2. Вторая слева цифра $0$ , единица в конце записи заменяется на два нуля, новая запись $100100$ .

3. Результат работы алгоритма $R = 36$ .

При каком наименьшем числе $N$ в результате работы алгоритма получится $R > 48$ ? В ответе запишите это число в десятичной системе счисления.

Показать ответ и решение

Решение №1

Переведем $49 = 1100012$ . Не совпадают.

Переведем $50 = 110010 2$ . Не совпадают.

Переведем $51 = 1100112$ . Совпали. Обрубим $2$ последние цифры и припишем $0$ . $110002 = 2410$ .

Решение №2

for i in range(6, 1000):
    s = bin(i)[2::]
    s = s[:len(s) - 1]
    s += s[1] * 2
    if int(s, 2) > 48:
        print(i)
        break

Ответ: 24