Вопросы и упражнения. 1. Напишите процедуру поиска трех минимальных элементов массива за один проход

1. Напишите процедуру поиска трех минимальных элементов массива за один проход.

2. Напишите процедуру поиска k -й порядковой статистики при помощи неполного алгоритма QuickSort.

3. Выполните поиск медианы в массиве A = (48, 72, 3, 14, 35, 65, 88, 89, 95, 6, 5, 65, 21, 24, 77), используя неполный алгоритм QuickSort. В качестве разделяющего использовать первый элемент массива.

4. Выполните поиск образца ‘ abbabab ’ в строке ‘ abbabbabbababb ’, используя алгоритм Кнута, Морриса и Пратта.

5. Выполните поиск образца ‘ bacab ’ в строке ‘ aacabacaabacabc ’, используя алгоритм Бойера и Мура.

Заключение

В данном пособии были рассмотрены наиболее важные алгоритмы решения задач сортировки и поиска, а также соответствующие структуры данных. Рассмотренные алгоритмы входят в «золотой фонд» программирования, хорошее знакомство с ними следует считать необходимой частью подготовки квалифицированного программиста.

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

Но не менее важна и другая сторона дела. В ходе рассмотрения различных алгоритмов было показано, что выбор более сложного, но высокоэффективного алгоритма позволяет в сотни и тысячи раз ускорить решение задач по сравнению с простыми, «очевидными», но неэффективными алгоритмами. Из этого следует, что тщательный предварительный анализ задачи, оценка эффективности используемых алгоритмов, выбор алгоритма, оптимального в конкретной ситуации – это этапы, без которых невозможна разработка программ на профессиональном уровне. Если данное пособие поможет студенту осознать эту важную истину, задачу автора можно считать выполненной.