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

j:=Nh;L:=0;

REPEAT

IF j < Nh THEN x := j+l ELSE j: = 1 END;

копирование одной серии из f0 в последовательность J;

L:=L+1

UNTIL fo.eof;

FORi:=l TO N DO t[i]:=I END;

REPEAT (* слияние из t[l]...t[nh] в t[nh+l]...i[n]*)

установка входных последовательностей;

L: = 0;

j:=Nh+l; (*j -индекс выходной последовательности*)

REPEATL:=L+1;

слияние а серий с входов bi(j);

IF j < N THEN j : = j+l ELSE j := Nh+I END

UNTILвсе входы исчерпаны

переключение последовательностей

UNT1LL = 1

(• отсортированная последовательность в t [1 ] *)

ENDBalancedMerge,

Многофазная сортировка

Мы уже познакомились с необходимыми приемами и в достаточной мере готовы к исследованиям и программированию, связанным с новыми, более эффективными, чем сбалансированная сортировка, алгоритмами. В основе нашего очередного усовершенствования лежит отказ от жесткого понятия прохода и переход к более изощренному использованию последовательностей. Мы больше не будем считать, что есть N/2 входов и столько же выходов и они меняются местами после каждого отдельного прохода. Более того, уже само понятие прохода делается расплывчатым. Новый метод был изобретен Р. Гилстэдом [2.3] и называется многофазной сортировкой (PolyphaseSort).

Многофазная сортировка более эффективна, чем сбалансированная, поскольку она имеет дело с N—1-путевым слиянием, а не с N/2-путевым, если она начинается с N последовательностей. Ведь число необходимых проходов приблизительно равно logN *n, где n — число сортируемых элементов, а N — степень операции слияния, — это и определяет значительное преимущество нового метода.

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

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

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

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

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

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

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