Цепочка

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

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

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

Длина цепочки — количество символов в ней; её обычно обозначают вертикальными чертами, например |s|. Чтобы найти длину, считают все символы по одному, включая одинаковые. В цепочке «ааа» три символа, значит, |«ааа»| = 3. Длина нужна, чтобы сравнивать цепочки и описывать результаты действий с ними.

Пустая цепочка — цепочка, в которой нет символов. Её длина равна нулю: считать нечего, поэтому |ε| = 0, где ε обозначает пустую цепочку. Она отличается от цепочки с пробелом: пробел является символом и даёт длину 1. Понятие пустой цепочки позволяет обозначить отсутствие знаков, не добавляя новый символ.

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

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

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

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

При соединении длины складываются: если в первой цепочке m символов, а во второй n, в результате будет m + n символов. Ни один знак не теряется, а новые знаки не возникают, поэтому число мест в результате равно общему числу мест в обеих частях. Например, длины «ко» и «рабль» равны 2 и 5, значит, длина «корабль» равна 7. Это правило помогает заранее проверить подсчёт.

Цепочка может встречаться внутри другой как фрагмент — несколько символов, стоящих рядом и в том же порядке. Чтобы найти фрагмент, сравнивают его первый символ с позициями большой цепочки, а затем проверяют идущие следом знаки. Если все совпали подряд, фрагмент найден; его положение указывают по номеру первого символа. Если порядок или соседство нарушены, совпадения нет, даже когда нужные буквы присутствуют в другом месте.

Основные характеристики цепочек

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

Разбор задач

Задача 1. Для цепочки «информатика» укажите длину и перечислите символы по порядку. Повторяющиеся буквы не нужно объединять: каждая занимает отдельную позицию. Считаем запись слева направо.

1. Пронумеруем символы: и — 1, н — 2, ф — 3, о — 4, р — 5.
2. Продолжим: м — 6, а — 7, т — 8, и — 9, к — 10, а — 11.
3. Выпишем последовательность без перестановок: и, н, ф, о, р, м, а, т, и, к, а.

Ответ: длина равна 11; символы по порядку: и, н, ф, о, р, м, а, т, и, к, а.

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

1. Запишем «ко», а непосредственно за ней — «рабль».
2. Получим цепочку «корабль».
3. В «ко» 2 символа, в «рабль» 5 символов; 2 + 5 = 7.

Ответ: «корабль», длина — 7.

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

1. Запишем символы «программа» по позициям: п(1), р(2), о(3), г(4), р(5), а(6), м(7), м(8), а(9).
2. Проверим пары рядом стоящих знаков: на позициях 5 и 6 стоят р и а.
3. Порядок букв совпадает с фрагментом «ра», значит, он найден; его начало — позиция 5.

Ответ: да, «ра» встречается на позициях 5–6, начинается с позиции 5.

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

Ошибка: считать цепочки с одинаковыми символами одинаковыми, не учитывая порядок. Так происходит, если воспринимать запись как простой набор букв. Но перестановка может изменить и саму последовательность, и её смысл. Проверьте себя: сравните символы в каждой позиции; если хотя бы в одной они различаются, цепочки разные.

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

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

Ошибка: считать пустую цепочку цепочкой длины один. Её путают с пробелом, который на экране может выглядеть как пустое место. Пустая цепочка не содержит ни одного символа и имеет длину 0, а пробел сам является символом и имеет длину 1. Проверьте, записан ли в цепочке конкретный знак пробела: если да, она не пустая.

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

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

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

• Цепочка — упорядоченная последовательность символов.
• Перестановка символов обычно образует другую цепочку.
• Длина цепочки равна числу содержащихся в ней символов.
• Повторяющиеся символы считаются каждый раз.
• При соединении цепочек сохраняется порядок частей.
• Длина результата соединения равна сумме длин исходных цепочек.
• У пустой цепочки длина равна нулю.