"Информатика", Рудченко Т.А., Семёнов А.Л. / Под ред. Семёнова А.Л.
Последовательность — это объекты, расположенные в определённом порядке. Для бусин порядок задаётся их местами в цепочке и направлением просмотра. Поэтому одинаковые по цвету бусины всё равно различаются: у каждой есть собственная позиция. Сравнивая номера позиций, можно определить, какая бусина раньше или позже, найти соседние элементы и восстановить возможный порядок по нескольким условиям. Эти правила нужны при работе со списками, алгоритмами и упорядочиванием данных.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Последовательность — упорядоченный ряд объектов, в котором для каждого объекта важно его место. Например, цепочка бусин образует последовательность, потому что бусины лежат одна за другой. Это понятие нужно, чтобы обсуждать не только свойства объектов, но и их порядок.
Позиция элемента — место объекта в последовательности, обычно обозначаемое номером слева направо. Первой бусине присваивают номер 1, следующей — номер 2 и так далее. Номера помогают точно сравнивать элементы, даже если они выглядят одинаково.
Отношение «раньше—позже» показывает, как расположены два элемента относительно друг друга. Если номер позиции одной бусины меньше номера другой, первая бусина раньше второй. Такое сравнение нужно для описания порядка без неоднозначных слов «ближе» или «дальше».
Повторяющийся элемент — объект того же вида, который встречается в последовательности несколько раз. Каждое его вхождение занимает свою позицию, поэтому две синие бусины нельзя автоматически считать одной. Это позволяет правильно решать задачи, где одинаковые элементы нужно сравнить с другими.
Порядок бусин возникает из их расположения в цепочке и выбранного направления просмотра. Пока мы идём, например, слева направо, каждая следующая бусина считается более поздней. Если направление не задано, слова «раньше» и «позже» могут быть поняты по-разному, поэтому его выбирают до сравнения.
Чтобы определить, какая бусина раньше, нужно сравнить позиции двух бусин, а не только их цвет или форму. Цвет сообщает признак бусины, но не говорит, где она находится. Например, красная бусина может стоять как раньше, так и позже синей, поэтому ответ находят по номерам мест.
Одинаковые бусины нельзя считать одной: каждое их вхождение рассматривается отдельно и имеет собственное место. Если синяя бусина встречается дважды, удобно называть их первой и второй синей бусиной. Такое обозначение сохраняет различие между видом элемента и конкретным местом, которое он занимает.
Если одна бусина раньше второй, а вторая раньше третьей, то первая раньше третьей. Причина в том, что движение по последовательности не может вернуться назад: после первой позиции нужно пройти через вторую, а затем достигнуть третьей. Поэтому часть выводов можно сделать по цепочке отношений, не сравнивая первую и третью бусины непосредственно.
При изменении направления просмотра отношения «раньше» и «позже» меняются местами. Бусина, стоящая левее другой, раньше неё при просмотре слева направо, но позже при просмотре справа налево. Именно поэтому в записи решения полезно явно указать направление и не смешивать две нумерации.
Сначала выберите направление просмотра и пронумеруйте позиции. Затем сравните номера нужных элементов, отдельно различая одинаковые бусины. Таблица помогает связать словесное условие с конкретным способом проверки.
| Ситуация | Что означает | Как определить |
|---|---|---|
| Один элемент раньше другого | Он расположен ближе к началу последовательности | Сравнить номера позиций |
| Один элемент позже другого | Он расположен ближе к концу последовательности | Сравнить номера позиций |
| Элементы занимают соседние позиции | Между ними нет другого элемента | Проверить разность номеров позиций |
| Встречаются одинаковые элементы | Каждое вхождение имеет отдельную позицию | Нумеровать элементы по местам, а не только по названиям |
Задача 1. В цепочке идут красная, синяя, зелёная, синяя и жёлтая бусины. Нужно определить, какая синяя бусина раньше жёлтой и какая позже зелёной. Одинаковый цвет не означает одинаковое место, поэтому сначала выделим оба вхождения синей бусины.
Ответ: жёлтой бусины раньше стоят обе синие; позже зелёной стоит вторая синяя бусина.
Задача 2. Известно: белая бусина раньше чёрной, а чёрная раньше красной. Требуется узнать, какая бусина раньше красной. Здесь не даны номера, но сами отношения образуют последовательную цепочку.
Ответ: белая бусина раньше красной. Это вывод по цепочке отношений.
Задача 3. Жёлтая бусина раньше зелёной, зелёная раньше синей, красная позже жёлтой, но раньше синей. Нужно восстановить возможный порядок. Сначала объединим строгие условия, а затем вставим красную бусину в подходящее место.
Ответ: возможный порядок — жёлтая, красная, зелёная, синяя. Условие допускает и другой вариант: жёлтая, зелёная, красная, синяя.
Считать одинаковые бусины одной бусиной. Так делают, потому что видят общий цвет и не замечают разные места. Проверьте себя: пронумеруйте каждое вхождение отдельно и спросите, можно ли указать его позицию.
Определять «раньше» по цвету или размеру. Признак объекта не задаёт его положение, поэтому такой способ не работает. Проверьте себя сравнением номеров: ответ должен изменяться при перестановке бусин, даже если их цвета сохраняются.
Забывать указать направление просмотра. Без него одна и та же цепочка допускает два противоположных описания порядка. Проверьте себя: подпишите, откуда начинаете счёт, и убедитесь, что все отношения относятся к этому направлению.
Делать вывод по одному косвенному признаку. Отдельное условие может быть совместимо с несколькими расположениями или с другими условиями не совпадать. Проверьте себя: выпишите всю цепочку ограничений и подставьте полученный порядок в каждое из них.
Можно ли считать две одинаковые бусины одной?
Нет, если они встречаются в последовательности в разных местах. Это два вхождения одного вида, и каждое имеет собственную позицию.
Как определить, какая бусина раньше, если они одинакового цвета?
Нужно сначала различить бусины по позициям, например назвать их первой и второй синей бусиной. Затем сравнить номера этих позиций с направлением просмотра.
Что изменится, если рассматривать цепочку справа налево?
Порядок позиций станет обратным. Бусина, которая была раньше при просмотре слева направо, окажется позже при просмотре справа налево.
Можно ли восстановить порядок бусин по нескольким утверждениям?
Да, если перевести утверждения в цепочку ограничений и расставить элементы так, чтобы все условия выполнялись. Иногда возможных порядков бывает несколько.
Как понять, что условия задачи противоречат друг другу?
Постройте цепочку отношений и проверьте, не требуется ли одному элементу быть раньше самого себя. Противоречие также возникает, когда для одной пары указаны взаимоисключающие порядки.
Раньше-позже. Если бусина не одна