Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае — log N. Быстрый алгоритм основан на следующем инварианте:
(Ak : 0 ? k < L : ak < x) AND (Ak : R ? k < N : ak ? x)
причем поиск продолжается до тех пор, пока обе секции не «накроют» массив целиком.
L := 0;
R := N;
WHILE L < R DO
m := (L+R) DIV 2;
IF a[k] < x THEN L := m+1
ELSE R := m ;
END
END
Условие окончания — L і R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при всех обстоятельствах разность R-L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L Ј m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m+1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а[R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а[R] = x. В отличие от первого нашего решения приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.

Задания
Варианты:
1.Найти наименьший элемент в массиве А с помощью линейного поиска.
2.Поиск элементов в массиве А, которые больше 30.
3.Вывести на экран все числа массива А кратные 3 (3,6,9,…) с помощью линейного поиска.
4.Найти все элементы, модуль которых больше 20 и меньше 50, с помощью линейного поиска.
5.Вывести на экран все числа массива А кратные 4 (4,8,…) с помощью линейного поиска.
6.Вывести на экран сообщение, каких чисел больше относительно 50, с помощью линейного поиска.
7.Найти элемент в массиве А и найти число сравнений с помощью линейного поиска.
8.Поиск элементов случайным образом с помощью бинарного поиска.
9.Дан список номеров машин (345, 368, 876, 945, 564, 387, 230), найти, на каком месте стоит машина с заданным номером, бинарный поиск.
10.Поиск каждого второго элемента в списке и число сравнений.
11.Найти элемент с заданным ключом с помощью бинарного поиска.

Лабораторная работа №11. «ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ ПОИСКА »

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники