Сколько единиц в двоичной записи решу егэ

Всего: 47    1–20 | 21–40 | 41–47

Добавить в вариант

Всего: 47    1–20 | 21–40 | 41–47

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Всего: 57    1–20 | 21–40 | 41–57

Добавить в вариант

Всего: 57    1–20 | 21–40 | 41–57

Автор — Лада Борисовна Есакова.

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

Рассмотрим десятичное число 875. Последняя цифра числа (5) – это остаток от деления числа 875 на 10. Последние две цифры образуют число 75 – это остаток от деления числа 875 на 100. Аналогичные утверждения справедливы для любой системы счисления:

Последняя цифра числа – это остаток от деления этого числа на основание системы счисления.

Последние две цифры числа – это остаток от деления числа на основание системы счисления в квадрате.

Например, . Разделим 23 на основание системы 3, получим 7 и 2 в остатке (2 – это последняя цифра числа в троичной системе). Разделим 23 на 9 (основание в квадрате), получим 18 и 5 в остатке (5 = ).

Вернемся опять к привычной десятичной системе. Число = 100000. Т.е. 10 в степени k– это единица и k нулей.

Аналогичное утверждение справедливо для любой системы счисления:

Основание системы счисления в степени k в этой системе счисления записывается как единица и k нулей.

Например, .

1. Поиск основания системы счисления

Пример 1.

В системе счисления с некоторым основанием десятичное число 27 записывается в виде 30. Укажите это основание.

Решение:

Обозначим искомое основание x. Тогда .Т.е. x = 9.

Ответ: 9

Пример 2.

В системе счисления с некоторым основанием десятичное число 13 записывается в виде 111. Укажите это основание.

Решение:

Обозначим искомое основание x. Тогда

Решаем квадратное уравнение, получаем корни 3 и -4. Поскольку основание системы счисления не может быть отрицательным, ответ 3.

Ответ: 3

Пример 3

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 29 оканчивается на 5.

Решение:

Если в некоторой системе число 29 оканчивается на 5, то уменьшенное на 5 число (29-5=24) оканчивается на 0. Ранее мы уже говорили, что число оканчивается на 0 в том случае, когда оно без остатка делится на основание системы. Т.е. нам нужно найти все такие числа, которые являются делителями числа 24. Эти числа: 2, 3, 4, 6, 8, 12, 24. Заметим, что в системах счисления с основанием 2, 3, 4 нет числа 5 (а в формулировке задачи число 29 оканчивается на 5), значит остаются системы с основаниями: 6, 8, 12,

Ответ: 6, 8, 12, 24

Пример 4

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 71 оканчивается на 13.

Решение:

Если в некоторой системе число оканчивается на 13, то основание этой системы не меньше 4 (иначе там нет цифры 3).

Уменьшенное на 3 число (71-3=68) оканчивается на 10. Т.е. 68 нацело делится на искомое основание системы, а частное от этого при делении на основание системы дает в остатке 0.

Выпишем все целые делители числа 68: 2, 4, 17, 34, 68.

2 не подходит, т.к. основание не меньше 4. Остальные делители проверим:

68:4 = 17; 17:4 = 4 (ост 1) – подходит

68:17 = 4; 4:17 = 0 (ост 4) – не подходит

68:34 = 2; 2:17 = 0 (ост 2) – не подходит

68:68 = 1; 1:68 = 0 (ост 1) – подходит

Ответ: 4, 68

2. Поиск чисел по условиям

Пример 5

Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11?

Решение:

Для начала выясним, как выглядит число 25 в системе счисления с основанием 4.

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

Ответ: 5, 21

3. Решение уравнений

Пример 6

Решите уравнение:

Ответ запишите в троичной системе (основание системы счисления в ответе писать не нужно).

Решение:

Переведем все числа в десятичную систему счисления:

Квадратное уравнение имеет корни -8 и 6. (т.к. основание системы не может быть отрицательным). .

Ответ: 20

4. Подсчет количества единиц (нулей) в двоичной записи значения выражения

Для решения этого типа задач нам нужно вспомнить, как происходит сложение и вычитание «в столбик»:

При сложении происходит поразрядное суммирование записанных друг под другом цифр, начиная с младших разрядов. В случае, если полученная сумма двух цифр больше или равна основанию системы счисления, под суммируемыми цифрами записывается остаток от деления этой суммы на основание системы, а целая часть от деления этой суммы на основание системы прибавляется к сумме следующих разрядов.

