Задачи ЕГЭ, при решении которых используются знания о системах счисления.

Необходимые знания : уметь переводить числа: - из любой системы счисления в десятичную; - из десятичной системы счисления в любую; - между двоичной, восьмеричной и шестнадцатеричной системами счисления.

Полезно помнить, что в двоичной системе: - четные числа оканчиваются на 0, нечетные – на 1; - числа, которые делятся на 4, оканчиваются на 00, и т.д.; - числа, которые делятся на 2 k, оканчиваются на k нулей; - если число N принадлежит интервалу 2 k-1 N < 2 k, в его двоичной записи будет всего k цифр, например, для числа 123: 2 6 = < 128 = 2 7, 123 = (7 цифр)

- числа вида 2 k записываются в двоичной системе как единица и k нулей, например: 16 = 2 4 = = 2 8 = числа вида 2 k -1 записываются в двоичной системе k единицами, например: 15 = = = = если известна двоичная запись числа N, то двоичную запись числа 2·N можно легко получить, приписав в конец ноль, например: 15 = , 30 = , 60 = , 120 =

задание под номером 1 Пример задания: Сколько единиц в двоичной записи десятичного числа 260? Решение: 1) проще всего представить заданное число в виде суммы степеней числа 2: 260 = = ) количество единиц в двоичной записи числа равно количеству слагаемых в таком разложении Ответ: 2

Еще пример задания: Сколько единиц в двоичной записи шестнадцатеричного числа 12F0 16 ? Решение: представим заданное число в двоичной системе счисления, сопоставив каждой цифре ее код : 12F0 16 = считаем количество единиц в двоичной записи числа Ответ: 6

Ещё пример задания: Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел номер того числа, в двоичной записи которого содержится ровно 6 единиц. Если таких чисел несколько, укажите номер наибольшего из них. 1)63 10 * ) F ) )

Решение: 1) нужно перевести все заданные числа в двоичную систему, подсчитать число единиц и выбрать наибольшее и чисел, в которых ровно 6 единиц; 2) для первого варианта переведем оба сомножителя в двоичную систему: = = ) в первом числе ровно 6 единиц, умножение на второе добавляет в конец два нуля: * 4 10 = * = то есть в этом числе 6 единиц

4) для второго варианта воспользуемся связью между шестнадцатеричной и двоичной системами счисления: каждую цифру шестнадцатеричного числа можно переводить отдельно в тетраду (4 двоичных цифры): F 16 = = F8 16 = ) после добавления единицы F = также получаем число, содержащее ровно 6 единиц, но оно меньше, чем число в первом варианте ответа ( )

6) для третьего варианта используем связь между восьмеричной и двоичной системами: каждую цифру восьмеричного числа переводим отдельно в триаду (группу из трёх) двоичных цифр: = = это число тоже содержит 6 единиц, но меньше, чем число в первом варианте ответа ( ) 7) последнее число уже записано в двоичной системе, оно тоже содержит ровно 6 единиц, но меньше первого числа

8) таким образом, все 4 числа, указанные в вариантах ответов содержат ровно 6 единиц, но наибольшее из них – первое Ответ: 1.

Задачи для тренировки: 1) Сколько единиц в двоичной записи числа 195? 2) Сколько единиц в двоичной записи числа 173? 3) Сколько единиц в двоичной записи числа A87 16 ? 4) Сколько единиц в двоичной записи числа ? 5) Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел номер того числа, в двоичной записи которого содержится ровно 4 единицы. Если таких чисел несколько, укажите номер наибольшего из них. 1)15 10 * ) D )3) ) ) Сколько единиц в троичной записи десятичного числа 243?

Ответы: 1)4 2)5 3)6 4)6 5)3 6)1 (3 5 )

задание под номером 10 (анализ последовательностей) Что нужно знать: русский алфавит принципы работы с числами, записанными в позиционных системах счисления

Пример задания: Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. КККК 2. КККЛ 3. КККР 4. КККТ …… Запишите слово, которое стоит на 67-м месте от начала списка.

