Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Lab_rab_Pascal_OZO / Lab_13_Поиск_элемента_в_массиве

.doc
Скачиваний:
16
Добавлен:
21.03.2015
Размер:
71.17 Кб
Скачать

Лабораторная работа № 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: (ваш номер по журналу соответствует номеру варианта)

  1. Напишите программу, которая организует хранение в массиве 15 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. Номер элемента массива, в положительном случае, выводится на экран монитора.

  2. Напишите программу, которая организует хранение в массиве 10 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры вводится контрольное число, наличие которого в массиве необходимо проверить. В положительном случае замените элемент массива, равный контрольному числу, нулём. Содержимое массива выводится на монитор.

  3. Напишите программу, которая организует хранение в массиве 15 различных целых чисел. Содержимое массива сортируется по убыванию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. На экран монитора выводится содержимое массива до "контрольного числа" включительно.

  4. Дан массив А состоящий из 15 целых чисел. Отсортируйте первую половину массива по убыванию, а вторую по возрастанию. Введите контрольное число и определите его наличие в массиве А. В положительном случае выведите найденное число и его индекс на экран.

  5. Напишите программу, которая организует хранение в массиве 10 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры вводится контрольное число, наличие которого в массиве необходимо проверить. В отрицательном случае замените элементы массива, неравные контрольному числу, нулём. Содержимое массива выводится на монитор.

  6. Дан массив из 10 целых чисел. Отсортируйте его и найдите в нём контрольное число. Все элементы до контрольного числа замените на противоположные.

  7. Дан массив А состоящий из 20 целых чисел. Отсортируйте его по убыванию. Введите с клавиатуры 2 контрольных числа a и b. Определите наличие в массиве чисел, лежащих в диапазоне от a до b. В положительном случае выведите найденные числа и их индексы в массиве на экран.

  8. Дан массив А состоящий из 20 целых чисел. Отсортируйте первую половину массива по возрастанию, а вторую по убыванию. Введите контрольное число и определите его наличие в массиве А. В положительном случае выведите найденное число и его индекс на экран.

  9. Дан массив из 10 целых чисел. Отсортируйте его и найдите в нём контрольное число. Все элементы после контрольного числа замените на 5.

  10. Дан массив А состоящий из 20 целых чисел. Отсортируйте его по возрастанию. Введите с клавиатуры 2 контрольных числа a и b. Определите наличие в массиве чисел, лежащих в диапазоне от a до b. В положительном случае выведите на экран количество найденных чисел.

  11. Напишите программу, которая организует хранение в массиве 15 различных целых чисел. Содержимое массива сортируется по убыванию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. Значение следующего элемента массива, в положительном случае, выводится на экран монитора.

  12. Напишите программу, которая организует хранение в массиве 15 различных целых чисел. Содержимое массива сортируется по убыванию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. На экран монитора выводится содержимое массива после "контрольного числа".

  13. Напишите программу, которая организует хранение в массиве 10 различных целых чисел. Содержимое массива сортируется по убыванию. После этого, с клавиатуры вводится контрольное число, наличие которого в массиве необходимо проверить. В положительном случае замените элемент массива, равный контрольному числу, нулём. Содержимое массива выводится на монитор.

  14. Дан массив А состоящий из 20 целых чисел. Отсортируйте его по убыванию. Введите с клавиатуры 2 контрольных числа a и b. Определите наличие в массиве чисел, лежащих в диапазоне от a до b. В положительном случае выведите сумму найденных чисел на экран.

  15. Напишите программу, которая организует хранение в массиве 15 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. Значение элемента массива, в положительном случае, выводится на экран монитора.