Таблица для мешка

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

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

Элемент мешка — объект или значение, которое входит в мешок. Разные предметы могут совпадать по значению: две красные фишки — разные предметы, но при подсчёте по цвету это два элемента со значением «красный». Такое уточнение помогает понять, что именно мы объединяем в одну группу.

Кратность элемента — число его вхождений в мешок. Если красный цвет встречается четыре раза, его кратность равна 4. Кратность нужна, чтобы показать повторения, не перечисляя каждый одинаковый элемент отдельно.

Таблица для мешка — способ записи мешка, в котором каждому различному элементу соответствует строка с указанием его кратности. В таблице для цветов достаточно одной строки для каждого цвета, даже если фишек такого цвета несколько. Такая запись делает состав набора компактным и позволяет быстро выполнять подсчёты.

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

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

Чтобы составить таблицу по перечню, сначала находят все разные значения. Затем каждое значение записывают один раз и считают, сколько раз оно встретилось в исходном перечне. Например, при подсчёте цветов удобно отмечать уже учтённые элементы, чтобы не посчитать их повторно. Так таблица сохраняет состав мешка, хотя сам перечень становится короче.

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

Восстановить мешок по таблице можно, повторив каждый элемент указанное число раз. Если у значения «синий» кратность 2, в мешок нужно включить два синих элемента; если кратность равна 1 — один. Такой способ работает, потому что таблица хранит все сведения о составе мешка: перечень разных значений и количество каждого из них. Порядок восстановленных записей можно выбрать любой.

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

Как читать таблицу для мешка

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

Разбор задач

Составляем таблицу по перечню

Задача. Для мешка {красный, синий, красный, зелёный, синий, красный} составьте таблицу. Нужно не сохранять порядок исходного перечня, а выделить разные значения и выяснить, сколько раз каждое встречается. После подсчёта проверим, что учтены все шесть записей.

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

Ответ: красный — 3, синий — 2, зелёный — 1.

Читаем таблицу фруктов

Задача. По таблице «яблоко — 3, груша — 2, слива — 1» определите общее число фруктов и сколько раз встречается груша. Вопрос состоит из двух частей: нужно найти одну конкретную кратность и подсчитать весь набор. Для общего количества следует учесть каждую строку, а не только груши.

1. Находим строку «груша»: указанная рядом кратность равна 2. Значит, в мешке две груши.
2. Складываем кратности всех фруктов: 3 + 2 + 1 = 6. Каждое слагаемое учитывает отдельную группу фруктов, поэтому сумма даёт число предметов во всём мешке.

Ответ: всего 6 фруктов, груша встречается 2 раза.

Меняем кратности после действий

Задача. В мешке было 4 красных и 2 синих фишки. Добавили одну синюю, затем убрали две красных; запишите новую таблицу и найдите общее число фишек. Удобно выполнять действия по очереди, меняя только кратность того цвета, с которым работают. Так меньше вероятность ошибиться и затронуть другой элемент.

1. В начале таблица такая: красный — 4, синий — 2. Добавление синей фишки увеличивает только синюю кратность: 2 + 1 = 3.
2. Затем убирают две красные фишки: 4 − 2 = 2. Красная кратность остаётся положительной, значит, строку «красный» сохраняем.
3. Записываем новую таблицу: красный — 2, синий — 3. Складываем кратности: 2 + 3 = 5.

Ответ: красный — 2, синий — 3; всего 5 фишек.

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

Считать, что порядок важен. Так ошибаются, когда переносят на мешок правила работы со списком. Но перестановка не меняет количество элементов каждого вида. Проверь себя: сравни составы, а не последовательность слов или предметов.

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

Путать кратность и общее число элементов. Кратность относится к одному значению, а общее количество — ко всему мешку. Ошибка возникает, когда число из одной строки принимают за размер всего набора. Для проверки сложи кратности каждой строки.

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

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

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

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

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