Длина цепочки

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

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

Элемент цепочки — один объект, занимающий определённое место в цепочке. Если одинаковая буква встречается дважды, это два разных элемента, потому что они находятся на разных местах. Такое уточнение помогает правильно считать цепочку «ААБ».

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

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

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

Длину находят последовательным подсчётом всех элементов от первого до последнего. Каждый шаг счёта соответствует одному занятому месту в цепочке. Повторение не даёт права пропустить элемент: в «ААА» три позиции и длина 3. Поэтому нужно считать не разные значения, а все вхождения элементов.

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

Если к цепочке приписать один новый элемент, появляется ровно одно дополнительное место. Все прежние элементы остаются на своих местах, поэтому к прежнему количеству прибавляется единица. Так, после добавления буквы к цепочке длины 4 получается цепочка длины 5. Это правило действует независимо от того, совпадает новый элемент с уже имеющимся или нет.

При соединении двух цепочек сначала идут все элементы первой, затем все элементы второй. В результате ни один элемент не исчезает и не повторяется дополнительно из-за самого соединения. Поэтому можно отдельно посчитать элементы каждой части и сложить результаты: длина соединённой цепочки равна сумме длин. Например, цепочки длины 2 и 5 образуют цепочку длины 7.

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

Цепочки и их длина

Пользуйтесь таблицей так: сначала найдите все элементы цепочки, затем посчитайте их количество. В строке «ААБ» видно, что одинаковая буква учитывается дважды. Кавычки вокруг записи служат для обозначения цепочки и сами в подсчёт не входят.

Разбор задач

Задача 1. Определить длину цепочки «ИНФОРМАТИКА». Нужно учесть каждый символ, в том числе повторяющиеся буквы. Кавычки обозначают запись цепочки и не считаются её элементами.

1. Перечислим символы по порядку: И, Н, Ф, О, Р, М, А, Т, И, К, А.
2. Сосчитаем их: получилось 11 символов.
3. Повторяющиеся И и А не удаляем, потому что они занимают отдельные места.

Ответ: длина цепочки «ИНФОРМАТИКА» равна 11.

Задача 2. Сравнить длины цепочек «АБВГ» и «ГВБА». На первый взгляд записи отличаются, но для длины важен только подсчёт элементов. Порядок понадобится для различения самих цепочек, а не для определения их размера.

1. В первой цепочке четыре элемента: А, Б, В, Г.
2. Во второй цепочке тоже четыре элемента: Г, В, Б, А.
3. Сравним полученные числа: 4 = 4.

Ответ: цепочки имеют одинаковую длину — 4; ни одна не длиннее другой.

Задача 3. Цепочка «КОТ» имеет длину 3, а цепочка «ДОМ» — длину 3. Их приписали одну к другой. Требуется найти длину результата, не пересчитывая всю новую запись вручную.

1. При соединении сохраняются все элементы первой цепочки и все элементы второй.
2. Сложим длины частей: 3 + 3 = 6.
3. Проверка по записи «КОТДОМ» также даёт шесть символов.

Ответ: длина получившейся цепочки равна 6.

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

Не считать повторяющиеся элементы. Так происходит, когда длину путают с количеством разных элементов: в «ААБ» оставляют только А и Б. Для проверки отметьте каждое место цепочки отдельным счётом, даже если значения совпадают.

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

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

Забывать о длине пустой цепочки. Иногда отсутствие записи принимают за один невидимый элемент. Спросите себя, есть ли что считать: если элементов нет, длина равна 0.

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

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

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

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

• Длина цепочки — это число её элементов.
• Каждый элемент считается отдельно, даже если он повторяется.
• Порядок элементов меняет цепочку, но не её длину.
• Длина пустой цепочки равна 0.
• При добавлении одного элемента длина увеличивается на 1.
• При соединении двух цепочек их длины складываются.