Презентация по информатике на тему "Реализация алгоритмов обработки массивов на языке программирования PASCAL"

МАССИВЫ
Подготовил учитель информатики
МОУ «СОШ № 1 г. Верхнеуральска»
Ивановский Константин Борисович
Реализация алгоритмов обработки массивов на языке программирования
PASCAL

Содержание
1. Формирование (задание) массива
1.1. Описание массива данных.
1.2. Формирование массива вводом данных с клавиатуры.
1.3. Формирование массива с использованием функции RND.
1.4. Формирование массива чтением данных из файла.
1.5. Формирование двумерного массива.
1.6. Нахождение суммы массива.
2. Организация поиска данных в массиве.
2.1. Поиск по заданному условию.
2.2. Поиск минимального (максимального) элемента массива.
2.3. Поиск в двумерном массиве.

3. Сортировка массива данных.
3.1. Сортировка массива по убыванию (возрастанию) элементов.

1.1. Описание массива данных
Массив – именованный набор с фиксированным количеством однотипных данных.
Массив – совокупность однотипных данных, каждое из которых идентифицируется с именем массива и индексом (индексами).
Массив – упорядоченный (каждый элемент имеет порядковый номер) набор однотипных данных, объединенных общим именем (идентификатором).
Количество индексов в списке определяет размерность массива. Все элементы имеют одно и то же имя, а следовательно и один и тот же тип. Этот тип, также как и размерность массива должен быть описан в программе.
Для определения массивов используется зарезервированное слово array (массив).
Var T : array [ 1 . . 12 ] of integer;
После слова array в квадратных скобках указан начальный и конечный номера (индексы) элементов массива, а после служебного слова of – тип его элементов (в данном случае integer). Обнаружив такой тип данных, компилятор для переменной с именем t выделит 12 последовательных ячеек памяти с размером 2 байта каждая. Каждая отдельная ячейка имеет свой номер. После выделения места во все такие числовые ячейки записывается значение нуль.
a[1]:=2; a[2]:=83; a[3]:=14; a[4]:=-7; . . . a[8]:=18;

1.1. Описание массива данных.
Чаще всего номера элементов меняются от 1 до заданного числа N. Поместив значение N в разделе констант (const), в описании можно указать в качестве переменной N последнее значение (верхнюю границу) номера элементов массива.
Пример:

Const n=5;
Var a : array [1 .. n] of integer;
Begin
readln(a[1]);
readln(a[2]);
readln(a[3]);
readln(a[4]);
readln(a[5]);
End.
Для ввода данных в память ЭВМ необходимо организовать цикл. Поскольку число повторений ввода данных известно (это размерность массива), удобно использовать цикл пересчет (цикл “до”).
Пример:

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
Begin
for i:=1 to n do
readln(a[i]);
End.

