Загрузка...
Учебная работа. Реферат: Массивы. Основные алгоритмы обработки массивов на примере языка программирования Pascal
Оглавление
Введение. 3
1. Определение и типы массивов. 4
2. Главные операции обработки массивов. 7
2.1 Определение размерности массива, наполнение массива. 7
2.2 Вывод массива на экран. 9
2.3 Поиск требуемого элемента в массиве. 10
2.4 Поиск наибольшего и малого частей массива. 12
2.5 Сортировка частей массива. 13
3. Индивидуальности обработки двумерных массивов. 15
4. Обработка квадратных матриц. 17
4.1 Определение диагоналей массива. 17
4.2 Определение четвертей матрицы.. 18
5. Открытые массивы.. 20
Перечень литературы.. 21
Введение
Тема данного реферата «Массивы. Главные методы обработки массивов на примере языка программирования Pascal». Актуальность избранной темы обоснована тем, что массивы весьма обширно употребляются при разработке различного рода приложений. Массивы являются всераспространенным и полезным методом сохранения почти всех разных частей связанных данных. Массивы полезны при разработке отсортированных и неотсортированных списков данных, при сохранении таблиц данных и для выполнения почти всех остальных задач. С понятием «массив» приходится работать и при решении научно-технических и экономических задач, связанных с обработкой совокупностей огромного количества значений.
Массив является комфортным методом хранения нескольких связанных частей данных в едином контейнере для большего удобства и эффективности программирования. Массив дозволяет сохранять и манипулировать почти всеми элементами данных средством единственной переменной. Не считая уменьшения общего числа разных имен переменных, которые нужно выслеживать, остальным главным преимуществом использования массивов будет то, что можно применять циклы для легкой обработки разных частей массивов. Объединяя массивы и циклы можно написать маленькое число операторов, которые обрабатывают большенный размер данных. Выполнение тех же задач с внедрением отдельных переменных может востребовать написания сотен операторов.
В связи со всем изложенным выше цель данной работы – разглядеть главные методы обработки массивов очень близко к практическому их применению.
1.
Определение и типы массивов
Массив — это огромное количество однотипных частей, объединённых общим именованием и занимающих в компе определённую область памяти. количество частей в массиве постоянно естественно. В общем случае массив — это структурированный тип данных, состоящий из фиксированного числа частей, имеющих один и этот же тип.
Иными словами можно сказать, что массив представляет собой фиксированное количество упорядоченных однотипных компонент, снабженных индексами, т.е. является совокупой конечного числа данных 1-го типа. В качестве частей массива можно применять хоть какой тип данных, потому полностью правомерно существование массивов записей, массивов указателей, массивов строк, массивов и т.д.
Массивы могут быть:
· одномерными (одна строчка – несколько столбцов);
· многомерными (несколько строк – несколько столбцов).
Для сотворения массива его за ранее нужно обрисовать или в разделе var, или в разделе type. Для задания массива употребляется зарезервированное слово array
, опосля которого указывается тип индекса (-ов) компонент (в квадратных скобках) и опосля слова of
—
тип самих компонент:
Type
<имя массива>=
array
[<тип индекса(-ов)>]
of
<тип компонент>;
Либо
V
ar
<имя массива>:
array
[<тип индекса(-ов)>]
of
<тип компонент>;
Введя тип массив, можно задавать переменные либо типизированные константы этого типа. Размерность массива быть может хоть какой, составляющие массива могут быть хоть какого, в том числе и структурированного, типа; индекс быть может хоть какого порядкового типа, не считая типа longint.
При задании значений константе-массиву составляющие указываются в круглых скобках и делятся запятыми, при этом, если массив многомерный, наружные круглые скобки соответствуют левому индексу, вложенные в их круглые скобки — последующему индексу и т.д.
к примеру
,
Type
arr = array [1..3] of real;
matrix = array [1..3, 1..2] of integer;
Const
mas1: arr = (1, 2, 3);
mas2: matrix = ((1, 2), (3, 4), (5, 6));
Тип массив можно вводить и конкретно при определении соответственных переменных либо типизированных констант.
к примеру,
Var
m1, m2 : array [1..3] of integer;
matr : array [1..3, 1..3] of real;
Доступ к компонентам массива осуществляется указанием имени массива, за которым в квадратных скобках помещается
к примеру,
m1 [2], matr[i,j].
Для обработки массива и поочередного доступа к данным, как правило, употребляется цикл FOR.
К примеру
,
for i:=1 to 10 do read(mas[i]);
Обработка частей двумерного массива обычно производится при помощи двойного цикла. один цикл управляет перебором номеров строк, иной — столбцов.
К примеру,
for i:=1 to 10 do
for j:=1 to 10 do read(mas[i, j]);
Над элементами массива можно создавать те же операции, которые допустимы для данных его базисного типа. Если два массива имеют схожие типы индексов и схожие типы частей, то к ним применимы булевы операции (<>=).
2.
Главные операции обработки массивов
2.1 Определение размерности массива, наполнение массива
Размерностью массива именуется количество ячеек данного массива. При описании массива нужно указывать конкретное число ячеек, но при реализации задачки не постоянно нужно заполнять все зарезервированные ячейки.
к примеру,
Задачка 1.
«Дан одномерный массив из 10 компонент…» — эта формулировка значит, что и при описании и при обработке массива постоянно будут употребляться 10 ячеек.
задачка 2.
«Дан массив размерность N…» — данная формулировка значит, что размерность массива будет определяться самим юзером. Т.е. от разраба таковой программки требуется:
· найти наивысшую размерность массива (как правило, полностью довольно 100 ячеек);
· отдать возможность юзеру указать количество требуемых ячеек (writeln(“Введите размерность массива”);
readln(n)- сейчас n обозначает размерность).
Для того чтоб заполнить массив нужно поочередно перебрать все ячейки (составляющие) массива и записать в их некие значения. Для перебора ячеек массива употребляется цикл for
, в каком при помощи счетчика перебираются индексы ячеек. Заносимые в массив данные могут запрашиваться как с клавиатуры, так и выбираться случайным образом при помощи генератора случайных чисел Random.
к примеру,
метод 1.
Наполнение одномерного массива с клавиатуры
writeln(“Введите размерность массива”);
readln(n);
For i:=1 to n do
Begin
Writeln(“Введите ”,i,” элемент массива”);
Readln(mas[i]);
End;
Ход выполнения:
i
=
Writeln
Readln
действие
Шаг 1
1
Введите 1 элемент массива
Mas[1]
Считываем число в 1 ячейку
Шаг 2
2
Введите 1 элемент массива
Mas[2]
Считываем число в 2 ячейку
Шаг 3
3
Введите 1 элемент массива
Mas[3]
Считываем число в 3 ячейку
…
…
…
…
…
Шаг
n
n
Введите n элемент массива
Mas[n]
Считываем число в последнюю ячейку
метод 2.
Наполнение массива случайными числами
writeln(“Введите размерность массива”);
readln(n); {определяем размерность массива}
Randomize; {включаем генератор случайных чисел}
For i:=1 to n do {начинаем перебирать массив}
Mas[i]:=random(100) {выбор хоть какого числа из обозначенного спектра и размещение его в массиве}
Ход выполнения:
i
=
Random
Mas[i]
действие
Шаг 1
1
Хоть какое число до 100
Хоть какое число до 100
Считываем выбранное число в массив
Шаг 2
2
Хоть какое число до 100
Хоть какое число до 100
Считываем число в 2 ячейку
Шаг 3
3
Хоть какое число до 100
Хоть какое число до 100
Считываем число в 3 ячейку
…
…
…
Шаг
n
n
Хоть какое число до 100
Хоть какое число до 100
Считываем число в последнюю ячейку
2.2 Вывод массива на экран
Для вывода массива нужно поочередно перебрать все ячейки (составляющие) массива и вывести лежащие там значения на экран при помощи оператора write
/
writeln
.
Оператор write
выведет значения массива в строчку
Оператор writeln
выведет значения массива в столбец
Для перебора ячеек массива употребляется цикл for
, в каком при помощи счетчика перебираются индексы ячеек.
метод 1
. Вывод одномерного массива размерностью 3 при помощи оператора writeln
Writeln(‘Массив’);
For i:=1 to 3 do
Массив
1
2
3
Writeln(mas[i]);
Экранное метод 2.
Вывод одномерного массива размерностью 3 при помощи оператора write
Writeln(‘Массив:’);
For i:=1 to 3 do
Массив
1 2 3
Write(mas[i],’ ‘);
Экранное метод поиска в массиве определенного элемента можно представить последующим образом:
Набросок 1. Блок-схема поиска требуемого элемента в массиве
к примеру,
Дан одномерный массив из 7 ячеек. Найти, сколько в нем чисел кратных 7.
Var
mas:array[1..7] of integer;
i:integer; {нужна для перебора массива}
kol:integer; {количество пригодных частей}
begin
for i:=1 to 7 do
begin
write(‘Введите’ ,i, ‘ элемент’);
readln(mas[i]); {заполняем массив}
if (mas[i] mod 7 =0) and (mas[i]<>0) then kol:=kol+1
{если элемент делится на 7 и в остатке ноль и при всем этом сам элемент не равен нулю, то увеличиваем счетчик kol}
end;
writeln(“Количество чисел кратных 7 -”, kol) {вывод результата}
end.
Ход выполнения:
9
-7
0
14
5
21
-5
Элементы
1
2
3
4
5
6
7
Индексы
Введенный массив
i
=
Readln(mas[i])
Проверка
(mas[i] mod 7 =0) and (mas[i]<>0)
действие
Шаг 1
1
Mas[1]=9
ересь
Kol=0
Шаг 2
2
Mas[2]=-7
правда
Kol=0+1
Шаг 3
3
Mas[3]=0
ересь
Kol=1
Шаг
4
4
Mas[4]=14
правда
Kol=1+1
Шаг
5
5
Mas[5]=5
ересь
Kol=2
Шаг
6
6
Mas[6]=21
правда
Kol=2+1
Шаг 7
7
Mas[7]= -5
ересь
Kol=3
Вывод результата на экран
2.4 Поиск наибольшего и малого частей массива
Общий метод работы можно представить в последующем виде:
· определяются переменные (max и min), в каких в итоге выполнения метода разместятся соответственно наибольшее и малое значения;
· начинается перебор массива с одновременной проверкой «является ли просматриваемый элемент больше наибольшего либо меньше малого»; в случае, если условие поистине –
Главный метод смотрится последующим образом:
Max:= — 32000;
Min:= 32000;
For i:=1 to n do
begin
If mas[i]>max then max:=mas[i];
If mas[i]<min then min:=mas[i];
End;
Ход выполнения:
9
-7
0
-10
Элементы
1
2
3
4
Индексы
Введенный массив
i
=
Данные
Условие
Ответ
действие
Шаг 1
1
Max=-32000
Min=32000
Mas[1] = 9
9 > -32000 9 < 32000
правда
правда
Max=9
Min=9
Шаг 2
2
Max=9
Min=9
Mas[2]= — 7
-7 > 9
-7 < 0
ересь
правда
Max=9
Min= — 7
Шаг 3
3
Max=9
Min= — 7
Mas[3]=0
0 > 9
0 < -7
ересь
ересь
Max=9
Min= — 7
Шаг
4
4
Max=9
Min= — 7
Mas[4] = — 10
-10 > 9
— 10 < -7
ересь
правда
Max=9
Min= — 10
2.5 Сортировка частей массива
Существует много алгоритмов сортировки массива, но более обычным и понятным является сортировка способом «пузырька», при которой самый «легкий» элемент «всплывает», а самый тяжкий «утопает».
к примеру,
9
-7
0
-8
Элементы
1
2
3
7
Индексы
Дан массив
нужно расположить эти элементы в порядке возрастания, т.е. в итоге работы программки нужно получить массив
-8
-7
0
9
Элементы
1
2
3
7
Индексы
При сортировке способом «пузырька» сравниваются два примыкающих элемента (mas[i] и mas[i+1]). Если mas[i] > mas[i+1], то происходит перестановка частей. Зрительно процесс сортировки можно представить в виде:
Набросок 2. Сортировка способом «пузырька»
Таковым образом, для организации сортировки будет нужно два цикла, которые выстраиваются в последующем порядке:
(n-размерность массива)
For j:=1 to n do {количество просмотров массива}
For i:=1 to n-1 do {перебор частей массива}
If mas[i] > mas[i+1] then begin
t:=mas[i];
mas[i]:=mas[i+1];
mas[i+1]:=t;
end;
Как видно из примера для перестановки частей массива требуется доборная переменная, которая служит временным хранилищем значения ячейки массива.
9
-7
0
-8
Шаг 1.
9
-7
0
-8
9
-7
0
-8
-7
-7
0
-8
Шаг 2.
-7
-7
0
-8
-7
9
0
-8
Шаг 3.
3. Индивидуальности обработки двумерных массивов
Двумерный массив –
структура данных, хранящая внутри себя прямоугольную матрицу. В матрице любой элемент определяется номером строчки и номером столбца, на пересечении которых он размещен.
Для описания двумерных массивов употребляются те же методы, что и для одномерных массивов, но в качестве размерности массива задается двойное
).
Таковым образом, для сотворения двумерного целочисленного массива размерностью 5×7 (5 строк, 7 столбцов) нужно записать:
Метод
1
Type mas=array[1..5,1..7] of integer;
метод
2
Var mas:array[1..5,1..7] of integer;
Для поочередного перебора
всех частей двумерного массива нужно применять т.н. вложенный цикл:
For i:=1 to 5 do {перебор строк матрицы}
For j:=1 to 7 do {перебор столбцов (ячеек) в строке}
Т.е. случае, если индекс столбца (j) дойдет до собственного конечного значения (в примере j = 7).
При таковой организации перебора частей массива процесс перебора будет проходить по последующей схеме:
11
12
13
14
15
16
17
21
22
23
24
25
26
27
31
32
33
34
35
36
37
41
42
43
44
45
46
47
51
52
53
54
55
56
57
Набросок 3. процесс перебора частей двумерного массива
Ход выполнения:
i
=
j
=
Условие перехода на последующую строчку
j
=7
Обрабатываемый элемент
Шаг 1
1
1
нет
Mas[1,1]
Шаг 2
1
2
нет
Mas[1,2]
Шаг 3
1
3
нет
Mas[1,3]
Шаг
4
1
4
нет
Mas[1,4]
Шаг 5
1
5
нет
Mas[1,5]
Шаг 6
1
6
нет
Mas[1,6]
Шаг 7
1
7
да
Mas[1,7]
Шаг 8
2
1
нет
Mas[2,1]
Шаг 9
2
2
нет
Mas[2,2]
Шаг 10
2
3
нет
Mas[2,3]
…
…
…
…
…
Для того чтоб вывести
двумерный массив на экран в виде таблицы нужно опосля вывода содержимого каждой строчки предугадать переход на строчку ниже:
For i:=1 to n do
Begin
For j:=1 to n do
Write(mas[i,j],’ ‘);
Writeln;
End;
4. Обработка квадратных матриц
Если количество строк массива равно количеству столбцов, то таковой массив именуется квадратной матрицей. При работе с квадратной матрицей, в отличие от обыденного двумерного массива, можно выделить:
· диагонали (основная, побочная);
· элементы, расположенные над и под диагоналями;
· четверти матрицы.
11
12
13
14
15
21
22
23
24
25
31
32
33
34
35
41
42
43
44
45
51
52
53
54
55
тут 1-ая цифра номера элемента обозначает номер строчки матрицы (i), 2-ая цифра – номер столбца (j)
Для определения частей, входящих в хоть какой из перечисленных разделов, существует формула, главными составляющими которой являются i – номер строчки, j – номер столбца и N – размерность массива. к примеру, для определения элемента с номером 43, размещенного под побочной диагональю можно применять формулу i+j>N+1
, где i=4, j=3, N=5, таковым образом, получаем 4+3>5+1.
4.1 Определение диагоналей массива
Набросок 4. Диагонали двумерного массива
Таковым образом, в матрице, представленной в п. 4, элементы с номерами 11, 22, 33, 44 и 55 являются элементами главной диагонали. Элементы с номерами 15, 24, 33, 42, 51 – элементы побочной диагонали.
Размещение частей, находящихся над либо под диагональю, определяется по отношению к одной
из диагоналей.
Набросок 5. Размещение частей по отношению к диагоналям
Элементы 12, 13, 14, 15, 23, 24, 25, 34, 35 и 45 размещены над главной диагональю, 21, 31, 32, 41, 42, 43, 51, 52, 53, 54 размещены под главной диагональю. Элементы 11, 12, 13, 14, 21, 22, 23, 31, 32 и 41 размещены над побочной диагональю, 25, 34, 35, 43, 44, 45, 54, 53, 54, 55 размещены под побочной диагональю.
4.2 Определение четвертей матрицы
Относительно обеих
диагоналей элемент массива может находиться в одной из четвертей.
12, 13, 14, 23 – элементы первой четверти
25, 34, 35, 45 – элементы 2-ой четверти
43, 52, 53, 54 – элементы третьей четверти
21, 31, 32, 41 – элементы четвертой четверти
Набросок 6. Определение четвертей матрицы
Используя правила, выставленные на рисунке 6, весьма просто можно программным методом сформировывать матрицы требуемого вида.
к примеру,
сформировать матрицу N × N вида:
4
0
0
0
5
на главной диагонали – 5;
на побочной диагонали – 4;
в I четверти – 0;
во II четверти – 2;
в III четверти – 3;
в IV четверти – 1.
1
4
0
5
2
1
1
4
2
2
1
5
3
4
2
5
3
3
3
4
Var
mas:array[1..100,1..100] of integer; i,j,n:integer;
Begin
Writeln(‘Введите размерность массива’);
Readln(n);
For i:=1 to n do {заполняем массив в согласовании с правилами}
For j:=1 to n do
Begin
If i=j then mas[i,j]:=4;
If i+j<N+1 then mas[i,j]:=5;
If (i<j) and (i+j<N+1) then mas[i,j]:=0;
If (i<j) and (i+j>N+1) then mas[i,j]:=2;
If (i>j) and (i+j>N+1) then mas[i,j]:=3;
If (i>j) and (i+j<N+1) then mas[i,j]:=4;
End;
For i:=1 to n do {выводим приобретенный массив на экран в виде таблицы}
Begin
For j:=1 to n do
Write(mas[i,j],’ ‘);
Writeln;
End;
End.
5. Открытые массивы
Открытые массивы употребляются в процедурах и функциях как характеристики, у каких не задаются размеры. Фактический размер в этом случае определяется при помощи функций High. индексация постоянно начинается с нуля.
К примеру,
Вычислить наибольший элемент в массиве
function Max (Var Mas: array of integer): integer;
Var Ma : integer;
i : Byte;
Begin
Ma : = Mas [0];
for i : = 1 to High (Mas) do
if Ma < Mas [i] then
Ma : = Mas [i];
Max : = Ma
End.
Данная функция может работать с хоть каким одномерным массивом целых чисел.
Перечень литературы
1. А. Епанешников, В. Епанешников Программирование в среде Turbo Pascal 7.0 — М.: «Диалог-Мифи», 1998
2. Информатика: Учеб. пособие для студ. пед. вузов / А.В. Могилев, Н.И. Пак, Е.К. Хеннер – М.: Изд. Центр «Академия», 2001
3. Мизрохи. Turbo Pascal и объектно-ориентированное программирование. – М.: деньги и статистика, 1992
4. Программирование в Delphi – М.: ЗАО «Издательство БИНОМ», 2000
5. Турбо Паскаль 7.0. Исходный курс. Учебное пособие. – М.: «Нолидж», 1998
]]>