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