Презентация, доклад на тему Разбор задач ЕГЭ по теме Системы счисления (№1, №10, №16) по материалам сайта К. Полякова

материалам сайта К. Полякова http://kpolyakov.spb.ru

Выступление подготовила
учитель информатики и ИКТ
МБОУ гимназии №2
Назарова Алла Васильевна

представление информации в памяти компьютера.
Что нужно знать:
перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной системами счисления

системы счисления.
Что нужно знать:
русский алфавит
принципы работы с числами, записанными в позиционных системах счисления
если слово состоит из L букв, причем есть n1 вариантов выбора первой буквы, n2 вариантов выбора второй буквы и т.д., то число возможных слов вычисляется как произведение
N = n1 · n2 · … · nL
если слово состоит из L букв, причем каждая буква может быть выбрана n способами, то число возможных слов вычисляется как N = nL

счисления.
Что нужно знать:
принципы кодирования чисел в позиционных системах счисления
чтобы перевести число, скажем, 12345N, из системы счисления с основанием в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду:
4 3 2 1 0 ← разряды
1 2 3 4 5N = 1·N4 + 2·N3 + 3·N2 + 4·N1 + 5·N0
последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на N
две последние цифры – это остаток от деления на , и т.д.

в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

2128 – 250

Е, С, Н , А, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение:
количество слов с буквой А можно вычислить как разность между количеством всех возможных слов и количеством слов, в которых нет буквы А
количество всех слов 5 · 5 · 5 = 53 = 125 (на любой из 3-х позиций может стоять любая из 5 букв)
количество слов, в которых нет буквы А равно 4 · 4 · 4 = 43 = 64 (на любой из 3-х позиций может стоять любая из 4 букв, кроме А)
получается 125 – 64 = 61 слово, в котором есть буква А (она или несколько)
Ответ: 61.

{A, C, G, T}, которые содержат ровно две буквы A?

Решение:
рассмотрим различные варианты слов из 5 букв, которые содержат две буквы А и начинаются с А:
АА*** А*А** А**А* А***А
Здесь звёздочка обозначает любой символ из набора {C, G, T}, то есть один из трёх символов.
итак, в каждом шаблоне есть 3 позиции, каждую из которых можно заполнить тремя способами, поэтому общее число комбинаций (для каждого шаблона!) равно 33 = 27
всего 4 шаблона, они дают 4 · 27 = 108 комбинаций
теперь рассматриваем шаблоны, где первая по счёту буква А стоит на второй позиции, их всего три:
*АА** *А*А* *А**А
они дают 3 · 27 = 81 комбинацию
два шаблона, где первая по счёту буква А стоит на третьей позиции:
**АА* **А*А
они дают 2 · 27 = 54 комбинации
и один шаблон, где сочетание АА стоит в конце
***АА
они дают 27 комбинаций
всего получаем (4 + 3 + 2 + 1) · 27 = 270 комбинаций
ответ: 270.

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

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

в четверичной системе – с нуля, поэтому для получения 67-го элемента списка нужно переводить в четверичной систему число 67-1 = 66.

2150 – 122

Решение:
приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 27 – 22 – 21:
42015 + 8405 – 2150 – 122 = (22)2015 + (23)405 – 2150 – 27 + 22 + 21 =
= 24030 + 21215 – 2150 – 27 + 22 + 21
вспомним, число 2N–2K при K < N записывается как N–K единиц и K нулей:
для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2N–2K, причём в этой цепочке степени двойки нужно выстроить по убыванию
в нашем случае в выражении 24030 + 21215 – 2150 – 27 + 22 + 21 стоит два знака «минус» подряд, это не позволяет сразу использовать формулу
используем теперь равенство , так что – 2150 = – 2151 + 2150; получаем
24030 + 21215 – 2151 + 2150 – 27 + 22 + 21
здесь две пары 2N–2K , а остальные слагаемые дают по одной единице
общее число единиц равно 1 + (1215 – 151) + (150 – 7) + 1 + 1 = 1210
ответ: 1210.

– 2128 – 250

Решение:
Общая идея: количество значащих нулей равно количеству всех знаков в двоичной записи числа (его длине!) минус количество единиц
приведём все числа к степеням двойки, учитывая, что 250 = 256 – 4 – 2 = 28 – 22 – 21:
4512 + 8512 – 2128 – 250 = (22)512 + (23)512 – 2128 – 28 + 22 + 21 = 21536 + 21024 – 2128 – 28 + 22 + 21
старшая степень двойки – 21536, двоичная запись этого числа представляет собой единицу и 1536 нулей, то есть, состоит из 1537 знаков; таким образом, остаётся найти количество единиц
вспомним, число 2N–2K при K < N записывается как N–K единиц и K нулей:
для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2N–2K, причём в этой цепочке степени двойки нужно выстроить по убыванию
в нашем случае вы выражении 21536 + 21024 – 2128 – 28 + 22 + 21 стоит два знака «минус» подряд, это не позволяет сразу использовать формулу
используем теперь равенство , так что – 2128 = – 2129 + 2128; получаем
21536 + 21024 – 2129 + 2128 – 28 + 22 + 21
здесь две пары 2N–2K , а остальные слагаемые дают по одной единице
общее число единиц равно 1 + (1024 – 129) + (128 – 8) + 1 + 1 = 1018
таким образом, количество значащих нулей равно 1537 – 1018 = 519
ответ: 519.

счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Решение:
приведём все слагаемые к виду 3N и расставим в порядке убывания степеней:
98 + 35 – 9 = 316 + 35 – 32
первое слагаемое, 316, даёт в троичной записи одну единицу – она нас не интересует
пара 35 – 32 даёт 5 – 2 = 3 двойки
Ответ: 3.

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