Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления
![]()
|
Ещё пример задания:Р-02. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 240-м месте от начала списка. Решение (1 способ, перебор с конца): подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв; очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 33=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ) аналогично можно показать, что есть всего 35 = 243 слова из 5 букв очевидно, что последнее, 243-е слово – это УУУУУ далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е) Ответ: УУУОУ.
Решение (2 способ, троичная система, идея М. Густокашина): по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) выпишем начало списка, заменив буквы на цифры: 1. 00000 2. 00001 3. 00002 4. 00010 …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления переведем 239 в троичную систему: 239 = 222123 заменяем обратно цифры на буквы: 22212 УУУОУ Ответ: УУУОУ.
Решение (3 способ, закономерности в чередовании букв, И.Б. Курбанова): подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв:
так как слова стоят в алфавитном порядке, то первая треть (81 шт) начинаются с «А», вторая треть (тоже 81) – с «О», а последняя треть – с «У», то есть первая буква меняется через 81 слово аналогично: 2-я буква меняется через 81/3 = 27 слов; 3-я буква – через 27/3 = 9 слов; 4-я буква – через 9/3 = 3 слова и 5-я буква меняется в каждой строке. из этой закономерности ясно, что на первой позиции в искомом слове будет буква «У» (последние 81 букв); на второй – тоже буква «У» (последние 27 букв); на третьей – тоже буква «У» (последние 9 букв); на четвертой – буква «О» (т.к. последние три буквы «У», а перед ними 3 буквы «О»)% на пятой – буква «У» (т.к. последние 3 буквы чередуются «А», «О», «У», а перед ними такая же последовательность). Ответ: УУУОУ. Решение (с помощью программы, А.Н. Носкин): на компьютерном ЕГЭ можно использовать программу (язык Python): a = ["А", "О", "У"] # буквы А, О, У в алфавитном порядке s = "" # строка для формирования ответа x = 239 # числовой код слова: 240-1 = 239 while x > 0: # перевод в троичную систему счисления s += str(x%3) x //= 3 s = s[::-1] # реверс строки ответа for x in s: # формирование СЛОВА i = int(x) print( a[i], end="" ) Ответ: УУУОУ. Решение (с помощью программы, С.С. Поляков): программа на языке Python использует модуль itertools: from itertools import product print( *list(product('АОУ',repeat=5))[240-1] ) Ответ: УУУОУ. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: from sys import exit n=0 s='аоу' for a in s: for b in s: for c in s: for d in s: for e in s: n+=1 if n==240: print(a+b+c+d+e) exit() # выход из Python Ответ: УУУОУ. |