Решение задач В4 на тему Кодирование информации «Перебор слов, системы счисления»
Некоторые задачи В4 отличаются содержанием и методом решения от остальных задач, поэтому они выделены в отдельный блок
ПРИМЕР
1 B4 . Все 5-буквенные слова, составленные из букв А, О, У, записаны в
алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААО 3. ААААУ 4. АААОА
…Запишите слово, которое стоит на 210-м месте от
начала списка.
Решение
Заменим буквы А, О, У на 0, 1, 2(для них порядок
очевиден – по возрастанию)
Выпишем начало списка, заменив буквы на цифры:
1. 00000
2. 00001 3. 00002 4. 00010
..Полученная запись есть числа, записанные в
троичной системе счисления в порядке возрастания. Тогда на 210 месте будет
стоять число 209 (т. к. первое число 0). Переведём число 209 в троичную систему (деля и снося остаток справа
налево):
209 = 212023. Произведём обратную замену
и получим УОУАУ.
Ответ: УОУАУ
ПРИМЕР
2 B4 . Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в
алфавитном порядке. Вот начало списка:
1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА
Укажите номер первого слова, которое начинается с
буквы У.
Решение;
Из четырёх букв можно составить 45 = 1024
пятибуквенных слова.
Т. к. слова идут в алфавитном порядке, то первая
часть (256 шт) начинаются с «А»,
вторая
часть (256 шт) – с «К»,
третья часть – с «Р»,
а последняя
часть – с «У», то есть первая буква меняется через 256 слов. Т. е. со слова с
номером
1 + 256 * 3 = 769 первой буквой будет У.
Ответ: 769.
ПРИМЕР
3 B4 Все 4-буквенные слова, составленные из букв М, У, Х, А записаны в
алфавитном порядке и пронумерованы.
Вот начало
списка:
1. АААА 2.
АААМ 3. АААУ 4.
АААХ 5. ААМА
Напишите номер слова ХУХХ
РЕШЕНИЕ.
Пусть букве А
соответствует 0, М—1, У —2 и Х—3.
Тогда данный список слов станет последовательно
записанным рядом чисел в четверичной системе исчисления.
Слово ХУХХ станет числом 3233. Переведём его в
десятичную систему: 3233 = 3 * 43 + 2 * 42 + 3 * 41
+ 3 = 3 * 64 + 2 * 16 + 12 + 3 = 192 + 32 + 15 = 239.
Нужно прибавить 0 (АААА)
поэтому нужный нам номер 239 + 1 = 240.
Ответ: 240.
|