Системы счисления Задания из ЕГЭ

Примеры заданий: 1. Дано: D7 16 и Какое из чисел с, записанных в двоичной системе счисления, удовлетворяет неравенству a < c < b? 1) ) ) ) Общий подход: перевести все числа (и исходные данные, и ответы) в одну (любую!) систему счисления и сравнить. Решение (вариант 1, через десятичную систему): 1) 2) А3 (базовый уровень, время – 1 мин) Тема: Системы счисления и двоичное представление информации в памяти компьютера. 3) переводим в десятичную систему все ответы: = 217, = 220, = 215, =216 4) очевидно, что между числами 215 и 217 может быть только 216 5) таким образом, верный ответ – 4.

2. Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (-78)? 1) 3 2) 4 3) 5 4) 6 Решение (вариант 1, классический): 1) переводим число 78 в двоичную систему счисления: 78 = = = ) по условию число занимает в памяти 1 байт = 8 бит, поэтому нужно представить число с помощью 8 разрядов 3) чтобы получилось всего 8 разрядов (бит), добавляем впереди один ноль: 78 = ) делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0): обратный код 5) добавляем к результату единицу = это и есть число (-78) в двоичном дополнительном коде 6) в записи этого числа 4 единицы 7) таким образом, верный ответ – 2.

Задачи для тренировки: 1. Сколько единиц в двоичной записи числа 173 ? 1) 72) 53) 64) 4 2. Как представлено число 263 в восьмеричной системе счисления? 1) ) ) ) Как записывается число A87 16 в восьмеричной системе счисления? 1) ) ) ) Как записывается число в шестнадцатеричной системе счисления? 1) ) 1A4 16 3) 1EC 16 4) A Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (-128)? 1) 1 2) 2 3) 3 4) 4 6. Дано: a=DD 16, b= Какое из чисел С, записанных в двоичной системе счисления, удовлетворяет неравенству ? 1) ) ) )

А4 (базовый уровень, время – 2 мин) Тема: Выполнение арифметических операций в двоичной, восьмеричной и шестнадцатеричной системах счисления. Пример задания: Чему равна сумма чисел x=43 8 и y=56 16 ? 1) ) ) ) Общий подход: перевести оба исходных числа и ответы в одну (любую!) систему счисления, и выполнить сложение Решение (вариант 1, через десятичную систему): 1) x=43 8 =4*8+3=352) y=56 16 =5*16+6=86 3) сложение: = 121 4a) переводим результат во все системы, в которых даны ответы (пока не найдем нужный): 121 = = = b) или переводим все ответы в десятичную систему = 81, = 121,69 16 = 105, = 65 5) таким образом, верный ответ – 2.

Задачи для тренировки: 1. Вычислите значение суммы в двоичной системе счисления. 1) ) ) ) Вычислите сумму чисел x и y, при x = 271 8, y = Результат представьте в шестнадцатеричной системе счисления. 1) ) 1AD 16 3) ) 10B Чему равна разность чисел и ? 1) ) ) ) 64 16

А11 (базовый уровень, время – 1 мин) Тема: Кодирование и декодирование информации. Примеры заданий: 1. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится 1) 4B 16 2) )BACD 16 4) Решение: 1) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный 2) последовательность БАВГ кодируется так: = ) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем = = 4B 16 4) правильный ответ – 1.

ABCDE Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице: Определить, какой набор букв закодирован двоичной строкой ) EBCEA2) BDDEA3) BDCEA4) EBAEA Решение (вариант 1, декодирование с начала): 1) здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений 2) попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно 3) пусть первая буква – E с кодом 011, тогда остается цепочка для кода первой буквой может быть только B с кодом 01, тогда остается ( начало исходной цепочки – EB?) для кода первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв

поэтому наше предположение о том, что первая буква – E, неверно 4) пусть первая буква – B с кодом 01, тогда остается цепочка для кода первой буквой может быть только D с кодом 10, тогда остается (можно полагать, что начало исходной цепочки – BD?) для кода на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA 5) правильный ответ – 3 для кода первой буквой может быть только С с кодом 100, тогда остается (начало исходной цепочки – BDC?) Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»

Решение (вариант 2, кодирование ответов): 1) в данном случае самое простое и надежное – просто закодировать все ответы, используя приведенную таблицу кодов, а затем сравнить результаты с заданной цепочкой 2) получим 1) EBCEA – ) BDDEA – ) BDCEA – ) EBAEA – ) сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.

Задачи для тренировки: 1. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится: 1) ) D2 16 3) ) 2D Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице: abcde Определите, какой набор букв закодирован двоичной строкой ) baade2) badde3) bacde4) bacdb

B3 (повышенный уровень, время – 5 мин) Тема: Кодирование чисел. Системы счисления. Примеры заданий: 1. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11? Общий подход: вспомним алгоритм перевода числа из десятичной системы в систему с основанием, из него следует, что младшая цифра результата – это остаток от деления исходного числа на N, а две младших цифры – это остаток от деления на N 2 и т.д. в данном случае N=4, остаток от деления числа на N 2 =16 должен быть равен 11 4 = 5 потому задача сводится к тому, чтобы определить все числа, которые меньше или равны 25 и дают остаток 5 при делении на 16

1) общий вид чисел, которые дают остаток 5 при делении на 16: k*16+5 где k – целое неотрицательное число (0, 1, 2, …) Решение (вариант 1, через десятичную систему): 2) среди всех таких чисел нужно выбрать те, что меньше или равны 25 («не превосходят 25»); их всего два: 5 (при k=0) и 21 (при k=1) таким образом, верный ответ – 5, 21. Решение (вариант 2, через четверичную систему): 1.переведем 25 в четверичную систему счисления: 25 = 121 4, все интересующие нас числа не больше этого значения 2.из этих чисел выделим только те, которые заканчиваются на 11, таких чисел всего два: это 11 4 = 5 и = 21 3.таким образом, верный ответ – 5, 21.

2. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2. Общий подход: здесь обратная задача – неизвестно основание системы счисления, мы обозначим его через N поскольку последняя цифра числа – 2, основание должно быть больше 2, то есть N>2 вспомним алгоритм перевода числа из десятичной системы в систему с основанием, из него следует, что младшая цифра результата – это остаток от деления исходного числа на N Решение: 1) итак, нужно найти все целые числа N3, такие что остаток от деления 23 на N равен 2, или (что то же самое) 23=k*N+2(*) где k – целое неотрицательное число (0, 1, 2, …); 2) сложность в том, что и k, и N неизвестны, однако здесь нужно «играть» на том, что это натуральные числа 3) из формулы (*) получаем k*N=21, так что задача сводится к тому, чтобы найти все делители числа 21, которые больше 2 4) в этой задаче есть только три таких делителя: N=3, 7 и 21 5) таким образом, верный ответ – 3, 7, 21.

3. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 31 оканчивается на 11. Общий подход: неизвестно основание системы счисления, мы обозначим его через N пока будем считать, что запись числа 31 в системе с основанием N состоит из трех цифр, причем две младшие (11) нам даны, а одну (обозначим ее через k) нужно найти: разряды 31 = k 1 1 N = k·N 2 + N 1 + N 0 = k·N 2 + N + 1 можно показать, что при большем количестве разрядов эта формула также верна, то есть, число 31 можно представить как 31=k·N 2 + N + 1 при некотором целом k; например, для числа с пятью разрядами получаем: разряды 31 = k 4 k 3 k N = k 4 ·N 4 + k 3 ·N 3 + k 2 ·N 2 + N 1 + N 0 = k·N 2 + N + 1 для k=k 4 ·N 2 +k 3 ·N+k 2 (из первых трех слагаемых вынесли общий множитель ·N 2 )

Решение: итак, нужно найти все целые числа, такие что 31=k. N 2 +N+1 (**) где k – целое неотрицательное число (0, 1, 2, …); сложность в том, что k и N неизвестны, однако здесь нужно «играть» на том, что это натуральные числа из формулы (**) получаем, так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом, то есть, k=(30-N)/N 2 – целое число выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30 из всех этих делителей только для 2, 3, 5 и 30 значение k=(30-N)/N 2 – целое число (оно равно соответственно 7, 3, 1 и 0) таким образом, верный ответ – 2, 3, 5, 30.

Решение: итак, нужно найти все целые числа, такие что (**) где – целое неотрицательное число (0, 1, 2, …); сложность в том, что и, и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа из формулы (**) получаем, так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом, то есть, – целое число выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30 из всех этих делителей только для 2, 3, 5 и 30 значение – целое число (оно равно соответственно 7, 3, 1 и 0) таким образом, верный ответ – 2, 3, 5, 30.