1.2. Формирование массива вводом данных с клавиатуры
Добавив в предыдущую программу комментарий, изменим программу так, чтобы можно было вводить каждое очередное значение массива в отдельной строке.

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
Begin
writeln(‘Введите элементы массива’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
End.
Для исходных данных: 3, -2, 9, 7, -1 результат работы программы на экране будет выглядеть следующим образом:

Введите элементы массива
a[1]=3
a[2]=-2
a[3]=9
a[4]=7
a[5]=-1

1.3. Формирование массива c использованием функции Random
При использовании функции генерации случайного числа программа будет отличаться только одной строкой – элементу массива присваивается значение генерируемое функцией Random, и вывод полученного значения на экран должен производиться позже.

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
End.

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
Begin
randomize;
writeln(‘Полученный массив:’);
for i:=1 to n do
begin
a[i]:=Random(100);
write(‘ a[‘,i,’]=‘,a[i]);
end;
End.
Для данной программы результатом ее выполнения может стать любой набор пяти случайных чисел в пределах от 0 до 100. На экране результат работы программы будет выглядеть следующим образом:

Полученный массив:
a[1]=31 a[2]=87 a[3]=2 a[4]=97 a[5]=12 _

1.3. Формирование массива c использованием функции Random
Часто в задачах требуется получить не просто случайный набор чисел, а случайный набор чисел из конкретного диапазона. Например: Получить массив случайных целых чисел в пределах от 80 до 250 (или, иногда говорят, из диапазона [80,250] ). Строка генерации элементов будет выглядеть следующим образом:
a[i]:=80+Random(170);
a[i]:=A+Random(B-A);
Обозначим A=80, B=250. Формула в общем виде будет выглядеть так:
Для того, чтобы вывести элементы массива в столбик необходимо оператор write заменить на оператор writeln.

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
Begin
randomize;
writeln(‘Полученный массив:’);
for i:=1 to n do
begin
a[i]:=80+Random(170);
writeln(‘ a[‘,i,’]=‘,a[i]);
end;
End.

Полученный массив:
a[1]=176
a[2]=87
a[3]=215
a[4]=197
a[5]=248

1.4. Формирование массива чтением данных из файла.
Рассмотрим случай, когда нам известно количество элементов (5), содержащихся в файле mas.dat, и известно место расположения файла (корневой каталог диска С:\ ).

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
f : file of integer;
Begin
assign(f,’C:\mas.dat’);
writeln(‘Считанный массив:’);
reset(f);
for i:=1 to n do
begin
read(f,a[i]);
writeln(‘ a[‘,i,’]=‘,a[i]);
end;
close(f);
End.

Const n=5;
Var a : array [1 .. n] of integer;
i : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
End.
Из сравнения двух программ видно, что в основе лежит та же самая структура. Только в последнем случае к исходной программе добавились команды необходимые для работы с файлами последовательного доступа. Вывод результатов на экран происходит аналогично выше разобранной программе.

1.5. Формирование двумерного массива.
Двумерный массив представляет собой таблицу, в которой каждый элемент имеет два индекса – номер строки и номер столбца в таблице. Задается такой массив аналогично:
Существуют определенные стандарты оформления: - переменной i обозначают номера строк; - переменной j обозначают номера столбцов; - переменной n обозначают количество строк; - переменной m обозначают количество столбцов. Величину N x M называют рангом матрицы.

Const n=3; m=3;
Var a : array [1 .. n, 1 .. m] of integer;
В этом случае мы имеем массив размерностью 3х3, 3 строки по 3 элемента в каждой. В номере ячейки массива первая цифра – это номер строки, вторая – номер столбца. a[1,2]=11, a[2,1]=64, a[3,1]=18.
Чтобы задать, или обработать двумерный массив, в котором каждый элемент имеет два индекса: номер строки и номер столбца, понадобится два цикла. Первый цикл (по i ) перебирает номера строк. Для каждого i второй цикл (по j ) перебирает номера столбцов.

for i:=1 to n do
for j:=1 to m do
Результатом работы двух циклов будет следующая комбинация номеров i, j : 1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,2 3,3

1.5. Формирование двумерного массива.
Для простоты и удобства написания программ первое время блок вывода массива на экран лучше выделять отдельно после формирования элементов массива.

Const n=3; m=3;
Var a : array [1..n,1..m] of integer;
i, j : integer;
Begin
randomize;
for i:=1 to n do
for j:=1 to m do
a[i]:=Random(100);
writeln(‘Полученный массив:’);
for i:=1 to n do
for j:=1 to m do
write(a[i,j]:4);
End.

Полученный массив:
25 11 8 64 50 6 18 97 38









Работая с таблицей мы при выводе на экран получаем строчную запись массива (как в случае с одномерным массивом). Дело в том, что оператор write после вывода информации на экран устанавливает курсор следом за выведенной информацией. А замена write на writeln приведет к тому, что наш массив будет выведен в один столбец (опять же, как в случае с одномерным массивом).
Решить эту проблему можно только выполнив команду writeln; после окончания выполнения цикла по j, когда все элементы строки уже выведены на экран. Т.е. Вывод очередной строки будет начинаться на экране с новой строчки.

1.5. Формирование двумерного массива.
Итак, давайте сравним два варианта программы. Слева исходная и справа с добавленной командой writeln …

Const n=3; m=3;
Var a : array [1..n,1..m] of integer;
i, j : integer;
Begin
randomize;
for i:=1 to n do
for j:=1 to m do
a[i]:=Random(100);
writeln(‘Полученный массив:’);
for i:=1 to n do
for j:=1 to m do
write(a[i,j]:4);
End.

Полученный массив:
11 8
64 50
6 18




Const n=3; m=3;
Var a : array [1..n,1..m] of integer;
i, j : integer;
Begin
randomize;
for i:=1 to n do
for j:=1 to m do
a[i]:=Random(100);
writeln(‘Полученный массив:’);
for i:=1 to n do
begin
for j:=1 to m do
write(a[i,j]:4);
writeln;
end;
End.

1.6. Нахождение суммы элементов массива.
Вычисление суммы элементов массива ничем не отличается от суммирования значений простых переменных. Решение этой задачи состоит из трех основных частей (этапов): 1) ввод данных; 2) вычисление суммы; 3) печать результатов.

