Сборник заданий по методам программирования

Вид материала

Учебно-методическое пособие

Содержание Создать структуру данных сбалансированное красно-черное ДЕРЕВО (*) ТЕМА 2. Сортировка Алгоритм слияния k отсортированных списков в один отсортированный список Реализовать алгоритм Шелла Реализовать алгоритм пирамидальной сортировки Реализовать алгоритм турнирной сортировки для произвольного числа элементов

Подобный материал:

• Сборник заданий по методам программирования, 665.7kb.
• Программа учебной дисциплины «Информатика и программирование» Программа дисциплины, 135.24kb.
• Лекция 3 Инструментальное по. Классификация языков программирования, 90.16kb.
• Лекция Языки и системы программирования. Структура данных, 436.98kb.
• Проект "пульс": (описание идеи), 4896.41kb.
• Программа дисциплины Языки и технологии программирования Семестры, 20.19kb.
• Краткий обзор моделей стохастического программирования и методов решения экономических, 59.55kb.
• Программа курса " Азы программирования", 26.19kb.
• Учебно-методический комплекс по дисциплине высокоуровневые методы информатики и программирования, 435.89kb.
• Календарный план учебных занятий по дисциплине «Языки и технология программирования», 43.35kb.

Создать структуру данных сбалансированное красно-черное ДЕРЕВО (*)

Определение: Двоичное дерево поиска называется красно-черным, если оно обладает следующими свойствами:

1. каждая вершина либо красная, либо черная;
   
2. каждый лист – черный;
   
3. если вершина красная, оба её ребенка – черные;
   
4. все пути, идущие вниз от корня к листьям, содержат одинаковое количество черных вершин.
   

Задача:

Создается структура данных сбалансированное красно-черное дерево с необходимым набором операций:

• создать пустое дерево;
  
• проверить дерево на пустоту;
  
• добавить элемент в дерево;
  
• удалить элемент из дерева;
  
• просмотреть все элементы дерева;
  
• реализовать обход дерева.
  

Структура данных создается с использованием указателей на сыновей узла.


Указания:

При работе с созданной структурой необходимо в случае добавления элемента выделять память под его хранение, и в случае удаления элемента освобождать выделенную под его хранение память. При выполнении операций вставки и удаления элемента дерево может потерять свои свойства. Чтобы их восстановить, надо перекрасить некоторые вершины и изменить структуру дерева. Это осуществляется с помощью вращений. Подробно о красно-черных деревьях можно прочитать в [3].

ТЕМА 2. Сортировка

27. Алгоритм слияния k отсортированных списков в один отсортированный список

Определение: Двоичной кучей называется массив A[1…n], в котором элементы связаны следующими соотношениями: для всех i < n/2 A[i] ≥ A[2i] и A[i] ≥ A[2i+1]. Или для двоичного дерева, хранящегося в массиве, значения предков не меньше значения потомка.


Задача:

Написать алгоритм, который позволяет за время O(n log k) слить k отсортированных списков размера n в один отсортированный список.

Указание:

Для решения этой задачи необходимо использовать кучу из k элементов, хранящуюся в массиве. Для построения кучи берется по одному элементу из каждого списка. При построении кучи надо вытаскивать минимальный элемент. Далее первый элемент массива (в нем окажется минимальный элемент) выбирается в новый итоговый список. Его место занимает следующий элемент из той кучи, которой принадлежал текущий минимальный элемент. После этого куча перестраивается. Процесс повторяется до тех пор, пока не получим отсортированный итоговый список. Подробное описание алгоритма можно найти в [1-9,12].

28. Реализовать алгоритм Шелла

Задача:

Имеется массив действительных чисел. Необходимо его отсортировать в порядке убывания с помощью алгоритма Шелла. Этот алгоритм является сортировкой вставками с убывающим шагом.

Указания:

При реализации алгоритма необходимо предусмотреть подсчет числа операций сравнения и присваивания. Желательно использовать технику барьеров. Также необходимо выбрать две различные последовательности шагов. С помощью генератора случайных чисел получить 20 массивов и, отсортировав их, используя выбранные последовательности шагов, получить эмпирические оценки трудоемкости алгоритма. Сопоставить полученные эмпирические и имеющиеся теоретические оценки. Подробное описание алгоритма можно найти в [1-9,12].

29. Реализовать алгоритм пирамидальной сортировки

Определение: Двоичной кучей называется массив A[1…n], в котором элементы связаны следующими соотношениями: для всех i < n/2 A[i] ≥ A[2i] и A[i] ≥ A[2i+1]. Или для двоичного дерева, хранящегося в массиве, значения предков не меньше значения потомка.

Определение: Пирамида – двоичное дерево, хранящееся в виде кучи.


Задача:

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

- построение пирамиды;

- перестройка пирамиды.


Указания:

При реализации алгоритма необходимо предусмотреть подсчет числа операций сравнения и присваивания. Проведя серию экспериментов c использованием генератора случайных чисел для формирования массивов, показать, что полученные результаты согласуются с теоретическими оценками. Подробное описание алгоритма можно найти в [1-9,12].

30. Реализовать алгоритм турнирной сортировки для произвольного числа элементов

Задача:

Имеется массив действительных чисел размера n. Необходимо его отсортировать в порядке возрастания с помощью алгоритма турнирной сортировки. Алгоритм турнирной сортировки относится к сортировкам выбором. Он состоит из двух этапов:

• построение дерева турниров;
  
• перестройка дерева.
  

Алгоритм требует выделения дополнительной памяти объемом 2n. Дерево турниров хранится в массиве. В случае, когда n является степенью двойки, выделяем массив M[1..2n]. Сортируемые числа записываем в листья строящегося дерева турниров. Далее формируем внутренние узлы, учитывая, что сыновьями M[i] будут M[2i] и M[2i+1]. Заполнение узлов производится снизу вверх. В M[i] выбирается максимальный из сыновей. В результате в M[1] находится максимальный элемент из сортируемых.

Далее этот элемент записывается в дополнительный массив и удаляется из дерева. Его место в соответствующем листе замещается неким условным значением, и ветка дерева перестраивается.


Указания:

При реализации алгоритма необходимо предусмотреть подсчет числа операций сравнения и присваивания. Проведя серию экспериментов с использованием генератора случайных чисел для формирования массивов, показать, что полученные результаты согласуются с теоретическими оценками. Подробное описание алгоритма можно найти в [1-9,12].