Тема 8 разбор. Кодирование данных, комбинаторика, системы счисления

• Название: Кодирование данных, комбинаторика, системы счисления
• Анкор: Тема 8 разбор
• Дата: 08.04.2023
• Размер: 327 Kb.
• Имя файла: ege8 (1).doc
• Тип: Документы; #1047035
• страница: 7 из 10

Еще пример задания (автор – В.В. Путилов):

Р-01. Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААК

3. ААААЛ

4. ААААО

5. ААААШ

6. АААКА

……

На каком месте от начала списка стоит слово ШКОЛА?

Решение:

1. 
   по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А  0, К  1, Л  2, О  3 и Ш  4
   
2. 
   слово ШКОЛА запишется в новом коде так: 41320₅
   
3. 
   переводим это число в десятичную систему:
   

41320₅ = 45⁴ + 15³ + 35² + 25¹ = 2710

4. 
   поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…
   
5. 
   Ответ: 2711.
   

Возможные ловушки и проблемы: нужно помнить, что список в задании начинается с 1, а числа в троичной системе – с нуля, поэтому для получения N-ой по счёту цепочки нужно переводить в троичную систему число N-1.

Решение (с помощью программы, С.С. Поляков):

12. 
    программа на языке Python использует модуль itertools:
    

from itertools import product

s = list(map(lambda x: ''.join(x), product('АКЛОШ',repeat=5)))

print(s.index('ШКОЛА')+1)

13. 
    Ответ: 2711.
    

Решение (с помощью программы, Б.С. Михлин):

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

print(n,a+b+c+d+e) # отладочная

if a+b+c+d+e=='школа':

print(n)

exit() # выход из Python

2. 
   Ответ: 2711.
   

Еще пример задания:

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

1. УУУУУ

2. УУУУО

3. УУУУА

4. УУУОУ

……

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

Решение (2 способ, троичная система, идея М. Густокашина):

1. 
   по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)
   
2. 
   выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У → 0, О → 1, А → 2):
   

1. 00000

2. 00001

3. 00002

4. 00010

……

3. 
   это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.
   
4. 
   тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления
   
5. 
   переведем 239 в троичную систему: 239 = 22212₃
   
6. 
   заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок (0 → У, 1 → О, 2 → А): 22212  АААОА
   
7. 
   Ответ: АААОА.
   

Решение (с помощью программы, С.С. Поляков):

1. 
   программа на языке Python использует модуль itertools:
   

from itertools import product

print( *list(product('УОА',repeat=5))[240-1] )

2. 
   Ответ: АААОА.
   

Решение (с помощью программы, Б.С. Михлин):

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

2. 
   Ответ: АААОА.