Основы дискретной математики

57) В массив заданного размера N (от 3 до 10) ввести произвольные числа. Не изменяя состояния этого массива и используя лишь один дополнительный массив, напечатать номера элементов исходного массива, соответствующие порядку убывания значений элементов. При вводе данных осуществить проверку.

58) В два одномерных массива одинакового размера N (N – заданное натуральное число) ввести произвольн

ые числа. Не изменяя исходных массивов, сформировать из элементов первого массива третий массив так, чтобы максимальный элемент первого массива в третьем находился на месте, соответствующем расположению максимального во втором, а каждый очередной по убыванию элемент из первого массива располагался в третьем на месте, соответствующем расположению очередного по убыванию элемента второго массива. Напечатать все три массива.

59) Напечатать в возрастающем порядке все четырехзначные натуральные числа, все цифры которых являются соседями в натуральном ряду. Примерами таких чисел являются 4756 и 7645. Найти количество и среднее арифметическое этих чисел.

60) Ввести числовую матрицу размером NxM (N, M заданы). Найти максимальный элемент среди расположенных в тех строках матрицы, которые являются упорядоченными (либо по возрастанию, либо по убыванию), или сообщить, что такого элемента нет.

1.4 Вопросы для самопроверки

1) Какими свойствами обладает отношение частичного порядка? Приведите примеры этого отношения.

2) Дайте определение отношения линейного порядка.

3) Сформулируйте постановку задачи сортировки.

4) В чём заключается преимущество отсортированных (упорядоченных) данных?

5) Как рассматривается задача сортировки с точки зрения программирования?

6) От каких факторов зависит эффективность алгоритма сортировки?

7) Перечислите наиболее часто используемые на практике методы поиска и сортировки.

8) Каким образом могут быть представлены данные при поиске и сортировке?

9) Перечислите основные операции при работе с данными.

10) В чём заключается алгоритм линейного поиска?

11) В чём заключается алгоритм бинарного поиска?

12) Опишите кратко поиск в бинарных деревьях.

13) Какие функции используются при оценке времени исполнения алгоритма?

14) В чём заключается метод сортировки вставками?

15) В чём заключается метод сортировки с помощью включения, прямого включения?

16) В чём заключается метод Шелла?

17) Опишите сортировку с помощью обменов.

18) Опишите алгоритм быстрой сортировки, предложенный Ч. Хоаром (QuickSort).

Практическая работа № 2. Представление множеств в компьютере

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

2.1 Теоретическая часть

2.1.1 Множества и операции над ними

Множество – это совокупность объектов, называемых элементами множества. Например:

• {Эссекс, Йоркшир, Девон};

• {2, 3, 5, 7, 11}.

В этом примере элементы каждого множества заключены в фигурные скобки. Чтобы обеспечить возможность ссылок, мы будем обозначать множества прописными латинскими буквами. Например,

S = {3, 2, 11, 5, 7} – множество, содержащее целые числа. Заметим, что множество S совпадает с одним из множеств, выписанных выше, поскольку порядок, в котором записываются элементы множества, значения не имеет.

В общем случае запись аS означает, что объект а – элемент множества S. Часто говорят, что а принадлежит множеству S. Если объект а не принадлежит S, то пишут: аS.

В современных языках программирования требуется, чтобы переменные объявлялись как принадлежащие к определенному типу данных. Тип данных представляет собой множество объектов со списком стандартных операций над ними. Определение типа переменных равносильно указанию множества, из которого переменным присваиваются значения [22].

Существует несколько способов конструирования нового множества из двух данных. Опишем коротко эти операции на множествах. Прежде всего, отметим, что все элементы некоторых множеств принадлежали другим большим множествам. Например, все элементы множества С = {0, 1, 4, 9, 16,…} содержатся в множестве

Z = {0, ±1, ±2, ±3,…}.

Рисунок 2.1 – Диаграмма Венна подмножества А S

Объединением двух множеств А и В называется множество

АВ = {х: х А или х В}.

Оно состоит из тех элементов, которые принадлежат либо множеству A, либо множеству В, а возможно и обоим сразу. Диаграмма Венна объединения показана на рисунке 2.2.

Пересечением двух множеств А и В называется множество

А В = {х: х А и х В}.

Оно состоит из элементов, которые принадлежат как множеству А, так и множеству B. Диаграмма Венна пересечения приведена на рисунке 2.3.

Рисунок 2.2 – Диаграмма Венна Рисунок 2.3 – Диаграмма Венна для объединения множеств для пересечения множеств

Дополнением множества В до множества А называется

A\В = {х: х А и x В}.

Дополнение А \ В состоит из всех элементов множества А, которые не принадлежат В (см. рисунок 2.4). Если мы оперируем подмножествами некоего большого множества U, мы называем U универсальным множеством для данной задачи. На наших диаграммах Венна прямоугольник как раз и символизирует это универсальное множество. Для подмножества А универсального множества U можно рассматривать дополнение А до U, т. е. U \ А. Поскольку в каждой конкретной задаче универсальное множество фиксировано, множество U \ А обычно обозначают и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U можно записать

= {х: не (хА)} ó = {х: х A}.

Диаграмма Венна дополнения изображена на рисунке 2.5.

 Скачать реферат