Const n=7;
Var a : array [1..n] of integer;
i : integer;
s : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
s:=0;
for i:=1 to n do
s:=s+a[i];
writeln(‘Сумма элементов S=’,s);
End.

Введите элементы:
a[1]=3
a[2]=-2
a[3]=9
a[4]=7
a[5]=-1
a[6]=6
a[7]=1
Сумма элементов S=23



Результат выполнения программы на экране:
Выполнение блока вычисления суммы представлено в следующей таблице:

2.1. Поиск элементов массива по заданному условию.
Поиск по ключу одна из важных невычислительных задач. Осуществим поиск путем сплошного перебора. Если элемент равный данному найден то напечатаем его номер.

Const n=7;
Var a : array [1..n] of integer;
i : integer;
x : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
write(‘Введите число х=’);
for i:=1 to n do
if a[i]=x then
write(‘N элемента равного х - ’,i);
End.

Введите элементы:
a[1]=3
a[2]=-2
a[3]=9
a[4]=7
a[5]=-1
a[6]=6
a[7]=1
Введите число х=-1
N элемента равного х - 5



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

2.2. Поиск минимального элемента массива.
Первое число запоминаем сразу как «наименьшее». Начиная со второго числа и до последнего будем сравнивать каждое из них с нашим «наименьшим». Если сравниваемый элемент окажется меньше, то мы запомним его как «наименьшее». В итоге сравнив «наименьшее» со всеми элементами решим поставленную задачу.

Const n=7;
Var a : array [1..n] of integer;
i : integer;
min : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
min:=a[1];
for i:=2 to n do
if min>a[i] then min:=a[i];
write(‘наим-ший элемент = ’,min);
End.
В случае поиска максимального элемента в программе следует заменить следующие строки:
. . .
max : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
max:=a[1];
for i:=2 to n do
if max<a[i] then max:=a[i];
write(‘наибольший элемент = ’,max);
End.
Необходимо найти минимальное число в следующей последовательности: 3, -1, 9, 7, -3, -5, 1

2.2. Поиск минимального и максимального элементов в массиве.
Задачу поиска максимального и минимального элементов можно объединить в одной программе.
Причем программа изменится не значительно. В цикле добавляется составной оператор
begin … end;

Const n=7;
Var a : array [1..n] of integer;
i : integer;
min, max : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
min:=a[1]; max:=a[1];
for i:=2 to n do
begin
if min>a[i] then min:=a[i];
if max<a[i] then max:=a[i];
end;
writeln(‘MIN=’,min,’ MAX= ’,max);
End.
Но в задачах на поиск минимальных, максимальных элементов часто требуется найти не само значение, а индекс (номер элемента в массиве), чтобы потом можно было производить изменения в массиве, переставляя элементы, или изменяя их значения в зависимости от поставленной задачи.

2.3. Поиск минимального элемента в двумерном массива.

Const n=3; m=3;
Var a : array [1..n,1..m] of integer;
i, j : integer;
min : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
for j:=1 to m do
begin
write(‘a[‘,i,’,’,j,’]=‘);
readln(a[i,j]);
end;
min:=a[1,1];
for i:=1 to n do
for j:=1 to m do
if min>a[i,j] then min:=a[i,j];
writeln(‘MIN=’,min);
End.
Задачу поиска максимального и минимального элементов в двумерном массиве резко отличается от предыдущих вариантов. Дело в том, что мы будем обрабатывать не одну строку, а несколько и поэтому не имеем права начинать сравнение со второго элемента. Необходимо перебрать полностью все элементы массива начиная с а[1,1] и заканчивая элементом a[n,m].
Но в задачах на поиск минимальных, максимальных элементов в двумерном массиве иногда приходится искать минимальный элемент в какой-то одной строке или столбце. Это существенно упрощает задачу. Мы фиксируем один из параметров ( i – строку, или j – столбец ) и обрабатываем как одномерный массив.
Например: для предыдущей задачи найти максимум во второй строке.
. . .
end;
min:=a[2,1];
for j:=2 to m do
if min>a[2,j] then min:=a[2,j];
writeln(‘MIN второй строки =’,min);
End.

