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