Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции - Высокоуровневые методы информатики и программирования (ВМИП) - файл 1.doc


Лекции - Высокоуровневые методы информатики и программирования (ВМИП)
скачать (2205.5 kb.)

Доступные файлы (1):

1.doc2206kb.04.12.2011 09:12скачать

содержание
Загрузка...

1.doc

1   2   3   4   5   6   7   8   9   10   11
Реклама MarketGid:
Загрузка...
^

Алгоритмы поиска информации

Линейный поиск



Пусть имеется некоторый набор данных и требуется определить, где в этом наборе находится заданный элемент ( и есть ли он в наборе ). Такая задача называется задачей поиска. Большинство задач поиска сводится к поиску в таблице ( массиве ) элемента с заданным значением.
^ Пример
Написать программу поиска элемента x в массиве из n элементов. Значение элемента x вводится с клавиатуры.
Решение
Пусть имеются следующие описания:

Const n = 10; { размерность массива }

Var a: array ( 1...n ) Of Integer;

{ массив из n элементов целого типа }

x: Integer; { искомый элемент целого типа }

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

For i: =1 To n Do If a[i] = x Then k: = i;

Этот способ решения поставленной задачи, безусловно, приводит к цели, но обладает рядом существенных недостатков:

  • если значение x встречается в массиве несколько раз, то найдено будет последнее из них;

  • после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется n сравнений.

Разумно прекратить просмотр сразу после обнаружения заданного элемента. Так как в этом случае число повторений не известно, необходимо использовать цикл с предусловием. В результате:

- либо будет найден искомый элемент, то есть найдется такой индекс i, что а [ i ] = x;

- либо будет просмотрен весь массив, и искомый элемент не обнаружится.

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

While ( i <= n ) And ( a[ i ]<> x ) Do Inc ( i );
Примечание: Необходимо обратить внимание на порядок простых условий в составном условии цикла. Здесь предполагается, что второе условие не проверяется, если результат логического выражения ясен после проверки первого условия. В противном случае возникнет отказ из-за выхода индекса за границы массива.
Программа линейного поиска:
program n6;

const n=5;

var a:array[1..n] of integer;

{ массив из n элементов целого типа }

x:integer; { искомый элемент целого типа }

i,k:integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

writeln('Введите x');

readln(x);

for i:=1 to n do if a[i]=x then k:=i;

while (i<=n) and (a[i]<>x) do inc(i);

writeln('a[',k,']=',x,'=x');

end.

^

Линейный поиск с использованием барьера



Недостатком нашей программы является то, что в заголовке цикла записано сложное условие, которое проверяется перед каждым увеличением индекса, что замедляет поиск. Чтобы ускорить его, необходимо максимально упростить логическое выражение.

Постараемся оставить в заголовке цикла лишь простое условие а [ i ]<>x. Для этого используем следующий прием. В массив на ( n + 1 ) - e место запишем ископаемый элемент x, который назовем барьерным. Тогда если в процессе работы программы обнаружится такой индекс i, что а [ i ] = x, то элемент будет найден, а если условие a[i] = x выполнится только при i = n + 1, то, значит, интересующего нас элемента в массиве нет. Таким образом, эта часть программы будет выглядеть так:

a [ n + 1 ]: = x; i: = 1;

While a [ i ]<>x Do Inc ( i );

При таком способе поиска в случае наличия в массиве нескольких элементов, удовлетворяющих заданному свойству, также будет найден элемент с наименьшим индексом.
Программа линейного поиска с использованием барьера:
program n7;

const n=5;

var a:array[1..n+1] of integer;

{ массив из n элементов целого типа }

x:integer; { искомый элемент целого типа }

i,k:integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n+1 do read(a[i]);

writeln('Введите x');

readln(x);

a[n+1]:=x; i:=1;

while (a[i]<>x) do begin

inc(i);

if a[i]=x then k:=i;

end;

writeln('a[',k,']=',x,'=x');

end.


^

Бинарный поиск



Как было отмечено выше, если никаких дополнительных сведений о массиве, в котором хранятся данные, нет то ускорить поиск нельзя. Если же заранее известна некоторая информация о данный, среди которых ведется поиск, например,

массив данных отсортирован, удается существенно сократить время работы, применяя другие методы поиска.

Одним из методов поиска, более эффективным, чем линейный, является бинарный ( двоичный ) поиск, называемый также методом половинного деления. При его использовании на каждом шаге область поиска сокращается вдвое. Рассмотрим применение этого метода для решения конкретной задачи.

Задача
Даны целое число x и массив a[1..n], отсортированный в порядке убывания, то есть для любого k: 1 ≤ k < n: a[k-1] ≤ a[k]. Найти такое i, что a[i] = x, или сообщить, что элемента x в массиве нет.

Идея бинарного метода состоит в том, чтобы проверить, является ли x средним элементом массива. Если да, то ответ получен. Если нет, то возможны два случая:

  • x меньше среднего элемента, следовательно, в силу упорядоченности массива a, можно исключить из рассмотрения все элементы массива, расположенные в нем правее среднего ( так как они больше среднего элемента, который, в свою очередь, больше x ), и применить этот метод к левой половине массива.

  • x больше среднего элемента, следовательно, рассуждая аналогично, можно исключить из рассмотрения левую половину массива и применить этот метод к его правой части.

Средний элемент и в том, и в другом случае в дальнейшем не рассматривается. Таким образом, на каждом шаге отсекается та часть массива, где заведомо не может быть обнаружен элемент x.
^ Рассмотрим пример
Пусть x = 6, а массив а состоит из 10 элементов:

3 5 6 8 12 15 17 18 20 25.

1-й шаг: найдем номер среднего элемента:



m =.Так как 6 < a [ 5 ], далее можем рассматривать только элементы, индексы которых меньше 5. Об остальных элементах можно сразу сказать, что они

больше x вследствие упорядоченности массива, и среди них искомого элемента нет:
3 5 6 8 12 15 17 18 20 25;


  1. й шаг: рассматриваем лишь первые 4 элемента массива;

находим индекс среднего элемента этой части:

m =

6 > a [ 2 ], следовательно, первый и второй элементы из рассмотрения исключаем:

  1. 5 6 8 12 15 17 18 20 25;


3-й шаг: рассматриваем 2 элемента; значение
m =;

3 5 6 8 12 15 17 18 20 25;

а [ 3 ]= 6 ! Элемент найден, его номер - 3.

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

В общем случае значение m =, где l - индекс первого, а r - индекс последнего элемента рассматриваемой части массива.
program n8;const n=10;var x,l,r,m,i:integer; f:boolean; a:array[1..n] of integer;begin writeln('Введите исходный массив:'); for i:=1 to n do read(a[i]); writeln('Введите x'); readln(x); l:=1; r:=n; f:=false;

while (l<=r)and not f do

begin

m:=(l+r) div 2;

if a[m]=x then f:=true else if a[m]<x then l:=m+1 else r:=m-1;

end;

writeln('a[',m,']=',x,'=x');

end.
Программа этой же сортировки с использованием барьера.
program n9;const n=10;var x,l,r,m,i:integer; f:boolean; a:array[1..n] of integer;

begin

writeln('Введите исходный массив:');

for i:=1 to n do read(a[i]);

writeln('Введите x');

readln(x);

l:=1;

r:=n;

f:=false;

while (l<=r)and not f do

begin

m:=(l+r) div 2;

if a[m]=x then f:=true else if a[m]<x then l:=m+1 else r:=m-1;

end;

writeln('a[',m,']=',x,'=x');

end.

1   2   3   4   5   6   7   8   9   10   11



Скачать файл (2205.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru