Бит чётности —Каталог задач по ЕГЭ - Информатика

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

Задача 1#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

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

Задача 2#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

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

Задача 3#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

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

Задача 4#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

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

Задача 5#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

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

Задача 6#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

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

Задача 7#30265

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

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

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

а) если число чётное, то к двоичной записи числа в конце дописывается $11$

б) если число нечётное, то к двоичной записи числа в конце дописывается $01$

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

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

Рассмотрим первое число $= 127$ . Переведем в двоичную сс и получим $11111112$ . Отрубим две последние цифры и получим число нечетное, а значит должно было добавиться $01$ . Значит не подходит.

Похоже это число мы сразу можем угадать. У нас есть $11111 2$ и к нему должно добавить $01 2$ . Получаем число $11111012 = 125$ . (Число $126$ также не подходит т.к. $= 11111102$ )

Решение №2

ans = 0
for i in range(1000):
    s = bin(i)[2::]
    if i % 2 == 0:
        s += ’11’
    else:
        s += ’01’
    if int(s, 2) < 128:
        ans = max(ans, int(s, 2))
print(ans)

Ответ: 125

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

Задача 8#27987

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

Строится двоичная запись числа $N$ .
К этой записи дописываются ещё два разряда по следующему правилу:
1. складываются все цифры двоичной записи, и остаток от деления этой суммы на $2$ дописывается в конец числа (справа).
2. над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на $2$ .

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

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

ans = 0
for i in range(1, 1000):
    s = bin(i)[2:]
    s += str(s.count(’1’) % 2)
    s += str(s.count(’1’) % 2)
    if int(s, 2) < 77 and int(s, 2) > ans:
        ans = int(s, 2)
print(ans)

Ответ: 72

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

Задача 9#27672

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

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

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

а) если число чётное, то к двоичной записи числа в конце дописывается $11$

б) если число нечётное, то к двоичной записи числа в конце дописывается $01$

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

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

Решение №1

Рассмотрим первое максимально возможное число $R$ , меньшее $128$ , а именно $127$ . Переведем в двоичную систему счисления и получим $1111111 2$ . Уберём две последние цифры и получим нечетное число, а значит к исходному числу $N$ должно было добавиться $01$ . Значит, число $R = 127$ не могло получиться в результате работы алгоритма.

Теперь мы сразу можем угадать число $R$ . У нас есть $111112$ , и к нему нужно добавить $012$ . Получаем число $11111012 = 125$ .

Решение №2

ans = 0
for i in range(1000):
    s = bin(i)[2::]
    if i % 2 == 0:
        s += ’11’
    else:
        s += ’01’
    if int(s, 2) < 128:
        ans = max(ans, int(s, 2))
print(ans)

Ответ: 125

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

Задача 10#25978

На вход алгоритма подаётся натуральное число $N$ . Алгоритм строит по нему новое число $R$ следующим образом.
1) Строится двоичная запись числа $N$ .
2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на $2$ дописывается в конец числа (справа). Например, запись $11100$ преобразуется в запись $111001$ ;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на $2$ .

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

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

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

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

Ответ: 106

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

Задача 11#25603

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

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

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

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

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

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

for n in range(1, 10000):
    r = bin(n)[2:]
    r = r + str(r.count(’1’) % 2)
    r = r + str(r.count(’1’) % 2)
    r = int(r, 2)
    if r > 150:
        print(r)
        break

Ответ: 154

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

Задача 12#25090

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

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

2. К этой записи дописывается единица.

3. Затем справа дописывается бит чётности: $0$ , если в двоичном коде полученного числа чётное число единиц, и $1$ , если нечётное.

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

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

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

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

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

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

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

Подойдет ли число $16910 = 101010012$ ? Нет, оно кончается на 001.

Подойдет ли число $170 = 10101010 10 2$ ? Нет, оно кончается на 010.

Подойдет ли число $17110 = 101010112$ ? Нет, оно кончается на 011.

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

Ответ: 172

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

Задача 13#24406

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

Строится двоичная запись числа $N$ .
К этой записи дописываются ещё два разряда по следующему правилу:
1. cкладываются все цифры двоичной записи числа $N$ , и остаток от деления суммы на $2$ дописывается в конец числа (справа). Например, запись числа $11100$ преобразуется в запись $111001$ ;
2. над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на $2$ .

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

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

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

Аналитическое решение:
Заметим, что если число единиц в двоичной записи нечётное, то в первый раз допишется единица, а затем число единиц станет чётным, и во второй раз мы допишем ноль. Если же число единиц в двоичной записи чётное, то в первый раз мы допишем ноль, затем количество единиц не изменится, и мы снова допишем ноль. Таким образом, в любом случае последняя цифра числа — ноль. Напишем программу:

for i in range(1, 100):
    s = bin(i)[2::]
    a = 0
    for j in range(len(s)):
        a += int(s[j])
    if a % 2 == 0:
        s += ’00’
    else:
        s += ’10’
    if int(s, 2) > 43:
        print(int(s, 2))
        break

Ответ: 46