При вычитании происходит поразрядное вычитание записанных друг под другом цифр, начиная с младших разрядов. В случае, если первая цифра меньше второй, мы «занимаем» у соседнего (большего) разряда единицу. Занимаемая единица в текущем разряде равна основанию системы счисления. В десятичной системе это 10, в двоичной 2, в троичной 3 и т.д.

Пример 7

Сколько единиц содержится в двоичной записи значения выражения: ?

Решение:

Представим все числа выражения, как степени двойки:

В двоичной записи двойка в степени n выглядит, как 1 и n нулей. Тогда суммируя и , получим число, содержащее 2 единицы:

Теперь вычтем из получившегося числа 10000. По правилам вычитания занимаем у следующего разряда.

Теперь прибавляем к получившемуся числу 1:

Видим, что у результата 2013+1+1=2015 единиц.

Ответ: 2015.

Эта презентация может помочь разобраться в решении задания №16 ЕГЭ по информатике. Материал для презентации был взят с сайта К. Полякова (http://kpolyakov.spb.ru). В презентации рассмотрены решения некоторых заданий типа: сколько единиц в двоичной записи числа 81023 + 21024 – 3 и т.п.

Данная задачка судя по всему типовая в ЕГЭ по информатике, алгоритм ее решения в общем случае следующий: перевести число в двоичную форму (например, тут — http://floatingpoint.ru/online/dec2bin.php) и подсчитать количество единиц — калькулятор нулей и единиц в двоичной записи числа

Однако в некоторых простых случаях можно попробовать разложить искомое число на сумму или разность степеней двоек, и проделать вычисления в уме.

Для этого нужно помнить несколько первых степеней двойки и двоичные записи по крайней мере некоторых чисел от 1 до 15:

1024 = 2^10, 512 = 2^9, 256 = 2^8, 128 = 2^7, 64 = 2^6, 32 = 2^5, 16 = 2^4

15 = 1111, 14 = 1110, 13 = 1101, 12 = 1100, 11 = 1011, 10 = 1010, 9 = 1001, 8 = 1000, 7 = 111, 6 = 110, 5 = 101, 4 = 100, 3 = 11, 2 = 10, 1 = 1.

Так же могут оказаться полезны некоторые суммы, например:

192 = 128 + 64

160 = 128 + 32

320 = 256 + 64

640 = 512 + 128

Приведем некоторые типовые примеры.

Сколько единиц в двоичной записи числа 1025?

1025 = 1024 + 1
1024 = 2^10 это степень двойки, а единица так и будет единицей, следовательно, 
всего в двоичной записи числа 1025 ровно 2 единицы. 

10000000001

Сколько единиц в двоичной записи числа 519?

519 = 512 + 7
512 = 2^9 это степень двойки, а 7 записывается в двоичной системе как 111 и содержит три единицы, 
следовательно, всего в двоичной записи числа 519 содержится ровно 4 единицы. 

1000000111

Сколько единиц в двоичной записи числа 514?

514 = 512 + 2
Слагаемые 512 = 2^9 и 2 = 2^1 - это степени двойки, следовательно, в двоичной записи числа 514 
ровно 2 единицы. 

1000000010

Сколько единиц в двоичной записи числа 127?

127 = 128 - 1
Число 128 представляет собой целую степень двойки и равняется 2^7, требуя таким образом 
для своей записи ровно 8 бит: 10000000
10000000-1 = 1111111
Следовательно, в записи числа 127 содержится 7 единиц.

1111111

Сколько единиц в двоичной записи числа 195?

195 = 192 + 3 = 128 + 64 + 3
128 = 2^7
64 = 2^6
3 = 11 в двоичной системе и содержит 2 единицы. Таким образом в двоичной записи числа 195 
содержится 4 единицы.

11000011

Сколько единиц в двоичной записи числа 173?

173 = 160 + 13
160 = 128 + 32 = 2^7 + 2^5, а 13 = 1101 в двоичной системе. 
Тогда всего получим 5 единиц. 

10101101

Сколько единиц в двоичной записи числа 3458?

3458 = 2048 + 1410
1410 = 1024 + 386
386 = 256 + 130
130 = 128 + 2
Таким образом 3458 = 2^11 + 2^10 + 2^8 + 2^7 + 2^1 и всего будет 5 единиц. 

110110000010

Решение задач 1 ЕГЭ по информатике 2015 года

Рассмотрим задачу №1 из демоверсии  ФИПИ 2015 года:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110.Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В – 101
2) это невозможно
3) для буквы В – 010
4) для буквы Б – 10

