Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления
![]()
|
Еще пример задания (автор – В.В. Путилов):Р-01. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААЛ 4. ААААО 5. ААААШ 6. АААКА …… На каком месте от начала списка стоит слово ШКОЛА? Решение: по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А 0, К 1, Л 2, О 3 и Ш 4 слово ШКОЛА запишется в новом коде так: 413205 переводим это число в десятичную систему: 413205 = 454 + 153 + 352 + 251 = 2710 поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда… Ответ: 2711.
Решение (с помощью программы, С.С. Поляков): программа на языке Python использует модуль itertools: from itertools import product s = list(map(lambda x: ''.join(x), product('АКЛОШ',repeat=5))) print(s.index('ШКОЛА')+1) Ответ: 2711. Решение (с помощью программы, Б.С. Михлин): можно использовать «метод грубой силы» – перебор всех вариантов: 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 print(n,a+b+c+d+e) # отладочная if a+b+c+d+e=='школа': print(n) exit() # выход из Python Ответ: 2711. Еще пример задания:Р-00. Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка: 1. УУУУУ 2. УУУУО 3. УУУУА 4. УУУОУ …… Запишите слово, которое стоит на 240-м месте от начала списка. Решение (2 способ, троичная система, идея М. Густокашина): по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У → 0, О → 1, А → 2): 1. 00000 2. 00001 3. 00002 4. 00010 …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления переведем 239 в троичную систему: 239 = 222123 заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок (0 → У, 1 → О, 2 → А): 22212 АААОА Ответ: АААОА. Решение (с помощью программы, С.С. Поляков): программа на языке 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 Ответ: АААОА. |