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