Давайте проанализируем текст задачи. Итак, нам известно, что используется неравномерный двоичный код. Что это такое? На самом деле все очень просто:

равномерное кодирование — каждый символ кодируется кодами равной длины

неравномерное кодирование — разные символы могут кодироваться кодами разной длины

Например, если у нас есть три символа А, Б, В и закодированы они так:

• А — 010
• Б — 011
• В — 111

, то это равномерное кодирование, так как длина кода одинаковая. Если же эти же символы мы закодируем вот так:

• А — 01
• Б — 110
• В — 1011

, то получим неравномерное кодирование.

Кроме этого, нам необходимо знать и понимать условие Фано

Никакое кодовое слово не может быть началом другого кодового слова

Также существует обратное условие Фано

Никакое кодовое слово не является окончанием другого кодового слова

Чтобы однозначно декодировать сообщение, достаточно того, чтобы условие Фано (или обратное условие) выполнялось.

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

Рассмотрим первый вариант ответа. Если мы для буквы В сократим код до 101, то условие Фано нарушено не будет. Действительно, с кода 101 не начинается ни один из четырех оставшихся кодов для А, Б, Г и Д и все коды различны.

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

Третий вариант не подходит, так как в этом случае код буквы В — 010 будет начинаться с 0, а 0 — это код буквы А. Получается, что это нарушает условие Фано.

Вариант 4 тоже не подходит. В этом случае код буквы Б — 10 будет являться началом для кода буквы В, а это нарушение условия Фано.

Правильный ответ: 1.

Для успешного решения задач типа А1 ЕГЭ по информатике рекомендую ознакомиться со статьями “Системы счисления” и “Перевод чисел из двоичной системы счисления в десятичную”. Для контроля правильности перевода удобно использовать “Скрипт для перевода числа из десятичной системы счисления в любую другую”.

Задачи А1 предполагают проверку знаний  о  системах  счисления  и  двоичном  представлении информации в памяти компьютера.

Рассмотрим решение задачи А1 из демоверсии ЕГЭ 2012.

Сколько единиц в двоичной записи числа 1025?
1)   1
2)   2
3)   10
4)   11

Данную задачу можно решить простым переводом числа 1025 в двоичную систему счисления, а затем посчитать количество единиц.

Как видно, в полученном двоичном числе содержится 2 единицы.

Второй способ решения данной задачи рассчитан на тех, кто хорошо знает степени числа 2. Если посмотреть на число 1025 внимательно, можно заметить, что 1025=1024+1. Число 1024 – это 2¹⁰. Отсюда следует, что 1025=2¹⁰+1.

Если посмотреть как выглядят степени числа 2 записанные в двоичной системе счисления, то нетрудно представить число 1024 в двоичной системе счисления.

Прибавив к получившемуся числу единицу получим число 10000000001₂, которое содержит 2 единицы.

Третий способ вытекает из предыдущего. Если посмотреть внимательно, то можно увидеть, что любое число, являющееся степенью двойки и записанное в двоичной системе счисления содержит одну единицу. Таким образом узнать количество единиц в двоичной записи любого числа очень просто — достаточно представить его как сумму степеней числа 2 — количество слагаемых и будет указывать число единиц.

Возьмем для примера число 73 и узнаем сколько единиц в его двоичной записи.

73=64+8+1=2⁶+2³+2⁰. Так как слагаемых у нас получилось три, значит и единиц в двоичной записи числа 73 будет тоже 3.

Решение задачи А1 демонстрационной версии ЕГЭ 2013:

Сколько единиц в двоичной записи десятичного числа 255?

1) 1        2) 2        3) 7        4) 8

Первый способ:

Для успешного решения данной задачи необходимо знать, что 256 это 2 в восьмой степени или 10000 0000 в двоичной системе счисления — 256=2⁸=100000000₂. Соответственно, 255 — это 11111111 в двоичной системе счисления — 255₁₀=11111111₂. Правильный ответ — 4 (8 единиц).

Второй способ:

Этот способ заключается в переводе числа 255 из десятичной системы счисления в двоичную и подсчете единиц:

Как видим, количество единиц восемь. Правильный ответ 4.

Автор: