Сложение мешков. Мощность мешка

Определения и обозначения

Мешок — совокупность объектов, в которой порядок элементов не важен, но одинаковые элементы могут повторяться. Например, записи {а, б, а} и {а, а, б} обозначают один мешок. Такое понятие нужно, когда требуется хранить не только разные виды объектов, но и число объектов каждого вида.

Элемент мешка — отдельный объект, входящий в мешок; одинаковые элементы считаются разными вхождениями. В записи {а, а, б} есть два вхождения элемента а и одно вхождение б. Это различие нужно, чтобы не потерять количество одинаковых объектов при подсчёте.

Сложение мешков — объединение содержимого двух мешков с сохранением всех элементов и их повторений. Чтобы получить сумму, берут каждый элемент первого мешка и каждый элемент второго, не удаляя совпадения. Операция помогает собрать два набора данных в один, сохранив их полный состав.

Мощность мешка — количество всех его элементов, включая повторяющиеся. Её можно записать как число элементов мешка или обозначить, например, |A| для мешка A. Мощность нужна, чтобы узнать общий размер набора, а не только количество разных видов элементов.

Как это устроено

Мешок отличается от множества тем, что в нём сохраняются повторы. Если в мешке лежат три одинаковых предмета, каждый из них важен для общего количества, хотя названия у них совпадают. Порядок же не учитывают, потому что перестановка предметов не меняет состав набора. Поэтому при описании мешка смотрят на то, какие объекты и сколько раз встретились.

Чтобы сложить два мешка, выпиши подряд содержимое первого и второго, сохранив каждое вхождение. Ничего не нужно удалять или сопоставлять: совпадающие элементы тоже переносятся оба раза. Например, в {а, б} + {б, в, в} элемент б появится дважды, поскольку по одному его вхождению пришло из каждого мешка. Получившийся мешок можно записать в любом порядке.

Мощность суммы равна сумме мощностей слагаемых, потому что при сложении учитывается каждый элемент обоих мешков. Если в первом мешке 3 элемента, а во втором 4, то в результате будет 3 + 4 = 7 элементов. Совпадающие элементы не исчезают, поэтому вычитать их или считать только разные названия не нужно. Это правило позволяет быстро найти размер результата, даже не выписывая его целиком.

Мощность по записи находят подсчётом всех элементов, включая повторы. Чтобы определить число вхождений конкретного элемента, например вхождений г, считают только записи г, но из каждого слагаемого. Эти два подсчёта отвечают на разные вопросы: мощность показывает размер всего мешка, а число вхождений — сколько раз встречается выбранный элемент. Полезно сначала определить, что именно требуется в задаче.

Пустой мешок не содержит элементов, поэтому при сложении к другому мешку нечего добавлять. Его мощность равна 0, и сумма A + пустой мешок имеет тот же состав, что и A. Это похоже на прибавление нуля к числу: значение не меняется. Такое свойство удобно, когда один из наборов данных оказался пустым.

Основные свойства мешков и их сложения

Пользуйся таблицей, чтобы быстро определить, что сохраняется при сложении и как считать мощность. Сначала выясни, требуется ли размер всего мешка или количество конкретного элемента. Затем проверь, что все повторы учтены.

Разбор задач

Задача 1. Определить мощность мешка {красный, синий, красный, зелёный}. Нужно посчитать все элементы, не исключая повторяющийся красный. Названия цветов здесь обозначают элементы, а не виды, которые следует посчитать только по одному разу.

1. Перечислим вхождения по порядку: красный, синий, красный, зелёный. В записи четыре позиции.
2. Учтём оба вхождения красного, потому что каждое из них считается отдельным элементом мешка.
3. Запишем общее количество: 4. Значит, мощность мешка равна 4.

Ответ: 4.

Задача 2. Вычислить сумму мешков {1, 1, 3} и {1, 2, 3, 3}, а затем найти её мощность. В первом мешке 3 элемента, во втором — 4. При составлении результата одинаковые числа останутся столько раз, сколько они встретились в обоих мешках вместе.

1. Выпишем элементы первого мешка: 1, 1, 3. Затем добавим все элементы второго: 1, 2, 3, 3.
2. Получим общий мешок {1, 1, 3, 1, 2, 3, 3}. Порядок можно изменить, но ни одно вхождение удалять нельзя.
3. Сложим мощности слагаемых: 3 + 4 = 7. Проверка по записи результата тоже даёт семь элементов.

Ответ: {1, 1, 3, 1, 2, 3, 3}; мощность равна 7.

Задача 3. Даны мешки A = {а, а, б, в}, B = {а, в, в, г, г} и C = {б, г}. Найти A + B + C, мощность результата и число вхождений элемента г. Чтобы не пропустить элементы, сначала объединим мешки последовательно, а затем отдельно подсчитаем общую мощность и вхождения г.

1. Запишем все элементы A, затем добавим B и C: {а, а, б, в, а, в, в, г, г, б, г}. Здесь повторения сохранены.
2. В A четыре элемента, в B пять, в C два. Поэтому мощность результата равна 4 + 5 + 2 = 11.
3. Посчитаем г отдельно: два вхождения находятся в B и одно — в C, в A таких элементов нет. Всего получается три вхождения г.

Ответ: A + B + C = {а, а, б, в, а, в, в, г, г, б, г}; мощность 11; элемент г встречается 3 раза.

Типичные ошибки

Первая ошибка — удалять повторы, принимая мешок за множество. Так делают, если считают, что одинаковые названия обязательно должны быть записаны только один раз; проверь себя, спросив, каждое ли вхождение из исходной записи перенесено в ответ. Если нет, состав мешка изменился.

Вторая ошибка — считать одинаковые элементы только один раз при нахождении мощности. Обычно внимание сосредотачивается на разных видах объектов, но мощность показывает общее число вхождений. Пересчитай позиции в записи по одной: их число и есть мощность, даже если несколько позиций содержат одинаковый элемент.

Третья ошибка — считать порядок элементов важным. Из-за привычки читать запись слева направо можно решить, что перестановка создаёт другой мешок. Для проверки переставь элементы местами и сравни, сохранились ли все вхождения; если да, мешок тот же.

Четвёртая ошибка — при сложении забыть перенести часть одного мешка или объединить одинаковые элементы в один. Это происходит, когда результат составляют по видам элементов, а не по вхождениям. Проверь сумму подсчётом: число элементов в ней должно быть равно сумме мощностей слагаемых.

Связь с другими темами

Для работы с мешками пригодятся понятия множества, элемента и принадлежности, а также навык подсчёта объектов. Мешок расширяет привычную идею набора: он позволяет учитывать не только наличие элемента, но и число его повторений. Это полезно при описании наборов данных и подсчёте повторяющихся объектов.

В алгоритмах мешки помогают рассуждать о коллекциях, в которых могут быть одинаковые значения, например о списке оценок или наборе товаров. Позже такие представления пригодятся при изучении алгоритмов обработки данных и операций над коллекциями. Правила сложения позволяют объединять данные, не теряя повторов.

Что запомнить

• В мешке порядок элементов не важен.
• В мешке одинаковые элементы могут повторяться.
• Сложение мешков сохраняет все элементы обоих мешков.
• При сложении мешков повторы не уничтожаются.
• Мощность мешка — число всех его элементов.
• Мощность суммы мешков равна сумме их мощностей.
• Пустой мешок имеет мощность 0 и не изменяет другой мешок при сложении.