Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница7/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   2   3   4   5   6   7   8   9   10   ...   19
^

Дихотомический поиск по интервалу


Задачей поиска по интервалу является определение записей таблицы, ключи которых входят в задаваемый интервал значений.

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

В качестве примера рассмотрим следующую последовательность ключей (ключи записей упорядоченной таблицы):

индексы записей

1

2

3

4

5

6

7

8

9

10

ключи

5

8

12

15

18

20

21

25

28

30

Определить записи, ключи которых попадают в задаваемый интервал:

1) интервал [10, 20]

Результат поиска: записи с индексами 3..6.

2) интервал [16, 40]

Результат поиска: записи с индексами 5..10.

3) интервал [4, 35]

Результат поиска: записи с индексами 1..10 (все записи таблицы попадают в заданный интервал).

4) интервал [16, 17]

Результат поиска: в таблице нет записей с ключами из заданного интервала.

5) интервал [35, 40]

Результат поиска: в таблице нет записей с ключами из заданного интервала.
^ Задание к лабораторной работе
Разработать приложение, содержащее процедуры, реализующие основные операции над таблицами: формирование таблицы, сортировка или поиск (согласно указанному варианту), вывод таблицы.

В качестве языка программирования следует использовать ТурбоПаскаль, как наиболее подходящее средство для задач обработки данных.

В приложении А приведен пример программы, выполняющей сортировку таблицы методом линейного выбора.
Варианты заданий

Упорядочить таблицу, используя:

1.Метод линейного выбора с подсчетом.

2.Метод шейкер - сортировки.

3. Метод вставки с бинарным включением.

4. Метод двухпутевой вставки.

5. Метод Шелла.

6. Метод "быстрой" сортировки (в качестве разделяющего использовать первый элемент таблицы).

7. Метод "быстрой" сортировки (в качестве разделяющего использовать средний элемент таблицы).

8. Метод простого двухпутевого слияния.

9. Метод естественного слияния.
Упорядочить таблицу указанными в варианте методами и выполнить сравнительный анализ зтих методов:

10. Метод вставки с прямым включением и метод двухпутевой вставки.

11. Метод вставки с прямым включением и метод Шелла.

12. Метод "пузырька" и метод шейкер сортировки.

13. Метод линейного выбора и метод линейного выбора с подсчетом.

14. Метод линейного выбора и метод "быстрой" сортировки (с первым разделяющим элементом).

15. Метод вставки с прямым включением и метод “быстрой” сортировки (со средним разделяющим элементом).

16. Метод линейного выбора и метод “быстрой” сортировки (со средним разделяющим элементом).

17. Метод вставки с прямым включением и метод "быстрой" сортировки (с первым разделяющим элементом).

18. Метод вставки с прямым включением и метод вставки с бинарным включением.

19. Метод “пузырька” и метод вставки с бинарным включением.

20. Метод “пузырька” и метод простого двухпутевого слияния.

21. Методы "пузырька", линейного выбора и вставки с прямым включением.

22. Метод "пузырька" и метод вставки с прямым включением.

23. Метод линейного выбора и модифицированный метод линейного выбора.

24. Модифицированный метод линейного выбора и метод вставки с прямым включением.

25. Модифицированный метод линейного выбора и метод "пузырька".
Выполнить следующие виды дихотомического поиска:

26. Поиск по совпадению при наличии в таблице нескольких записей с заданным значением ключа (предварительно упорядочить таблицу модифицированным методом линейного выбора).

27. Поиск по близости (предварительно упорядочить таблицу методом “пузырька”).

28. Поиск по интервалу (предварительно упорядочить таблицу методом вставки с прямым включением).

29. Поиск записей, ключи которых больше заданного значения (предварительно упорядочить таблицу методом шейкер-сортировки).

30. Поиск записей, ключи которых меньше заданного значения (предварительно упорядочить таблицу модифицированным методом линейного выбора).

Пояснения:

Сравнительный анализ методов сортировки (варианты 10-25) можно осуществить подсчетом числа сравнений, выполненных в процессе сортировки таблицы разными методами.
^ Требования к выполнению лабораторной работы

Разрабатываемое приложение должно удовлетворять следующим требованиям:

1. Алгоритмы, реализующие операции над таблицами, нужно оформить в виде процедур (функций) с соответствующими формальными параметрами.

2. Содержимое контрольной таблицы может считываться из файла, но должна быть предусмотрена также возможность ввода записей таблицы в интерактивном режиме. Таблица должна иметь не менее двух полей, одно из которых   ключевое.

3. На экран выводить:

а) исходную таблицу;

б) результаты выполнения шагов сортировки (поиска), демонстрирующие конкретный метод (при этом рекомендуется выполнять вывод данных различным цветом);

в) окончательный результат.

4. Для простых методов сортировки контрольную таблицу можно брать небольшой, примерно, 10-15 записей, для сложных – не менее 25 записей (чтобы выполнилось несколько шагов метода).

5. Привести примеры “ручной” сортировки (поиска) таблицы заданными методами.
Контрольные вопросы

  1. Определение таблицы, записи, ключа; классификация таблиц.

  2. Определение операции сортировки; основные методы сортировки и их характеристики.

  3. Определение операции поиска; дихотомический поиск по совпадению, близости, интервалу.
^

ЛАБОРАТОРНАЯ РАБОТА 2

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ


Цель работы: ознакомление с динамическими структурами данных и процедурами их обработки.

1   2   3   4   5   6   7   8   9   10   ...   19

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница