Все в порядке

Алфавит языка рассматривается как упорядоченное множество. Это означает, что задается, какой символ является первым, какой последним, и для каждого символа указывается, какой символ следует за ним в алфавите. В Кириллице буквы упорядочены от "а" до "я", в Латинице – от "a" до "z".

Порядок на алфавите порождает порядок на словах, называемый словарным или лексикографическим порядком. Это тот порядок, в котором располагаются слова в словаре. Такой порядок можно строго определить. Рассмотрим слово s. Назовем префиксом слова – начальный отрезок слова, а корнем слова – часть слова, следующую за префиксом. Любое слово s можно представить в виде пары <p, r>, где p – префикс, а r – корень. Например, слово "паспорт" можно представить в виде <па, спорт> или < пас, порт>. При таком разбиении как префикс так и корень может быть пустым словом.

Рассмотрим теперь два слова s₁ и s₂. Пусть p – максимальный общий префикс этих слов (если слова начинаются разными символами, то таким префиксом является пустое слово). Тогда слова s₁ и s₂ можно представить в виде пар <p, r1> и <p, r2>.

Слово s₁ предшествует слову s₂ в словарном порядке, если выполняется одно из двух условий:

Задача: расположите в словарном порядке слова (парус, пар и паровоз).

Ответ: У этих слов общий максимальный префикс – "пар". Поэтому в словаре первым будет идти слово "пар" (у него корень – пустое слово). Слово "паровоз" предшествует слову "парус", поскольку буква "о" предшествует в алфавите букве "у".

Задача 11:

Алфавит состоит из 4-х букв {М, У, Х, А} Слова длины 5 перечисляются в лексикографическом порядке. Нумерация слов начинается с единицы. Какое слово в этом перечислении стоит под номером 1016, под номером 365?

Ответ: ХХХМХ; ММУХА

Решение: Число различных слов длины 5 в 4-х буквенном алфавите равно 45 = 210 = 1024. При перечислении их в алфавитном (лексикографическом) порядке под номером 1 стоит слово ААААА, под номером 1024 – слово ХХХХХ. В задачах экзамена ЕГЭ обычно требуется указать слово, стоящее близко к концу перечисления, что имеет место в нашей задаче, в которой требуется назвать слово под номером 1016, стоящее в первом десятке с конца перечисления. Поэтому для решения задачи достаточно выписать десять слов в обратном лексикографическом порядке, что и дает слово ХХХМХ.

Для ответа на второй вопрос, где требуется найти слово, стоящее в середине перечисления, такой явный способ выписывания слов не подходит. В этом случае следует применять более общий подход, применимый для всех случаев. Для его понимания нужно вспомнить системы счисления.

Поставим в соответствие буквам алфавита цифры (А – 0, М – 1, У – 2, Х -3). При задании этого соответствия учитывается принятый порядок следования букв в алфавите. Число букв задает число используемых цифр, а тем самым задает основание системы счисления. Введенное соответствие букв и цифр порождает соответствие между словами в алфавите и числами в соответствующей системе счисления, в нашем случае – четверичной системе счисления. При лексикографическом перечислении слов длины k слову, стоящему под номером N, соответствует число N-1 в четверичной системе счисления, содержащее k цифр, включая незначащие нули. Так, слову под номером 1, состоящему из 5 букв, соответствует число 0, записанное как 00000, или, после замены цифр буквами, - ААААА. Поэтому для решения задачи, зная N, достаточно получить запись числа N-1 в четверичной системе, а затем заменить цифры буквами.

Получим решение задачи этим способом для N = 1016 и N = 365.

N - 1 = 1015 = 3* 4⁴ + 3* 4³ +3* 4² + 1* 4¹ + 3 = 33313₄ = ХХХМХ

N -1 = 364 = 1* 4⁴ + 1* 4³ +2* 4² +3* 4¹ + 0 = 112304 = ММУХА

Задача 12:

Алфавит состоит из 3-х букв {А,М, П} Слова длины 4 перечисляются в лексикографическом порядке. Нумерация слов начинается с единицы. Под каким номером стоит слово МАМА, слово - ПАПА?

Решение: В троичной системе слову МАМА соответствует число 10103 = 33 + 3 = 30. В перечислении, где нумерация начинается с 1, номер этого слова равен 31.

Слову ПАПА соответствует число 2020₃ = 60.

Задача 1

Общий максимальный префикс

Задача 2

Расположить в словарном порядке

Задача 3

Алфавит из трех букв. Какое слово длины 3 стоит на i-м месте

Задача 4

Алфавит из трех букв. Какое слово длины 4 стоит на i-м месте

Задача 5

Алфавит из четырех букв. Какое слово длины 3 стоит на i-м месте

Задача 6

Алфавит из четырех букв. Какое слово длины 4 стоит на i-м месте

Задача 7

Алфавит из 3-х букв. Каков порядковый номер слова ??? среди слов длины

Задача 8

Алфавит из 4-х букв. Каков порядковый номер слова ??? среди слов длины

Задача 9

Алфавит из 5-и букв. Каков порядковый номер слова ??? среди слов длины