Курсовая работа: Алгоритмы обработки больших массивов. Алгоритмы обработки данных

Фактически операция слияния почти идентична той же операции в сортировке с помощью N-путевого слияния, разница только в том, что здесь алгоритм исключения последовательности несколько проще.

Глава 2. Практические задачи по алгоритмам обработки данных

2.1 Решение задачи о пяти ферзях

Постановка задачи: Найти расстановку пяти ферзей, при которой каждое поле шахматной доски будет находится под ударом хотя одного из них.

Задача о пяти ферзях — хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. Для подобных задач характерно отсутствие аналитического решения. Вместо этого они требуют большого объема изнурительных вычислений, терпения и аккуратности. Поэтому такие задачи стали почти исключительно прерогативой вычислительных машин, которые обладают этими свойствами в гораздо большей степени, чем люди, даже гениальные.

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

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

2.2 Сортировка Шелла

Постановка задачи: Написать программу, которая реализует сортировку Шелла.

В 1959 г. Д. Шеллом было предложено усовершенствование сортировки с помощью прямого включения. Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. После первого прохода элементы перегруппировываются— теперь каждый элемент группы отстоит от другого на две позиции — и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает. Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояний обозначаются соответственно hi, h2, ..., ht, для них выполняются условия

ht = l. hJ+1<h

Каждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров.

2.3 Trie-дерево

Постановка задачи: В Trie-дереве определить количество слов, содержащих букву А.

Деревом называется связный ориентированный граф без циклов, каждая вершина которого имеет только одно входящее ребро.

Узел и поддеревья связаны между собой ветвями. Число ветвей, выходящих из узла, определяют его арность. Если все узлы имеют одинаковую арность, равную n, то такая структура называется n-арным деревом. Если n = 2, то дерево называется бинарным.

Одним из видов сильно ветвящихся деревьев является Trie-дерево. Название Trie-дерево происходит от искусственно образованного слова trie, от полного слова retrieval (поиск). Такое дерево используется тогда, когда ключами поиска являются достаточно короткие слова. Чем больше коротких слов содержится в Trie-дереве, тем эффективнее соотношение количества слов к количеству памяти, расходуемой под хранение элементов в Trie-дереве. Каждый ключ в Trie-дереве можно рассматривать как список символов, а все списки вместе — как дерево поиска. В такой структуре узлу уровня i + 1 ставится в соответствие i-ый символ слова, поэтому каждый узел содержит лишь один символ. Методы поиска по такому дереву экономны по памяти и по времени.

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

2.4 Обработка текстовых данных, хранящихся в текстовом файле

Постановка задачи: подсчитать число слов с чётной длиной.

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

Заключение

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

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

В этой курсовой работе так же рассмотрены такие задачи, как: сортировка Шелла, нахождение элементов в Trie-дереве и задачу с текстовыми данными.

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

Список литературы

1.  Вирт Н. Алгоритмы и структуры данных. — СПб.: Невский диалект, 2001. 352 с.

2.  Дмитриева М. В.. Кубенский А. А. Турбо Паскаль и Турбо Си: построение и обработка структур данных: Учебное пособие. — СПб.: Изд-во С.- Петербургского университета, 1995. — 245 с.

3.  Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск: Пер. с англ. — М.: Вильяме, 2000. — 822 с.

4.  Мейер Д., Бодуэн К. Методы программирования. Т. 1,2.— М.: Мир, 1985.

5.  Вирт Н. Алгоритмы и структуры данных+программы. — СПб.: Невский диалект, 2001. - 406 с.