Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

Лабораторная работа 13

Работа добавлена на сайт samzan.net:


Лабораторная работа № 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 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. Значение элемента массива, в положительном случае, выводится на экран монитора.

  1.  



1. Тема музыкального домашнего задания- Великие эпохи а великой эпохой в России принято считать Золотой век р
2. Тема- Учет расчетов с покупателями и поставщиками организации
3. Теоретичні засади функціонування фондового ринку 1
4. Точки роста инновационной среды - актуальные вопросы региональной политики
5. 2008 Введен в действие распоряжение проректора по учебной работе и менеджменту качества 06
6. Оценка деятельности предприятия Центр оптовой торговли VS Лэн
7. Инновационный менеджмент
8. 25 Методы оценки эффективности управленческих решений
9. варианты следует выбрать один или несколько по вашему мнению выделив его жирным шрифтом.html
10. Статья 222 Особенности государственной регистрации прав на земельные участки образуемые при разделе объед
11. Кейлоггер под MS-DOS
12. Реферат- Любовь как этический принцип педагогики
13. Контрольная работа Классификация топливноэнергетических ресурсов
14. Управление
15. Договор найма
16. ТЕМА 11 ВРЕМЯ ОТДЫХА
17. Современные представления о Духовном здоровье
18. Детский сад комбинированного вида 11 Катюша г
19. Реферат Отделочные работы в строительстве Выполнил- Студент гр
20.  Місце і роль освіти у сучасному світі

Материалы собраны группой SamZan и находятся в свободном доступе