Подготовка к ЕГЭ-2013 по теме: Перебор слов и системы счисления

Задачи в ЕГЭ-2013 по теме:
«Перебор слов и системы счисления».
При подготовке к сдаче ЕГЭ следует знать:
1. Таблицу степеней числа «2».
2. Общую формулу кодирования: N=m*k , где
m — количество символов (знаков) в алфавите, с помощью которого кодируют;
k — длина кода, т.е. число знакомест, которое используется для кодирования одного символа исходного сообщения;
N — максимальное количество разных символов исходного сообщения, которое можно закодировать с помощью алфавита из m знаков при постоянной длине кода в k знакомест.
3. Таблицу основных единиц измерения информации, т.к часто необходим переход от одних единиц измерения информации к другим (от бит — к килобайтам, от мегабайт — килобайтам и т.д.).
Количество различных комбинаций определяется по формуле:
n=xy, где X - количество вариантов символов, y - длина последовательности сигналов.

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

Разбор задачи B4 (демо ЕГЭ 2013)
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?
Решение: Количество различных комбинаций из "точек" и "тире" определяется по формуле:
n=xy,
где X - количество вариантов символов,
y - длина последовательности сигналов.
2 варианта символов: «точка» и «тире» (Х=2).
Длина последовательности 1 - 4 сигнала (y1=4).
Длина последовательности 2 - 5 сигналов (y2=5).
n1=xy1 =24 = 16 комбинаций.
n2=xy2 =25 = 32 комбинации.
n=n1+n2=16+32=48 комбинаций из "точек" и "тире", т.е. могут быть
закодированы 48 различных символов.
Ответ: 48

Разбор задачи B4
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…… Запишите слово, которое стоит на 101-м месте от начала списка.
Решение:
Заменим буквы А, О, У на 0, 1, 2 (для них порядок очевиден – по возрастанию).
Выпишем начало списка, заменив буквы на цифры:
1. 00000
2. 00001
3. 00002
4. 00010
... Полученная запись есть числа, записанные в троичной системе счисления в порядке возрастания. Тогда на 101-м месте будет стоять число 100 (т. к. первое число 0). Переведём число 100 в троичную систему (деля и снося остаток справа налево):
100 / 3 = 33 (1)
33 / 3 = 11 (0)
11 / 3 = 3 (2)
3 / 3 = 1 (0)
1 / 3 = 0 (1)
В троичной системе 100 запишется как 10201. Произведём обратную замену и получим ОАУАО.
Ответ: ОАУАО

Разбор задачи B4
Все 5-буквенные слова, составленные из букв Б, О, Р, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. БББББ
2. ББББО
3. ББББР
4. БББОБ
…… Запишите слово, которое стоит под номером 240.
Решение:
Всего из трёх букв можно составить 35 = 243 слова. Очевидно, что последнее слово РРРРР. Тогда слово с номером 242 запишется как
242 — РРРРО,
241 — РРРРБ,
240 — РРРОР.
Ответ: РРРОР

Разбор задачи B4
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…… Укажите номер слова ОАОАО.
Решение: Заменим буквы А, О, У на 0, 1, 2 (для них порядок очевиден – по возрастанию)
Выпишем начало списка, заменив буквы на цифры:
1. 00000
2. 00001
3. 00002
4. 00010 ... Полученная запись есть числа, записанные в троичной системе счисления в порядке возрастания. Запишем слово ОАОАО в троичной системе: 10101 и переведём его в десятичную:
1*34 + 1*32 + 1*30 = 81 + 9 + 1 = 91.
Не забудем о том, что есть слово номер 1, записывающееся как 0, а значит, 91 — число, соответствующее номеру 92.
Ответ: 92.

Задачи для тренировки
1. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
…… Запишите слово, которое стоит на 210-м месте от начала списка.
2. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААР
4. ААААУ
4. АААКА
…… Запишите слово, которое стоит на 350-м месте от начала списка
3. Все 5-буквенные слова, составленные из букв И, О, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ИИИИИ
2. ИИИИО
3. ИИИИУ
4. ИИИОИ
…… Запишите слово, которое стоит под номером 240.
4. Все 4-буквенные слова, составленные из букв В, И, Р, Т, записаны в алфавитном порядке.
Вот начало списка:
1. ВВВВ
2. ВВВИ
3. ВВВР
4. ВВВТ
5. ВВИВ
…… Запишите слово, которое стоит на 249-м месте от начала списка.
5. Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке.
Вот начало списка:
1. АААА
2. АААМ
3. АААР
4. АААТ
5. ААМА
…… Запишите слово, которое стоит на 250-м месте от начала списка.

Задачи для тренировки
6. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААЛ
4. ААААО
5. ААААШ
4. АААКА
…… На каком месте от начала списка стоит слово ШКОЛА?
7. Все 5-буквенные слова, составленные из букв В, И, Н, Т, записаны в алфавитном порядке. Вот начало списка:
1. ВВВВВ
2. ВВВВИ
3. ВВВВН
4. ВВВИТ
5. ВВВИВ
…… Запишите слово, которое стоит под номером 1020.
8. Все 6-буквенные слова, составленные из букв Б, К, Ф, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ББББББ
2. БББББК
3. БББББФ
4. ББББКБ
…… Запишите слово, которое стоит на 345-м месте от начала списка.
9. Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее двух и не более четырёх сигналов (точек и тире)?
10. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
11. Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля?
12. Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?
В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?
За четверть Василий Пупкин получил 20 оценок. Сообщение о том, что он вчера получил четверку, несет 2 бита информации. Сколько четверок получил Василий за четверть?