Лаб_1. Программах. Термин представление еще употребляют термин реализация
 Скачать 28.5 Kb.
|
|
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1. Представление множеств в ЭВМ. Реализация операций над подмножествами заданного универсума. Цель занятия: Изучение реализации операций над подмножествами заданного универсума. Теоретические сведения. Рассматривается представление множеств в программах. Термин «представление» (еще употребляют термин «реализация») применительно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) - значит описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции. Предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций. Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других - другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т.д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий. Реализация операций над подмножествами заданного универсума U. Пусть универсум U — конечный, и число элементов в нем не превосходит разрядности ЭВМ:  . Элементы универсума нумеруются:  . Подмножество А универсума U представляется кодом (машинным словом или битовой шкалой) С, в котором: где  - это i-й разряд кода С.Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно. Порядок выполнения работы. Для реализации операций над подмножествами заданного универсума подготовить конечные множества A и B. Составить программу для нахождения пересечения, объединения, дополнения множеств А и В. Дать обоснование полученного решения. |