Фибоначчиев поиск

Алгоритм предназначен для поиска аргумента K в таблице значений R1,R2,...,Rn, расположеных в порядке возрастания ключей: K1<K2<...<Kn.

Для удобства описания предполагается, что N+1 есть число Фибоначчи Fk+1. Подходящей начальной установкой данный метод можно сделать пригодным для любого N

1. [Начальная установка]. Установить i <=Fk, p<=Fk-1, q <= Fk-2. (В этом алгоритме p и q обозначают последовательные числа Фибоначчи.)

2. [Сравнение]. Если K<Ki, то перейти на F3; если K>Ki, то перейти на F4; если K=Ki, алгоритм заканчивается удачно.

3. [Уменьшение i ]. Если q=0, то алгоритм заканчивается неудачно. Если q<>0,то установить i<= i-q, заменить (p,q) на (q,p-q) и вернуться на F2.

4. [Уменьшение i ]. Если p=1, то алгоритм заканчивается неудачно. Если p<>1,то установить i<= i+q, p<=p-q, q<=q-p и вернуться на F2.

Задание к работе:

1. Составить блок-схему и программу на языке Borland Pascal, которая:

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

- осуществить сортировку по возрастанию и убыванию элементов файла в памяти, создав два соответствующих массива. Результаты сортировки выдать на монитор;

- осуществить выбор n-го минимума и m-го максимума, используя два метода (первый для поиска n-го минимума, второй - m-го максимума)

- используя неотсортированный массив и метод последовательного поиска, осуществить поиск элемента с заданным значением. Оценить затраты времени;

- используя отсортированный массив и метод бинарного поиска, осуществить поиск элемента с заданным значением. Оценить затраты времени. Сравнить с методом последовательного поиска.

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

Значения n и m запросить с клавиатуры.

2. Программу оформить в виде меню, примерные опции которого следующие: формирование файла, индикация содержимого файла (поэкранно), сортировка, вывод отсортированного массива на экран, выбор m-го максимума и n-го минимума, поиск I и II методами.

3. Во время работы по сортировке необходимо индицировать на экране время, затраченное на каждый из методов. Предпочтительней использование динамических переменных.

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

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

Контрольные вопросы.

1. Постановка задач поиска и выбора.

2. Какими методами осуществляется поиск в отсортированном и неотсортированном массиве?

3. Какие ограничения накладываются на условия выбора?

4. Правила оформления и назначение модуля в Borland Pascal?

5. Комментарии и их назначение.