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

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

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

Количество элемента в мешке — число раз, которое это значение встречается. Например, в мешке {2, 5, 2, 2} количество числа 2 равно 3, а числа 5 — 1. Подсчёт помогает точно описать состав мешка и не потерять одинаковые элементы.

Таблица для мешка — запись, где каждому различному значению соответствует его количество. Обычно в ней есть столбцы «Элемент» и «Количество». Она нужна, чтобы представить мешок короче и удобнее проверять, сравнивать или изменять его состав.

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

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

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

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

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

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

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

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

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

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

Эта таблица описывает мешок, в котором два яблока, одна груша и три сливы. Чтобы восстановить мешок, нужно повторить каждое значение указанное число раз, но порядок при этом можно выбрать любой. Для проверки сложите количества: 2 + 1 + 3 = 6, значит, в мешке шесть элементов.

Разбор задач

Задача. Дан мешок {4, 7, 4, 2, 7, 4, 9, 2}. Нужно составить таблицу для мешка, определить его размер и выяснить, равен ли он мешку {2, 4, 7, 9, 4, 2, 7, 4}. Важно не сравнивать записи по расположению чисел: сначала требуется узнать, сколько раз встречается каждое значение. Для наглядности строки таблицы расположим по возрастанию.

1. Выпишем разные значения: 2, 4, 7 и 9. Других чисел в записи нет, поэтому именно для них будут строки таблицы. Сначала ищем не порядок, а полный набор различных значений.
2. Посчитаем число 2: оно стоит на третьем и восьмом местах, значит, его количество равно 2. Число 4 встречается на первом, третьем и шестом местах? Проверяем исходную запись по позициям: 4 стоит на первом, третьем и шестом местах, поэтому его количество равно 3. При таком подсчёте полезно отмечать уже учтённые появления.
3. Посчитаем оставшиеся значения: 7 встречается два раза, а 9 — один раз. Запишем пары «значение — количество»: 2 — 2, 4 — 3, 7 — 2, 9 — 1. Каждому значению соответствует только одна строка.
4. Найдём размер мешка: сложим количества, 2 + 3 + 2 + 1 = 8. Результат совпадает с числом элементов в исходной записи, что подтверждает правильность подсчёта. Если бы сумма оказалась другой, следовало бы проверить каждую строку.
5. Сравним мешки по количеству каждого числа. Во второй записи число 2 встречается дважды, 4 — трижды, 7 — дважды, 9 — один раз. Все количества совпадают, значит, мешки равны, хотя элементы в них записаны в разном порядке.

Ответ. Таблица содержит строки: 2 — 2, 4 — 3, 7 — 2, 9 — 1; размер мешка равен 8. Два заданных мешка равны, потому что количество каждого значения в них одинаково. Перестановка элементов не меняет состав мешка.

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

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

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

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

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

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

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

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

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