Стастический поиск элементов в массиве

Вероятность нахождения элемента масива не одинакова для различних элементов массива. Если вероятность поиска всех элементов массива одинаковая, то эвристический метод не принесет существенной пользы. В этом случае вместо линейно Лоиска можно использовать статистический метод поиска. Этот метод основан на следующих предположениях. 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, чтобы получить число сравнений.

Содержание