Решение задания №16 из ЕГЭ по информатике

Кодирование информации, системы счисления

Основные определения

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

Система называется позиционной, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число.

Алфавит системы счисления — это используемый в ней набор цифр.

Основание системы счисления — это количество цифр в алфавите (мощность алфавита).

Разряд — это позиция цифры в записи числа. Разряды в записи целых чисел нумеруются с нуля справа налево.

Любое целое число A, записанное в системе счисления с основанием p, можно представить в расширенной форме:

Правила перевода чисел из одной системы счисления в другую.

Перевод целых чисел в десятичную систему счисления из других систем счисления.

Для перевода целого числа, записанного в системе счисления с основанием p, в десятичную, нужно пронумеровать цифры его целой части справа налево, начиная с 0, затем найти произведение каждой цифры числа на степень основания, где показателем степени является номер цифры, и сложить полученные значения (то есть, нужно представить число в расширенной форме и вычислить).

Перевод целых десятичных чисел в другие системы счисления.

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

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

Легко заметить, что множители при степенях p не что иное, как остатки от последовательного деления десятичного числа на p.

Кратные системы счисления

Для перевода восьмеричного числа в двоичную систему счисления достаточно заменить каждую цифру восьмеричного числа соответствующим трехразрядным двоичным числом.

Для перевода двоичного числа в восьмеричную систему счисления нужно разбить число на триады, начиная справа. Каждую триаду записать в виде одной восьмеричной цифры.


0	0	000
1	1	001
2	2	010
3	3	011
4	4	100
5	5	101
6	6	110
7	7	111

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

Для перевода двоичного числа в шестнадцатеричную систему счисления нужно разбить число на тетрады, начиная справа. Каждую тетраду записать в виде одной шестнадцатеричной цифры.


0	0	0000
1	1	0001
2	2	0010
3	3	0011
4	4	0100
5	5	0101
6	6	0110
7	7	0111
8	8	1000
9	9	1001
10	A	1010
11	B	1011
12	C	1100
13	D	1101
14	E	1110
15	F	1111

Некоторые полезные формулы

Число в системе счисления с основанием p записывается как одна единица и N нулей:
Например, , в десятичной системе счисления.
Число в системе счисления с основанием p записывается как N старших цифр данной системы счисления.
Например, в десятичной системе счисления.
Число в системе счисления с основанием p записывается как
N – M старших цифр данной системы счисления и M нулей.
Например, в десятичной системе счисления.

Задачи

