Слова по порядку (задача 8)

 

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

 

Рассмотрим типичную задачу ЕГЭ по информатике по теме 8 ("Перебор слов и системы счисления").

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

1. ЛЛЛЛЛ
2. ЛЛЛЛН
3. ЛЛЛЛР
4. ЛЛЛЛТ
5. ЛЛЛНЛ

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

(Задача 7755 с сайта "Решу ЕГЭ".)

В принципе эта задача решается довольно просто. Данные слова можно рассматривать как числа в системе счисления с основанием 4, причем вместо цифры 0 используется буква Л, вместо 1 - Н, вместо 2 - Р и вместо Т - 3. 

Заметим, что под номером 1 стоит число 0, под номером 2 - число 1 и т.д. Таким образом, под номером 150 будет стоять число 149.

Надо перевести число 149 в систему счисления с основанием 4, затем заменить в нем цифру 0 на букву Л, 1 - на Н и т.д. 

Это не так уж сложно сделать вручную, но можно и написать программу для решения подобных задач. 

Напишем две функции на Питоне. Первая будет преобразовывать число в строку символов. Вот её текст:

def num2str(key,n):
    base=len(key)
    s=''
    while n>0:
        s=key[n%base] + s
        n //= base
    return s

Первый параметр - это символьная строка, содержащая "цифры" нашей системы счисления. Для приведенной выше задачи следует написать строку "ЛНРТ".

Второй параметр - это число, которое надо преобразовать в строку с "цифрами" нашей системы счисления. 

Основание системы определятся по длине строки key. 

Мы последовательно находим цифры нашего числа как остатки от его деления на основание системы счисления и добавляем в строку результата символы, стоящие на соответствующих местах в строке key.

Теперь мы можем решить приведенную выше задачу в одну строку (разумеется, не считая самой функции):

print(num2str("ЛНРТ",149))

Программа печатает результат РННН. Так  как по условию слово должно состоять из пяти букв, то слева надо написать "незначащий ноль", т.е. букву Л. Таким образом, правильный ответ - слово ЛРННН.

Вторая функция делает обратную операцию, т.е. преобразует строку в число. Её первый параметр аналогичен первому параметру функции num2str - это символьная строка, содержащая "цифры" нашей системы счисления по порядку. Второй параметр - строка, содержащая число, записанное этими "цифрами".

Функция определяет, на каком месте в строке "цифр" находится очередной символ.  Затем результат умножается на основание системы счисления и к нему прибавляется значение этой цифры.

def str2num(key,s):
    base=len(key)
    n=0
    for i in range(len(s)):
        d=key.find(s[i])
        if d<0: print("Error!")
        n = n*base+d
    return n

С помощью этой функции легко решается, например, такая задача:

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

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

Укажите номер слова УАУАУ.

(Задача 3228 с сайта "Решу ЕГЭ".)

Решение следующее:

print(str2num("АОУ","УАУАУ"))

Результат - число 182. Опять-таки необходимо учесть, что номер, под которым число стоит в списке, на единицу больше, чем значение числа. Таким образом, правильный ответ - 183.

В заключение рассмотрим задачу 8 из варианта 8 с сайта Полякова:

(№ 223) Все 5-буквенные слова, составленные из букв П, О, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

1. ООООО
2. ООООП
3. ООООР
4. ООООТ
5. ОООПО
...

Какое количество слов находятся между словами ТОПОР и РОПОТ (включая эти слова)? 

Решение задачи:

print(str2num("ОПРТ","ТОПОР")-str2num("ОПРТ","РОПОТ")+1)

Ответ: 256.

Пояснение о выражении  str2num("ОПРТ","ТОПОР")-str2num("ОПРТ","РОПОТ")+1.

Если a, b и x - целые числа и a<b, то количество решений двойного неравенства a<x<b есть b-a-1, неравенств a<=x<b и a<x<=b - b-a, а неравенства a<=x<=b - b-a+1.

 

Рекомендация по отладке функций

Если вы будете решать задачу 8 программно, то не лишним будет предварительно убедиться в корректной работе данных функций. Проще всего это сделать в десятичной системе, указав в качестве параметра key строку из десятичных цифр. Функции должны правильно переводить строку в число и наоборот. 

Если вы запустите программу вроде этой:

print(num2str("0123456789",654321))
print(str2num("0123456789","13579")) 

и увидите результат

654321
13579

то скорее всего с функциями всё в порядке.

(c) Ю.Д.Красильников, 2021 г.