Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Тема: «Исследование основных алгоритмов поиска»





Цель работы – изучить принцип построения алгоритмов поиска.

Теоретические сведения

Алгоритмы поиска, как и алгоритмы сортировки, являются основными алгоритмами обработки данных как системных, так и прикладных задач.

Дан аргумент поиска K. Задача поиска состоит в отыскании записи, имеющей K своим ключом. Существуют две возможности окончания поиска: либо поиск оказался удачным, т.е. позволил определить местонахождение записи, содержащей ключ K, либо он оказался неудачным, т.е. показал, что ни одна из записей не содержит ключ K.

Последовательный поиск

Для массива, данные в котором не упорядочены путём сортировки или каким-либо другим способом, единственный путь для поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным его позиция в массиве фиксируется. Этот алгоритм называется последовательным или линейным поиском. Эффективность этого метода очень низкая, так как для отыскания одного элемента в массиве размерности N в среднем нужно сделать N/2 сравнений.

14.2 Бинарный (двоичный) поиск

Бинарный или двоичный поиск может быть использован в качестве алгоритма поиска в упорядоченном массиве:

Схема алгоритма следующая. Сначала сравнивают K со средним элементом массива. Результат сравнения позволяет определить, в какой половине массива следует продолжать поиск, применяя к ней ту же процедуру, и т.д. После не более чем сравнений ключ либо будет найден, либо будет установлено его отсутствие.

14.3 Интерполяционный поиск

По-видимому, бинарный поиск не является самым лучшим методом поиска, доказательством чему служит то обстоятельство, что в повседневной жизни им мало пользуются. Гораздо чаще используется интерполяционный поиск. Его схема следующая, Если известно, что K находится между и , то номер очередного элемента для сравнения определяется формулой

Последующая процедура аналогична процедуре, используемой в бинарном поиске.

Интерполяционный поиск асимптотически предпочтительнее бинарного; по существу один шаг бинарного поиска уменьшает количество "подозреваемых" записей от n до , а один шаг интерполяционного - от n до . В среднем интерполяционный поиск требует шагов.

Индивидуальные задания

1) Сформировать массив N целых чисел. Создать алгоритм определения суммы чисел, имеющих четные порядковые номера.

2) Сформировать массив N целых чисел. Создать алгоритм определения количества нулевых элементов и исключить их из массива.

3) Сформировать массив N целых чисел. Создать алгоритм определения наличия среди них одинаковых. Нулевые значения не учитывать.

4) Сформировать массив N чисел, среди которых могут быть как положительные, так и отрицательные числа. Создать алгоритм определения суммы и количества только отрицательных значений.



5) Сформировать массив N целых двухзначных чисел. Создать алгоритм выбора чисел, имеющих четные индексы, и записать их в новый массив.

6) Сформировать массив N целых двухзначных чисел. Создать алгоритм выбора чисел, имеющих нечетные индексы, и записать их в новый массив.

7) Сформировать массив N натуральных чисел. Создать алгоритм выбора из них равных и исключить их из массива.

8) Сформировать массив N натуральных чисел. Создать алгоритм выбора всех чисел < 20 или > 80 и исключить их из массива.

9) Сформировать массив N натуральных чисел. Создать алгоритм выбора всех чисел >9 и < 60 и исключить их из массива.

10) Сформировать массив N чисел, среди которых могут быть как положительные, так и отрицательные числа. Создать алгоритм определения суммы положительных и суммы отрицательных чисел.

11) Сформировать массив N целых чисел. Создать алгоритм определения суммы чисел, имеющих четные порядковые номера.

12) Сформировать массив N целых трёхзначных чисел. Создать алгоритм определения всех нечётных чисел и записать их в новый массив.

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

1) Что понимается под определением поиска?

2) Какие виды поиска различают?

3) Укажите основные особенности алгоритмов поиска.

Библиографический список

1. ГОСТ 19.701–90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения – М.: Изд-во стандартов.

2. Колмогоров, А. Н. Алгоритм, информация, сложность. (Новое в жизни, науке, технике. Математика. Кибернетика; вып. 1). / А. Н. Колмогоров. - М.: Знание, 1991. - 45 с.

3. Канцедал, С. А. Алгоритмизация и программирование / учеб. пособие для студ. учреждений сред. проф. образования / С.А. Канцедал. - М.: Форум-Инфра - М, 2008. - 352с.

4. Робертсон, Л. А. Программирование - это просто. пер. с англ. / Л. А. Робертсон; Ред. С. М. Молявко. - М.: Бином-Лаборатория Знаний, 2008. - 383с.

5. Окулов, С. М. Основы программирования. учеб. / С.М. Окулов. - 3-е изд. - М.: Бином, 2006. - 440 с.

6. Ляхович, В. Ф. Основы информатики / В. Ф. Ляхович. - Ростов н/Д : Феникс, 2000. – 606с.

7. Симонович С.В. Информатика: базовый курс. учеб. пособие для студ. втузов / Ред. С. В. Симонович. - СПб. и др. : Питер, 2000. – 638с.

8. Голицына О.Л. Информационные системы: учеб. пособие для студ. вузов, обуч. по спец. "Приклад. информатика" / О.Л. Голицына, Н. В. Максимов, И. И. Попов. - М.: Форум : Инфра, 2007. - 496с.

9. Кормен Т. Алгоритмы: построение и анализ: пер. с англ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. - 2-е изд. - М. ; СПб.; К.: Вильямс, 2005. - 1296с.

10. Уилсон С. Ф. Принципы проектирования и разработки программного обеспечения: учебный курс MCDS [] : пер. с англ.: официальное пособие для самостоятельной подготовки к экзамену 70-100 / С. Ф. Уилсон , Б. Мэйплс, Т. Лэндгрейв. - 2-е изд., испр. - М. : Русская Редакция, 2002. - 688с.

11. Савельев, А. Я. Основы информатики: учеб. для студ. вузов / А. Я. Савельев ; Моск. гос. техн. ун-т им. Н. Э. Баумана. - М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. - 327с.


[1] Допускается использовать готовые шаблоны согласно ГОСТ 19.701–90 - Схема алгоритмов и программ. Комплект шаблонов находится по адресу http://crisis.ucoz.ru/load/32-1-0-193

[2] Если необходимо выполнить сохранение элементов как шаблон для последующего использования, необходимо выполнить команду File / Save As и в появившемся окне выбрать тип Stencil.









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.