Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа № 13.
Поиск элемента в массиве.
Цель: изучение и приобретение навыков упорядочивания (сортировки) массива и получение дальнейших навыков по отладке и тестированию программ.
Оборудование и программное обеспечение: компьютер, Turbo Pascal 7.0.
Место проведения:
Время:
Теоретические сведения: Различают поиск в упорядоченном и неупорядоченном массивах.
Поиск элементов линейного массива, удовлетворяющих определенному условию.
Необходимо просмотреть элементы массива от первого до последнего, проверить выполнение условия для каждого из них и выполнить некоторые действия, если условия истины. В большинстве случаев необходимо не получить требуемые элементы, а найти их количественную характеристику (количество, сумму, произведение и т.д.). Общий вид: A – массив из p элементов, k – условие.
For i:=1 to p do
if k then <действие>;
где <действие> - совокупность операторов.
Линейный поиск.
Линейный поиск элемента - это последовательный просмотр всех элементов массива до тех пор, пока мы не встретим искомый или пока не будет достигнут конец массива. В последнем случае искомого элемента, который называют еще ключом, в массиве нет. При этом мы можем не только констатировать факт наличия или отсутствия элемента в массиве, но и возвратить его индекс. Естественно, элементов с интересующим нас значением в массиве может быть несколько. Поэтому имеет смысл говорить отдельно о поиске первого вхождения элемента в массив, последнего или m-го вхождения.
Рассмотрим этот алгоритм для поиска первого вхождения значения key в массив V. Функция возвращает индекс элемента, если такой найден, или -1 в противном случае.
function LinSearchFirst (V: Vector; num: integer; key: integer) : integer;
var
i : integer;
begin
i:=1;
while ((i <= num)and(V[i] <> key)) do i:=i+1;
if V[i]=key then
LinSearchFirst := i
else
LinSearchFirst := -1;
end;
Двоичный поиск.
Двоичный поиск, называемый также бинарным или поиском делением пополам, используется только для отсортированного массива. При этом сортировка может быть как по возрастанию, так и по убыванию, но это должно учитываться в алгоритме поиска.
При двоичном поиске рассматриваемый диапазон элементов на каждом шаге сокращается наполовину.
Поскольку элементов с заданным значением в массиве может быть несколько, в этом случае можно говорить только о присутствии или отсутствии такого элемента в массиве.
Исходный диапазон представляет собой весь массив. На каждом шаге мы рассматриваем средний элемент диапазона, индекс которого получается как (left+right)/2, где left - индекс левой границы диапазона (на первом шаге равен 1), right - индекс правой границы (на первом шаге равен реальной размерности массива). Поиск заканчивается, когда значение среднего элемента диапазона равно искомому, то есть мы нашли нужный элемент, или когда индекс левой границы становится больше индекса правой, это будет означать, что данного элемента в массиве нет.
Функция поиска элемента одномерного массива методом деления пополам. Возвращает TRUE, если элемент найден, и FALSE в противном случае
function BinSearch (V: Vector; num: integer; key: integer) : boolean;
var
left, right, mid : integer;
begin
left:=1; right:=num;
while left <= right do begin
mid := (left+right) div 2;
if V[mid]=key then begin
BinSearch := TRUE;
exit;
end
else if V[mid] < key then
left := mid+1
else
right := mid-1;
end;
BinSearch := FALSE;
end;
Пример 1. Дан массив из n целых чисел. Найти сумму элементов массива, расположенных между первым минимальным и последним максимальным (в сумму включить и сами эти элементы.)
Program summ_min_max;
uses crt;
const N=15;
type matr=array [1..N] of integer;
var summ,k:integer;
m:matr;
procedure gener(a,b:integer);
var i:integer;
begin
randomize;
for i:=1 to N do
begin
m[i]:=random(b-a)+a;
end;
end;
procedure vivod(x,y,shag:integer);
var i:integer;
begin
for i:=1 to N do
begin
gotoxy(x+shag*(i-1),y);
writeln(m[i]);
end;
end;
function pervyi_min(w:matr):integer;
var i,Mn:integer;
begin
Mn:=1;
for i:=2 to N do
if w[i]<w[Mn] then
begin
Mn:=i;
pervyi_min:=Mn;
end;
end;
function poslednii_max(w:matr):integer;
var i,Mx:integer;
begin
Mx:=1;
for i:=2 to N do
if w[i]>=w[Mx] then Mx:=i;
poslednii_max:=Mx;
end;
begin
clrscr;
summ:=0;
gener(-10,10);
vivod(2,4,5);
gotoxy(2,6);
for k:=pervyi_min(m) to poslednii_max(m) do
summ:=summ+m[k];
writeln('Сумма элементов = ',summ);
writeln;
readln;
end.
Пример 2. Дан массив t из n целых чисел. Найти количество таких i, для которых t[i] больше всех предыдущих.
Program Kolichestvo;
uses crt;
const k=1;
N=15;
type matr=array [1..N] of integer;
var a:integer;
m:matr;
procedure gener(a,b:integer);
var i:integer;
begin
randomize;
for i:=1 to N do
begin
m[i]:=random(b-a)+a;
end;
end;
procedure vivod(x,y,shag:integer);
var i:integer;
begin
for i:=1 to N do
begin
gotoxy(x+shag*(i-1),y);
writeln(m[i]);
end;
end;
procedure kol_elem(x,y:integer);
var i, max,kol:integer;
begin
kol:=1;
max:=m[1];
for i:=2 to N do
if m[i]>max then
begin
max:=m[i];
kol:=kol+1;
end;
gotoxy(x,y);
writeln(kol);
end;
begin
clrscr;
gener(-100,100);
vivod(2,2,5);
gotoxy(2,4);
writeln('количество таких i, для которых t[i] больше всех предыдущих, равно ');
kol_elem(2,6);
writeln;
readln;
end.
Порядок выполнения работы:
Задание: Создать и отладить программу для решения следующую задачу (см. Приложение).
Содержание отчета по каждому заданию:
Приложение лабораторной работе №13: (ваш номер по журналу соответствует номеру варианта)