Цепочка цепочек

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

Цепочка — упорядоченный набор объектов, в котором каждому объекту соответствует своё место. Порядок здесь не случаен: перестановка объектов изменит саму цепочку. Это понятие нужно, чтобы различать не просто набор предметов, а последовательность с определёнными позициями.

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

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

Таблица — представление цепочки цепочек в виде строк и столбцов. Каждая строка может быть внутренней цепочкой, а её столбцы — элементами этой цепочки. Такое представление помогает одновременно видеть порядок строк и положение объектов внутри строки.

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

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

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

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

Чтобы найти элемент цепочки цепочек, нужны два признака: номер внутренней цепочки и номер элемента в ней. Сначала по первому номеру выбирают нужную строку или список, а затем по второму находят объект внутри выбранной цепочки. Например, запись (3; 2) означает второй элемент третьей внутренней цепочки. Если перепутать номера, будет выбран другой объект, даже если оба номера сами по себе допустимы.

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

Представление цепочек и цепочек цепочек

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

Разбор задач

Задача 1

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

1. Запишем элементы по порядку и сохраним их номера: 1 — понедельник, 2 — вторник, 3 — среда, 4 — четверг.
2. Выберем позицию с номером 4, потому что именно она указана в условии.
3. Проверим, что номер выбранного объекта совпадает с его местом в цепочке.

Ответ: на четвёртом месте находится «четверг», его номер — 4.

Задача 2

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

1. Первую строку превращаем в цепочку [красный, жёлтый], вторую — в цепочку [круг, квадрат].
2. Объединяем их в заданном порядке: [[красный, жёлтый], [круг, квадрат]]. Это цепочка цепочек.
3. Для восстановления таблицы берём первую внутреннюю цепочку как первую строку, а вторую — как вторую строку, не меняя порядок элементов.

Ответ: цепочка цепочек — [[красный, жёлтый], [круг, квадрат]], а восстановленная таблица снова содержит эти две строки.

Задача 3

Условие. Дана цепочка цепочек: [[а, б, в], [г], [д, е]]. Найдите элемент по номеру внутренней цепочки и его номеру либо установите, что такого элемента нет. Рассмотрим обращение (3; 2), то есть второй элемент третьей цепочки.

1. По первому номеру 3 выбираем третью внутреннюю цепочку [д, е].
2. Смотрим на её длину: в ней два элемента, поэтому номер 2 допустим.
3. На второй позиции этой цепочки стоит е. Если бы был запрошен элемент (2; 2), его бы не существовало, потому что вторая цепочка состоит только из одного элемента.

Ответ: элемент (3; 2) — «е»; обращение (2; 2) было бы недопустимым.

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

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

Считают, что элемент цепочки цепочек обязан быть числом или словом. На самом деле таким элементом может быть целая цепочка, например строка таблицы. Чтобы проверить ответ, спросите: можно ли раскрыть выбранный элемент и увидеть внутри несколько объектов?

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

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

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

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

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

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

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

• Цепочка задаёт порядок объектов.
• Каждый элемент цепочки имеет своё место.
• В цепочке цепочек элементом является другая цепочка.
• Таблица может быть представлена как цепочка строк-цепочек.
• Для нахождения элемента обычно нужны два номера.
• Внутренние цепочки могут иметь разную длину.
• При обращении к элементу нужно учитывать оба уровня структуры.