Стастический поиск элементов в массиве
Вероятность нахождения элемента масива не одинакова для различних
элементов массива. Если вероятность поиска всех элементов массива одинаковая,
то эвристический метод не принесет существенной пользы. В этом случае вместо
линейно Лоиска можно использовать статистический метод поиска. Этот метод
основан на следующих предположениях.
1. Вероятность нахождения всех элементов в массиве одинаковая.
2. Среднее значение индекса искомого элемента массива равно среднему
значению индекса массива.
Статистический метод осуществляет поиск массивов в циклах, используя два
индекса. В каждом цикле используется первый и второй индексы для исследования
элементов массива с индексами, большими или меньшими среднего значения индекса
массива соответственно. Если массив содержит нечетное число элементов, метод
сначала исследует средний элемент. В каждом цикле отыскивается элементы, которые
расположены дальше от медианы. Поиск прекращается, когда метод находит
соответствующий элемент массива или когда исчерпает весь массив.
Програма , которая иллюстрирует статистический метод поиска. Программа
выводит неотсортированные элементы объекта-массива, а затем - результаты
поиска четырех значений в объекте-массиве. Результаты также отображают число
сравнений, выполненных методом поиска.
Определение функции-члена StatSearch сначала определяет, является ли число
элементов массива нечетным. Если это условие истинно, то функция-член сравнивает
средний элемент массива с аргументом поиска. Если эти два значения совпадают, то
функция-член возвращает индекс среднего элемента. В противном случае в функции
используется цикл while для исследования элементов массива выше и ниже среднего,
причем функция возвращает индекс найденного элемента иди выдает значение
глобальной константы NOT_FOUND, если аргумент поиска не найден. Число сравнений
хранится в члене данных nNumCompares. В классе объявлена функция-член
getNumCompare, чтобы получить значение в члене данных nNumCompare.
Функция main объявляет и инициализирует C++ массив пАгг. В ней также объявлен
объект Array как экземпляр класса myArray. Затем функция main выполняет
следующие задачи.
* Копирует значения в массиве nАгг в объект Array. В этой задаче используется
цикл for для перебора элементов в массиве пАгг.
* Выводит неотсортированные элементы в объекте Array, посылая ему сообщение
C++ show. Аргумент этого сообщения - строковый литерал "Array is:".
* Ищет значения в nArr[0], nArr[3], пАгг[6] и nArr[9], используя цикл for.
В каждой итерации цикла выводится значение аргумента поиска, а затем
посылается сообщение C++ StatSearch объекту Array. Аргумент этого
сообщения - аргумент поиска nArr[i]. Цикл присваивает результат сообщения
переменной j. В цикле используется оператор if, чтобы определить, является
ли поиск успешным. Если да, то программа выводит индекс найденного элемента
массива и число сравнений, выполненных функцией-членом StatSearch. Оператор
вывода посылает сообщение C++ getNumCompare, чтобы получить число сравнений.
Содержание