Задание 10. Пример задания

Демо 2012

Условие. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

1. ААААА
2. ААААО
3. ААААУ
4. АААОА

……

Запишите слово, которое стоит на 240-м месте от начала списка.

Решение (1 способ):   Определим, сколько 5-буквенных слов можно составить из трех различных букв. Так как на каждой из 5 позиций может стоять любая из 3 букв, то количество слов в списке будет равно  QUOTE    = 243. Значит последнее слово УУУУУ стоит на 243-м месте. На 242-м месте стоит УУУУО, на 241-м месте – УУУУА, а на 240-м месте – УУУОУ.

Ответ: УУУОУ.

Решение (2 способ): Слово в трехбуквенном алфавите можно рассматривать, как запись слова в троичной системе. Чтобы алфавитный порядок соответствовал обычному порядку на натуральных числах, первая по алфавиту буква (у нас – А) должна обозначать 0; вторая (у нас -  О) -  1, третья (у нас У) -  2. При такой записи незначащие нули в начале (слева) тоже записываются. То есть слова в списке представляют числа от 0 до 3⁵ – 1, число N находится в списке на (N+1)-м месте. На 240-м месте в списке стоит число 240-1 = 239. Чтобы понять, какое слово соответствует этому числу, переведем его в 3-чную систему счисления. Получим:   239: 3 = 79 (2 ост); 79:3 = 26 (1 ост); 26:3 = 8 (2 ост); 8:3 = 2 (2ост); 2:3 = 0 (2 ост). Таким образом, 239 = 22212₃. Этому соответствует слово УУУОУ.

Ответ: УУУОУ.

Замечание. Если заданный номер слова близок к началу или концу списка, то первый способ проще. Второй способ более универсален.