Алфавитная цепочка. Слово

Определения и обозначения

Алфавит — конечный упорядоченный набор символов, из которых составляются цепочки. Например, {а, б, в} — маленький алфавит из трёх букв. Он задаёт, какие символы разрешено использовать и в каком порядке их принято записывать.

Алфавитная цепочка — конечная последовательность символов заданного алфавита, где важен порядок следования. Из алфавита {а, б, в} можно получить цепочку «ваб». Это понятие позволяет точно описывать сообщения, коды и другие последовательности знаков.

Слово — алфавитная цепочка, рассматриваемая как единый объект. Оно может иметь обычный смысл, как «ваза», или быть формальным набором символов, как «вба». Так можно изучать строение последовательности независимо от её значения.

Длина слова — количество символов в цепочке, включая повторяющиеся. В слове «абба» четыре символа, поэтому его длина равна 4. Длина нужна, чтобы описывать размер слова и сравнивать цепочки.

Как это устроено

Алфавитную цепочку получают последовательным выбором символов: сначала выбирают знак для первой позиции, затем для второй и так далее. Каждый выбор делают только из заданного алфавита, поэтому посторонний символ использовать нельзя. Например, над алфавитом {а, б, в} цепочка длины 3 строится тремя выборами: по одному символу на каждую позицию.

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

Символы могут повторяться, если условие задачи не вводит запрет. Так появляются цепочки «аа», «аба» и «111», хотя в них используются одинаковые знаки несколько раз. При разрешённых повторах на каждой позиции можно снова выбирать любой символ алфавита, поэтому число вариантов растёт быстрее.

Позиции обычно нумеруют слева направо, начиная с первой: в слове «баба» стоят б₁, а₂, б₃, а₄, если обозначать символы вместе с их местами. Чтобы сравнить две цепочки, смотрят на символы с одинаковыми номерами. Одно различие на любой позиции уже означает, что цепочки не совпадают.

Длина определяется числом позиций, а не смыслом слова и не количеством разных символов. У «дом» длина 3, у «ааа» тоже длина 3, хотя во втором слове различен только один символ. Такое правило позволяет одинаково работать с настоящими словами, кодами и бессмысленными последовательностями.

Основные понятия темы

Сначала найдите в условии заданный алфавит, затем определите допустимые символы и их позиции. Строка «Пример» помогает увидеть понятие в действии, а последняя колонка выделяет правило, которое нельзя забывать.

Если нужно проверить две цепочки, сравнивайте их слева направо и не ограничивайтесь подсчётом одинаковых букв. Для определения длины просто пересчитайте все позиции, включая повторения.

Разбор задач

Задача 1. Для алфавита {а, б, в} записать все слова длины 2 и определить длину слова «авб». Нужно учесть каждый допустимый выбор на первой и второй позиции. Повторение символов не запрещено, поэтому одинаковые буквы также включаем.

1. Для первой позиции по очереди берём а, б и в.
2. Для каждой выбранной первой буквы перебираем а, б и в на второй позиции.
3. Получаем: «аа», «аб», «ав», «ба», «бб», «бв», «ва», «вб», «вв».
4. В слове «авб» считаем три позиции: а, в, б.

Ответ: всего 9 слов: «аа», «аб», «ав», «ба», «бб», «бв», «ва», «вб», «вв»; длина «авб» равна 3.

Задача 2. Определить, одинаковы ли цепочки «абба» и «абба», а также «абба» и «бааб»; указать их длины. Сравниваем не набор букв, а символы на одинаковых местах. Затем отдельно считаем позиции в каждой цепочке.

1. В первой паре все четыре позиции совпадают: а, б, б, а.
2. Во второй паре уже первая позиция различается: а и б.
3. В обеих цепочках по четыре символа, значит, их длины равны 4.

Ответ: «абба» и «абба» совпадают, а «абба» и «бааб» различны; длина каждой цепочки равна 4.

Задача 3. Из символов 0, 1 и 2 составить все слова длины 3, которые начинаются с 1 и заканчиваются 2. Первая и третья позиции уже определены условием. Свободной остаётся только средняя позиция, поэтому нужно перебрать для неё весь алфавит.

1. Записываем шаблон 1 _ 2.
2. Вместо пропуска по очереди ставим 0, 1 и 2.
3. Получаем слова «102», «112» и «122».

Ответ: «102», «112», «122».

Типичные ошибки

Цепочки «аб» и «ба» иногда считают одинаковыми, потому что в них используются одни и те же буквы. Ошибка появляется, если смотреть только на набор символов и забывать о позициях. Проверьте себя сравнением слева направо: уже первая позиция различается.

Повторяющийся символ иногда не считают отдельным элементом длины. Так, длину «ааа» ошибочно принимают за 1, хотя символ стоит в трёх позициях. Для проверки мысленно пронумеруйте все места цепочки.

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

Бессмысленную цепочку иногда объявляют недопустимой, потому что обычное слово должно что-то обозначать. В информатике слово часто является формальным объектом, поэтому смысл не обязателен. Спросите себя, требует ли условие именно русское осмысленное слово или только цепочку данного алфавита.

Связь с другими темами

До этой темы нужно уметь читать и записывать последовательности, различать символы и учитывать их порядок. Эти навыки помогают точно задавать каждую позицию цепочки. Без них легко перепутать перестановку с совпадением.

Алфавитные цепочки подготавливают к изучению кодирования информации. Сообщение в коде также представляют последовательностью символов выбранного алфавита. Поэтому правила о допустимых знаках и порядке нужны при работе с кодами.

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

Что запомнить

• Алфавит задаёт допустимые символы и их порядок.
• Алфавитная цепочка состоит из символов одного заданного алфавита.
• В цепочке важен порядок символов.
• Повторение символов разрешено, если это не запрещено условием.
• Длина слова равна числу символов в нём.
• Одинаковые слова должны иметь одинаковые символы на всех соответствующих позициях.