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

1.

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

2.

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

3.

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

4.

- числа вида 2k записываются в двоичной системе
как единица и k нулей, например:
16 = 24 = 100002
256 = 28 = 100000002
- числа вида 2k-1 записываются в двоичной
системе k единицами, например:
15 = 24-1 = 11112
255 = 28 -1 = 111111112
- если известна двоичная запись числа N, то
двоичную запись числа 2·N можно легко
получить, приписав в конец ноль, например:
15 = 11112,
30 = 111102,
60 = 1111002, 120 = 11110002

5.

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

6.

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

7.

Ещё пример задания:
Даны 4 числа, они записаны с использованием
различных систем счисления. Укажите среди
этих чисел номер того числа, в двоичной
записи которого содержится ровно 6 единиц.
Если таких чисел несколько, укажите номер
наибольшего из них.
1) 6310 * 410
2) F816 + 110
3) 3338
4) 111001112

8.

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

9.

4) для второго варианта воспользуемся связью
между шестнадцатеричной и двоичной
системами счисления: каждую цифру
шестнадцатеричного числа можно переводить
отдельно в тетраду (4 двоичных цифры):
F16 = 11112
816 = 10002
F816 = 1111 10002
5) после добавления единицы
F816 + 1 = 1111 10012
также получаем число, содержащее ровно 6
единиц, но оно меньше, чем число в первом
варианте ответа (111111002)

10.

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

11.

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

12.

Задачи для тренировки:
1) Сколько единиц в двоичной записи числа 195?
2) Сколько единиц в двоичной записи числа 173?
3) Сколько единиц в двоичной записи числа A8716?
4) Сколько единиц в двоичной записи числа 7548?
5) Даны 4 числа, они записаны с использованием
различных систем счисления. Укажите среди этих
чисел номер того числа, в двоичной записи которого
содержится ровно 4 единицы. Если таких чисел
несколько, укажите номер наибольшего из них.
1) 1510 * 1610 + 410
2) D716 + 110
2) 3) 3448
4) 111000012
6) Сколько единиц в троичной записи десятичного
числа 243?

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

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

25.

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

26.

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

27.

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

28.

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

29.

Пример задания:
Сколько единиц в двоичной записи числа
81023 + 21024 – 3?
Решение:
- приведём все числа к степеням двойки:
81023 + 21024 – 3 = 23069 + 22014 - 3
-число 22014 запишется как 1 единица и 2014
нулей, а 3=112, тогда 22014 – 3 - это
100000…..0000
11
011111…..1101
Т.е. единиц 2014 – 1 = 2013
- прибавление 23069 даст еще одну единицу, всего
получается 2013 + 1 = 2014 единиц
Ответ: 2014.

30.

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

31.

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

32.

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

33.

Задачи для тренировки:
1. Сколько единиц в двоичной записи числа
42014 + 22015 – 8 ?
2. Сколько единиц в двоичной записи числа
42016 – 22018 + 8800 – 80
3. Значение арифметического выражения:
92016 + 32015 – 9
записали в системе счисления с основанием 3.
Сколько цифр «2» содержится в этой записи?
4. Значение арифметического выражения:
162016 + 42015 – 16
записали в системе счисления с основанием 4.
Сколько цифр «3» содержится в этой записи?

34.

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

35.

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

36.

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

37.

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

38.

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

39.

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