Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
4
file:///home/disk1/12balov/files/22/document.doc
Постановка задачи: Задан массив содержащий n фамилий. Необходимо определить существует ли в этом массиве заданная фамилия. Если существует, необходимо вывести её номер, иначе сообщить об её отсутствии.
Будем предполагать, что каждый элемент массива уникален. Хотя, если это не так, то будем фиксировать только первое появление заданной строки в массиве.
Суть линейного поиска состоит в последовательной сравнении всех элементов массива с искомым элементом.
Const n=100;
Type strtype=string[20];
Var m=array[1..n] of strtype;
found:boolean; (* элемент найден *)
i:integer; (* номер элемента *)
str:string; (* искомая строка *)
== == == == == == == ==
i:=0;
repeat
inc(i);
found := m[i]=str;
until found or (i=n);
if found
then writeln(‘Номер искомой строки=’,i)
else writeln(‘В массиве нет заданной строки.');
== == == == == == == ==
В общем случае при поиске линейным методом среди n элементов требуется в среднем n/2 сравнений в случае успешного поиска и n сравнений в наихудшем случае (если в массиве нет искомого элемента).
Если о массиве известно, что он предварительно был отсортирован, то возможно применение следующего утверждения: как только обнаруживается, что очередное проверяемое значение больше искомого, мы можем уверенно выйти из цикла и сообщить о безуспешности поиска, не занимаясь проверкой оставшихся элементов массива.
Задан массив m состоящий из n элементов типа string. Необходимо найти номер элемента содержащего строку str.
В самом начале процесса поиска обозначим в переменной low=1 номер первого элемента массива, в переменной high=n номер последнего элемента массива.
Сравнить значение str с элементом ряда в позиции, лежащей посередине между low и high. Если этот элемент равен str, то поиск успешно завершается. Если он больше, чем str, значением границы high должен стать номер проверявшейся позиции, уменьшенный на единицу. Если элемент в проверяемой позиции меньше str, то значением границы low должен стать номер проверявшейся позиции, увеличенный на единицу. Продолжать описанный процесс, пока значение str не найдено и при этом low меньше или равно high.
Поиск строки ’Chester’.
Элемент ’Chester’найден!
Элемент ’Baker’ НЕ найден!
Своим названием метод бинарного поиска обязан заложенной в него идеи «отсечения половины». Процесс последовательного деления пополам называется дихотомией, вследствие чего описанный метод поиска часто называют дихотомическим.
Program LEC3_5_4; {бинарный поиск}
const n=7;
Type
diapason=1..n;
MyArray=array[diapason] of string[20];
const
m:MyArray=('Abel','Barnes','Bishop','Charles',
'Chester','Davis','Fisher');
var
str:string[20];
low,high,test:diapason;
found:boolean;
begin
str:='Chester';
{инициализация переменных}
low:=1; high:=n; found:=false;
{цикл поиска}
while (not found) and (low <= high) do
begin
test:=(low + high) div 2;
found:= m[test]=str;
if m[test]>str
then high:=test-1
else low:=test+1;
end; {while}
if found
then writeln('Строка '+str+' найдена. №=',test)
else writeln('Строка '+str+' НЕ найдена!');
writeln('Нажмите Enter...'); readln;
end.
Число проверок при поиске
|
n |
Линейный поиск |
Бинарный поиск |
||
|
элемент |
элемент |
элемент |
элемент |
|
|
7 |
4 |
7 |
3 |
3 |
|
100 |
50 |
100 |
7 |
7 |
|
1 000 |
500 |
1 000 |
10 |
10 |
|
1 000 000 |
500 000 |
1 000 000 |
20 |
20 |