Курсовая работа: Анализ алгоритмов нечисленной обработки данных

Проверяется i-й элемент массива (дерева) на наличие правого потомка. Если он имеется, то за i-й элемент берется правый потомок и повторяется Шаг 2. Увеличивается счетчик количества перестановок m:=m+1.

Шаг 4. Индексу j присваивается значение индекса i j:=i, за индекс i берется обратный указатель (предок) i:=b[i,5], и если предок существует, то происходит следующая проверка: если предок (i-й элемент) больше своего потомка (j-й элемент), то повторить Шаг 3, иначе повторить Шаг 4.

Шаг 5. Увеличение счетчика перестановок m:=m+1.

Шаг 6. Запись отсортированного массива (дерева) в файл.

3.5 Двоичный поиск

Схема алгоритма двоичного поиска приведена в приложении В. Алгоритм реализован в виде процедуры Dv_Poisk (приложение Б).

Шаг 1. Установить начальные значения верхнего и нижнего индекса, счетчика сравнений k и : vi:=N, ni:=1, k:=0 и f:=false,так как элемент ещё не найден.

Шаг 2. Нахождение среднего элемента массива: sri:=((ni+vi) div 2).

Шаг 3. Увеличение счетчика k на единицу: k:=k+1;

Шаг 4. Если средний элемент равен искомому: a[sri]=x, то элемент найден: f:=true;

Шаг 5. Если x>a[sri] переход на шаг 6, иначе на шаг 7.

Шаг 6. За новое значение ni принимается sri+1, а значение vi не меняется.

Шаг 7. За новое значение vi принимается sri-1, а значение ni не меняется.

Шаг 8. Повторение цикла до тех пор, пока счетчик не станет больше максимального количества сравнений: k>log2n , либо элемент не будет найден.

Шаг 9. Если f:=true, то выполняется шаг 10, иначе шаг 11.

Шаг 10. На экран выводится: (‘Element naiden, Index=’, sri,'. Sravnenii ‘,k).

Шаг 11.На экран выводится: (‘Element ne naiden’).

3.6 Запись в файл

Схема алгоритма записи в файл упорядоченного массива приведена в приложении В. Алгоритм реализован в виде процедуры Save_To_File (приложение Б).

Шаг 1. При n≤16 массив записывается в файл после каждой перестановки.

Шаг 2. При n≥128 массив записывается в файл через каждые 10 перестановок.

Каждый элемент отсортированного массива располагается в четырёх позициях.

4 Инструкции по пользованию программой

4.1 Руководство пользователя

Программа, реализованная в соответствии с задачей, поставленной на курсовом проекте, написана на языке Turbo Pascal 7.0. Для запуска программы необходимо иметь компилятор Turbo Pascal 7.0. После запуска программы следует нажать комбинацию клавиш Ctrl+F9. В появившемся окне будет сообщение с просьбой ввести число элементов. Введите целое число n от 16 до 1024 элементов (можно и меньше 16), а затем нажмите клавишу Enter. Если введено n≤16, то ввод элементов надо осуществить с клавиатуры, то есть вручную. Каждый вводимый элемент должен быть положительным и меньше 1000.

Если введено n>16, то программа сформирует массив самостоятельно при помощи датчика случайных чисел;

Дальше потребуется ввести элемент для поиска - x. Затем нажать Enter.

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

- для линейного поиска - количество сравнений;