Программа частотного словаря сочетаний слов
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
rray, что Array[1] - элемент в корне, а потомки элемента Array[i] - Array[2i] и Array [2i+1].
Алгоритм сортировки будет состоять из двух основных шагов:
. Выстраиваем элементы массива в виде сортирующего дерева:
Array[i] ? Array[2i][i] ? Array [2i+1], при n/2 ? i ? 1.
Этот шаг требует операций.
. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], …, Array [n-1] в сортирующее дерево. Затемпереставляем Array[1] и Array [n-1], преобразуем Array[1], Array[2], …, Array [n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], …, Array[n] - упорядоченная последовательность. [1] Этот шаг требует операций.
Выбор алгоритма сортировки перестановкамиобусловлен его простотой и быстродействием по сравнению с остальными описанными выше алгоритмами.
В основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением - к концу массива (тонут). Поэтому данный метод сортировки обменом иногда называют методом пузырька. Этот процесс повторяется столько раз, сколько элементов в массиве, минус единица. [3]
На рис. 1.1 цифрой 1 обозначено исходное состояние массива и перестановки на первом проходе, цифрой 2 - состояние после перестановок на первом проходе и перестановки на втором проходе, и т.д.
Рис. 1.1. Сортировка перестановками
Процедура сортировки, запускается нажатием кнопки Сортировка (Button1). Значения элементов массива вводятся из ячеек компонента stringGrid1. Во время сортировки, после выполнения очередного цикла обменов элементов массива, программа выводит массив в поле метки Label2.
Листинг 1.1. Сортировка массива методом обмена [3]
procedure TForm1. Button1Click (Sender: TObject);
const=5;
var:array [1..SIZE] of integer;
k:integer; // текущий элемент массива:integer; // индекс для ввода и вывода массива:boolean; // TRUE, если в текущем цикле были обмены:integer; // буфер для обмена элементами массива
begin
// вводмассива
for i:=1 to SIZE do[i]:= StrToInt (StringGrid1. Cells [i-1, 0]);
label2.caption:=;
// сортировка массива repeat:=FALSE; // пусть в текущем цикле нет обменов
for k:=l to SIZE-1 doa[k] > a [k+l] then
begin // обменяем k-й и k+1-й элементы
buf:= a[k]; a[k]:= a [k+l]; a [k+l]:= buf;:= TRUE;
end;
// выводмассива
for i:=l to SIZE do.caption:=label2.caption+ +IntTostr (a[i]);.caption:=label2.caption+#13;
untilnot changed; // еслинебылообменов, значит
// массивотсортирован.caption:=label2.caption
+#13+Maccив отсортирован.;
end;
Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.
Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение FALSE. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.
Рис. 1.2. Этапы сортировки массива методом обмена после завершения процесса сортировки
Для организации поиска в массиве могут быть использованы различные алгоритмы.
Линейный, последовательный поиск - алгоритм нахождения заданного значения произвольной функции на некотором отрезке. [2] Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым. [2]
Если отрезок имеет длину N, то найти решение с точностью до можно за время . Т.о. асимптотическая сложность алгоритма - . В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки / анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума / минимума.
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) - классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. [4]
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке.
Листинг 1.2. Двоичныйпоискэлементавмассиве. [5]
functionRecurceFind (L, R: Integer): Integer;
var: Integer;
begin
if R < L then
begin:=L; // Result:= -1 еслипоискточный
Exit;
end;:= (L + R) div 2;
if A[M] = X then
begin:= M;;
end;