Ввод/вывод массивов

Ввод осуществляется либо с клавиатуры, либо из файла, либо с помощью датчика случайных чисел (иногда можно пользоваться формулами).

Пример ввода массива с клавиатуры: for i:= 1 to 10 do begin

write (‘m[‘,i:2,’]=’);

readln (m[i]); end;

Пример вывода одномерного массива: for i:= 1 to 10 do begin выводит

write (‘m[‘,i:2,’]=’); в виде

writeln (m[i]); end; столбика

for i:= 1 to 10 do begin выводит

write (‘m[‘,i:2,’]=’); в виде

write (m[i],’ ‘); end; строки

writeln;

Области применения массивов:

1. Ввод/вывод связных данных одномерного массива

2. Перебор данных: поиск, выборка

3. Сортировка данных по возрастанию/убыванию ключевого выражения

4. Построение графика функции

5. Реализация численных методов решения задач на ЭВМ (СЛАУ, ДУ, сеточные методы и т.д.)

6. Вычисление каких-то характеристик массива: суммы, произведения, дисперсии, коррекции и т.д.

Основные алгоритмы обработки данных. Поиск заданного элемента массива методом перебора. Бинарный поиск. Поиск максимального и минимального элемента массива. Сортировка данных. Простая и быстрая сортировка. Сортировка массива методом «пузырька».

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

Для организации поиска в массиве могут быть использованы различные алгоритмы. Наиболее простой – это алгоритм простого перебора. Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или не будут проверены все элементы. Алгоритм простого перебора применяется, если элементы массива не упорядочены.

Поиск в массиве методом перебора элементов

Программа поиска в массиве целых чисел методом перебора элементов. Перебор элементов массива осуществляет инструкция repeat, в теле которой инструкция if сравнивает текущий элемент массива с образцом и присваивает переменной found значение true, если текущий элемент равен образцу. Цикл завершается, если в массиве обнаружен элемент, равный образцу (в этом случае значение переменной found равно true), или если проверены все элементы массива. По завершении цикла по значению переменной found можно определить, успешен поиск или нет.

Program poisk;

Var

massiv: array[1..10] of integer {массив целых}

obrazec: integer {образец для поиска}

found: boolean {признак совпадения с образцом}

i:integer;

Begin

{ввод 10 целых чисел}

writeln(‘Поиск в массиве’);

write(‘Введите 10 целых в одной строке через пробел’);

writeln(‘и нажмите <Enter>’);

write(‘->’);

for i:=1 to 10 do

read(massiv[i]);

{числа введены в массив}

write(‘Ведите образец для поиска (целое число) -> ’);

readln(obrazec);

{поиск простым перебором}

found:=false; {совпадений нет}

i:=1;

repeat

if massiv[i]=obrazec

then found:=true; {совпадение с образцом}

else i:=i+1; {переход к следующему элементу}

until (i>10) or (found); {завершим, если совпадение с образцом или проверен последний элемент массива}

if found

then writeln(‘Совпадение с элементом номер’, i,’. Поиск успешен.’)

else writeln(‘Совпадений с образцом нет.’);

end.

Очевидно, что чем больше элементов в массиве и чем дальше расположен нужный элемент от начала массива, тем дольше будет программа искать нужный элемент.

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

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

Для поиска в упорядоченных массивах применяют другие, более эффективные по сравнению с методом простого перебора, алгоритмы, один из которых – метод бинарного поиска.

Суть метода бинарного поиска: выбирается средний (по номеру) элемент упорядоченного, например, по возрастанию массива (элемент с номером sred), и с этим элементом сравнивается образец.

Если средний элемент равен образцу, то задача решена.

Если средний элемент меньше образца, то искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred).

Если средний элемент больше образца, то искомый элемент расположен ниже среднего (между элементами с номерами sred и niz).

После того, как определена часть массива, в которой может располагаться искомый элемент, поиск проводят в этой части, выделяя новый средний элемент. Номер среднего элемента вычисляется по формуле: (niz-verh)/2 +verh.

Программы бинарного поиска в упорядоченном массиве. В программу добавлены операторы вывода значений переменных verh, niz и sred. Выводимая информация полезна для понимания сути алгоритма. Кроме того, переменная n позволяет оценить эффективность этого алгоритма по сравнению с поиском методом простого перебора (для массивов, упорядоченных по возрастанию).

Program poisk1;

Var

A:array[1..9] of integer; {массив целых}

Obrazec:integer; {образец для поиска}

Sred, verh, niz: integer; {номера среднего, верхнего и нижнего элементов массива}

Found:boolean; {признак совпадения с образцом}

I:inteher;

Begin

{ввод 9 целых чисел}

Writeln(‘Бинарный поиск в массиве.’);

Write(‘Ведите 9 целых в одной строке через пробел ’);

Writeln(‘и нажмите <Enter>’);

For i:=1 to 9 do

Read(a[i]);

{здесь числа в массив введены}

Writeln(‘Введите образец для поиска (целое число)’);

Readln(obrazec);

{бинарный поиск}

Verh:=1;

Niz:=9;

Found:=false;

N:=0;

Writeln(‘ verh niz sred’);

Repeat

Sred:=(niz-verh) div 2 +verh;

Writeln(verh:6,niz:6sred:6);

N:=n+1;

If a[sred]=obrazec then found=true

Else begin

If obrazec<a[sred]

Then niz:=sred-1

Else verh:=sred+1;

End;

Until (verh>niz) or found;

If found

Then write(‘Совпадение с элементом номер ’, sred, ‘. Выполнено n сравнений.’)

Else witeln(‘Образец в массиве не найден.’);

Readln;

End.

Поиск минимального (максимального) элемента массива

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

Program mine1;

Const

Granica=10;

Var

A:array[1..granica] of integer; {массив целых}

Min:integer; {номер минимального элемента массива}

I:integer; {номер элемента, сравниваемого с минимальным}

Begin

{здесь инструкция ввода массива}

Min:=1; {пусть первый элемент - минимальный}

For i:=2 to granica do

If a[i]<a[min] then min:=i;

Writeln(‘Минимальный элемент массива:’,a[min]);

Writeln(‘Номер элемента: ’,min);

End.

Нахождения max и (min)

…….Begin

Y:=x[1]

m:=1

for k:=2 to 20 do

if y<(>) x[k] then

y:=x[k]…….

Дата добавления: 2015-07-11