Решение: 1)самый простой вариант решения этой задачи – использование систем счисления; действительно, здесь расстановка слов в алфавитном порядке равносильна расстановке по возрастанию чисел, записанных в четверичной системе счисления основание системы счисления равно количеству используемых букв

2) выполним замену К 0, Л 1, Р 2, Т 3 3) поскольку нумерация слов начинается с единицы, а первое число КККК 0000 равно 0, под номером 67 будет стоять число 66, которое нужно перевести в четверичную систему: 66 = ) Выполнив обратную замену (цифр на буквы), получаем слово ЛККР. Ответ: ЛККР.

Ещё пример задания: Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 101-м месте от начала списка.

Решение: 1) по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) А 0, О 1, У 2,

2) выпишем начало списка, заменив буквы на цифры: …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. тогда легко понять, что 101-м месте стоит число 100, записанное в троичной системе счисления

3) переведем 100 в троичную систему: 100 = ) заменяем обратно цифры на буквы: ОАУАО Ответ: ОАУАО.

Еще пример задания: Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова РУКАА.

Решение: 1)будем использовать четверичную систему счисления с заменой А 0, К 1, Р 2, У 3 2) слово РУКАА запишется в новом коде так ) переводим это число в десятичную систему: = = 720 4) поскольку нумерация элементов списка начинается с 1, а числа в четверичной системе – с нуля, к полученному результату нужно прибавить 1, тогда… Ответ: 721.

Задачи для тренировки: 1) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова УКАРА.

2) Все 5-буквенные слова, составленные из букв К, О, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ККККК 2. ККККО 3. ККККР 4. КККОК …… Запишите слово, которое стоит под номером 238.

3) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер первого слова, которое начинается с буквы К.

Ответы: 1)841 2)РРРОК 3)257

задание под номером 16 (кодирование чисел) Что нужно знать: - последняя цифра записи числа в системе счисления с основанием N – это остаток от деления этого числа на N - две последние цифры – это остаток от деления на N 2, и т.д. - число 2 N в двоичной системе записывается как единица и N нулей: 100…0 - число 2 N -1 в двоичной системе записывается как N единиц: 11…1 - число 2 N –2 K при K < N в двоичной системе записывается как N–K единиц и K нулей

Пример задания: Сколько единиц в двоичной записи числа – 3? Решение: - приведём все числа к степеням двойки: – 3 = число запишется как 1 единица и 2014 нулей, а 3=11 2, тогда – 3 - это … … Т.е. единиц 2014 – 1 = прибавление даст еще одну единицу, всего получается = 2014 единиц Ответ: 2014.

Ещё пример задания: Сколько единиц в двоичной записи числа – – 12? Решение: - запишем выражение следующим образом – – 12 = – – вспомним, что тогда – = 11…100…0 это 2512 – единиц и 530 – нулей.

- выделим из этого значения последнюю единицу со следующими 530 нулями как отдельное слагаемое: -таким образом, общее число единиц равно = 3038 Ответ: 3038.

Ещё пример задания: Значение арифметического выражения: – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи? Решение. - запишем выражение следующим образом: – 9 = (3 2 ) = = = в полученном числе три двойки. Ответ:3

Задачи для тренировки: 1. Сколько единиц в двоичной записи числа – 8 ? 2. Сколько единиц в двоичной записи числа – – Значение арифметического выражения: – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи? 4. Значение арифметического выражения: – 16 записали в системе счисления с основанием 4. Сколько цифр «3» содержится в этой записи?

Ответ. 1)2013 2)2395 3)2013 4)2012

Задание 5 в ЕГЭ 2016 г. Пример задания: На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись преобразуется в запись ; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 125. В ответе это число запишите в десятичной системе счисления.

Решение. - данный алгоритм приписывает в конце числа или 10, если изначально в его двоичной записи было нечетное количество единиц, или 00 если четное = может получиться в результате работы алгоритма из числа = Ответ:31.

Задачи для тренировки: 1. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись преобразуется в запись ; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 77. В ответе это число запишите в десятичной системе счисления.

2. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись преобразуется в запись ; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.

Ответ. 1) 19 2) 46