Презентация на тему Поиск данных

n элементов. Значение элемента х вводится с клавиатуры.
Решение:
Дано:
Const

n= 10;
Var a: Array[1..n] of integer;
x: integer;

никакой дополнительной информации о нем или о массиве, в

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

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

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

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

Прервем просмотр сразу же после обнаружения заданного элемента!

x) do inc(i);
В результате:
либо будет найден искомый элемент,

т.е. найдется такой индекс i, что a[i] = x;
либо будет просмотрен весь массив, и искомый элемент не обнаружится.
Поскольку поиск заканчивается только в случае, когда i = n + 1 или когда искомый элемент найден, то из этого следует, что если в массиве есть несколько элементов, совпадающих с элементом х, то в результате работы программы будет найден первый из них, т.е. элемент с наименьшим индексом.

в режиме пошагового просмотра при различных значениях х;

модифицировать

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

то, что в заголовке цикла записано достаточно сложное условие,

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

Для этого используем искусственный прием!

искомый элемент х, который будет являться барьерным. Тогда если

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

с максимально возможным индексом.

хранится массив нет, то ускорить поиск нельзя.
Если же известна

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

метод половинного деления.

При его использовании на каждом шаге область поиска сокращается вдвое.

в порядке неубывания чисел, то есть для любого k:

1 ≤ k < n: a[k-1] ≤ a[k].
Найти такое i, что a[i] = x или сообщить, что элемента х в массиве нет.

элементом массива. Если да, то ответ получен. Если нет,

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

15 17 18 20 25
х = 6
Шаг 1.
Найдем номер

среднего элемента:

Так как 6 < a[5]

3 5 6 8 12 15 17 18 20 25

Индекс среднего элемента:

Аналогично:

Шаг 3. Рассматриваем два элемента

A[3] = 6! Его номер – 3

m:
Где L – индекс первого, а R – индекс

последнего элемента рассматриваемой части массива.

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
End;

Begin
a[0]:=x;
L:= 1; R:= n;
Repeat
m:= (L + R) div 2;
if L > R then m:=0
else if a[m] < x then L:= m + 1
else R:= m - 1
until a[m]= x;
ans:= m;
End;

(Списать в тетрадь. Добавить комментарий)