Найдите основание системы счисления, в которой выполнено сложение: 144 + 24 = 201. [Материалы ЕГЭ №16 К.Ю. Полякова, №38]
Решение:
144_x + 24_x = 201_x, где х – искомое основание.
Запишем все числа в расширенной форме:
1∙x²+ 4∙x + 4 + 2∙x + 4= 2∙x² + 1
x²- 6∙x - 7= 0
x₁= -1, посторонний корень, так как x>0.
x₂= 7
Ответ: 7.
Решите уравнение 100₇+ x = 230₅. Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.
[Материалы ЕГЭ №16 К.Ю. Полякова, №68]
Решение:
100₇ + x = 230₅ x = 230₅ - 100₇
100₇ = 1∙72 = 49
230₅ = 2∙5² + 3∙5¹ = 50 + 15 = 65
x = 65 – 49 = 16
16 = 2 ∙ 61 + 4 ∙ 60 = 246
Ответ: 24
Решите уравнение 222_x+ 4 = 1100₅. Ответ запишите в троичной системе счисления. [Материалы ЕГЭ №16 К.Ю. Полякова, №102]
Решение:
222_x + 4 = 1100₅ , где х – искомое основание.
Запишем все числа в расширенной форме:
2∙x²+ 2 ∙x¹ + 2 ∙x₀ + 4 = 1 ∙53 +1 ∙52
2∙x² + 2 ∙x – 144 = 0
x²+ x – 72 = 0
x₁= -9, посторонний корень, так как x>0.
x₂= 8
8 = 2∙31 + 2∙30 =223
Ответ: 22
В системе счисления с некоторым основанием десятичное число 83 записывается в виде 123. Укажите это основание. [Материалы ЕГЭ №16 К.Ю. Полякова, №27]
Решение:
83 = 1∙x² + 2∙x¹ + 3∙x⁰ , где х – искомое основание.
x²+ 2∙x - 80 = 0
x₁= -10, посторонний корень, так как x>0.
x₂= 8
Ответ: 8
Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 35 оканчивается на 8. [Материалы ЕГЭ №16 К.Ю. Полякова, №29]
Решение:
35 = N∙p +8, p>5 и N целое число.
N∙p = 27, тогда 27 p = {9, 27}
Ответ: 9, 27
Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 84 оканчивается на 14. [Материалы ЕГЭ №16 К.Ю. Полякова, №43]
Решение:
Так как, известны две последние цифры записи числа 84 в системе счисления с основанием p, то
84 = N∙p²+ 1∙p¹ +4∙p0, p>4
N∙p² + p = 80
(N∙p + 1)∙p = 80
Следовательно, 80
p = {5, 8, 10, 16, 20, 40, 80}, при этом
Выполнив проверку получаем, что p={5, 80}
Ответ: 5, 80
Запись числа 180 в системе счисления с основанием p содержит 3 цифры и оканчивается на 0. Перечислите в порядке возрастания все возможные основания системы счисления. [Материалы ЕГЭ №16 К.Ю. Полякова, №60]
Решение:
180 = a₂∙p² + a₁∙p¹ + 0∙p0 , где p искомое основание.
180 = a₂∙p² + a₁∙p
180 = p∙( a₂∙p + a₁ )
Следовательно, 180 p и p2 ≤ 180 ≤ p3
p = {6, 9, 10, 12}
Ответ: 6, 9, 10, 12
Сколько единиц в двоичной записи числа 8⁴¹⁵ – 4¹⁶²+ 2⁵⁴³ – 25?
[Материалы ЕГЭ №16 К.Ю. Полякова, №108]
Решение:
8⁴¹⁵ – 4¹⁶²+ 2⁵⁴³ – 25 = 2¹²⁴⁵ – 2³²⁴ + 2⁵⁴³ – 25 = 2¹²⁴⁵ + (2⁵⁴³ – 2³²⁵ ) + (2³²⁴ -32) +7 = Количество единиц = 1 + 218 + 319 + 3 = 541
Ответ: 541
Сколько значащих нулей в двоичной записи числа 4²³⁰ + 8¹²⁰ – 2¹⁵⁰ – 100? [Материалы ЕГЭ №16 К.Ю. Полякова, №115]
Решение:
Количество нулей = Количество разрядов – Количество единиц
4²³⁰ + 8¹²⁰ – 2¹⁵⁰ – 100 = 2⁴⁶⁰+ 2³⁶⁰– 2¹⁵¹ + 2¹⁵⁰ – 2⁷ + 28 =
= 2⁴⁶⁰+ (2³⁶⁰– 2¹⁵¹ )+ (2¹⁵⁰ – 2⁷) + 11100₂
461 – (1 + 209 + 143 + 3) = 461 – 356 = 105
Ответ: 105
Значение выражения 49⁷ + 7²⁰ – 28 записали в системе счисления с основанием 7. Сколько цифр «6» содержится в этой записи? [Я.Н.Зайдельман , ЕГЭ 2020. Информатика и ИКТ. Подготовка к ЕГЭ в 2020 году. Диагностические работы. ФГОС. — М.: МЦНМО, 2019., стр 64, №16]

Решение:

49⁷ + 7²⁰ – 28 = 7¹⁴ + 7²⁰ – 49 + 21 = 7²⁰ + 7¹⁴ – 7² + 3∙7 =

= 100…00₇ + () + 30₇, первое и третье слагаемые не влияют на количество цифр «6» в записи числа.

Ответ: 12

Информационные источники

«ФИПИ. Открытый банк тестовых заданий», http://os.fipi.ru/tasks/5/a
Материалы для подготовки к ЕГЭ по информатике К.Ю. Полякова, http://kpolyakov.spb.ru/school/ege.htm
Образовательный портал «Решу ЕГЭ», https://ege.sdamgia.ru/
Я.Н.Зайдельман , ЕГЭ 2020. Информатика и ИКТ. Подготовка к ЕГЭ в 2020 году. Диагностические работы. ФГОС. — М.: МЦНМО, 2019.
Я. Н. Зайдельман, М. А. Ройтберг, Информатика и ИКТ. Подготовка к ЕГЭ в 2019 году. Диагностические работы. ФГОС.— М.: МЦНМО, 2019.
Е.Л. Теплоухова, Как решать задачи на системы счисления? ЕГЭ. Информатика. Задание №16. - «ЛитРес: Самиздат»2019
Ушаков Д.М. ЕГЭ-2020. Информатика. 20 тренировочных вариантов экзаменационных работ для подготовки к ЕГЭ. — М.: АСТ, 2019.