Решение задач В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 |
2 |
|
69 |
0 |
|
23 |
2 |
|
7 |
1 |
|
2 |
|
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.
