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