3.1. Сортировка массива.
Упорядочения массивов по какому-либо признаку называются сортировкой. Существуют различные методы, различающиеся, в основном, по скорости получения результата.
«ПУЗЫРЬКОВАЯ СОРТИРОВКА»
Зафиксируем первый элемент а[1]=3 и будем последовательно сравнивать его со стоящими справа. Если какой-то из элементов справа окажется меньше первого, то мы поменяем местами этот элемент с первым и продолжим сравнение уже нового элемента, стоящего на первом месте с оставшимися числами:
В результате первого просмотра последовательности на первом месте окажется наименьший из всех элементов, т.е. он, как более «легкий» всплывает наверх (отсюда и название). Теперь зафиксируем второй элемент и повторим просмотр, производя по необходимости перестановки.
Необходимо упорядочить следующую последовательность чисел: 3, -1, 9, 7, -3
3 -1 9 7 -3
3 > -1
-1 3 9 7 -3
3  -1
-1 3 9 7 -3
-1 < 9
-1 3 9 7 -3
-1 < 7
-1 3 9 7 -3
-1 > -3
-1  -3
-3 3 9 7 -1
-3 3 9 7 -1
-3 -1 9 7 3
. . . . . . . . . . . .
-3 -1 9 7 3
. . . . . . . . . . . .
-3 -1 3 9 7
-3 -1 3 9 7
. . . . . . . . . . . .
-3 -1 3 7 9
-3 -1 3 7 9

3.1. Сортировка массива.

Const n=7;
Var a : array [1..n] of integer;
i, j : integer;
c : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then begin
c:=a[i];
a[i]:=a[j];
a[j]:=c;
end;
writeln(‘Упорядоченный массив:’);
for i:=1 to n do
writeln(a[i]);
End.
Уяснив идею решения, остановимся на двух вопросах: каким образом фиксировать элементы и как осуществлять перестановку двух элементов?
Чтобы при переборе элементов, стоящих справа от проверяемого, не менялся индекс последнего, индексы фиксируемого и стоящих правее него элементов должны быть различными: i и j.
Индекс i изменяется от 1 до n-1, индекс j всегда на 1 больше i и пробегает все значения от i+1 до n.
Для каждого значения i индекс j должен последовательно принять все допустимые значения, следовательно, конструкция программы, отражающей полный перебор всех элементов, представляет собой двойной (вложенный) цикл.
При перестановке двух элементов используется третья переменная- вспомогательная. Перестановка двух переменных a и b при помощи переменной c выглядит следующим образом
1) с:=a2) a:=b3) b:=c

3.1. Сортировка массива.

Const n=7;
Var a : array [1..n] of integer;
i, j : integer;
c : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then begin
c:=a[i];
a[i]:=a[j];
a[j]:=c;
end;
writeln(‘Упорядоченный массив:’);
for i:=1 to n do
writeln(a[i]);
End.
Сортировки массива по возрастанию
Сортировка двумерного массива не имеет смысла!! Иногда встречаются задачи в которых необходимо отсортировать отдельную строку или столбец. А такие задачи приводятся к решению с одномерным массивом …
Сортировки массива по убыванию

Const n=7;
Var a : array [1..n] of integer;
i, j : integer;
c : integer;
Begin
writeln(‘Введите элементы:’);
for i:=1 to n do
begin
write(‘a[‘,i,’]=‘);
readln(a[i]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]<a[j] then begin
c:=a[i];
a[i]:=a[j];
a[j]:=c;
end;
writeln(‘Упорядоченный массив:’);
for i:=1 to n do
writeln(a[i]);
End.