Курсовая работа по теме: Обработка массивов данных

Комитет образования и науки г. Новокузнецка

12 районная научно - практическая конференция учащихся

Секция прикладная информатика

Обработка массивов данных

Выполнил:

Игнатенко Никита Вадимович, 10Б класс, МНБОУ «Лицей №76»

Научный руководитель:

Зиновьева Татьяна Александровна,

учитель информатики МНБОУ «Лицей №76»

Новокузнецк, 2014

Содержание

1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1. Актуальность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Объект исследования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

3. Предмет исследования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

4. Цель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

5. Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Массив . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1. Преимущество использования массивов . . . . . . . . . . . . . . . . . . . . . . . 4

3. Одномерные массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4. Типовые алгоритмы обработки одномерных массивов и задачи, решаемые с их помощью………………………………………………………………… 6

1. Задачи с использованием типовых алгоритмов обработки одномерных массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2. Обработка строк . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8

3. Типовые алгоритмы обработки строковых переменных . . . . . . . . . .10

4. Сортировка методом «Пузырька» . . . . . . . . . . . . . . . . . . . . . . . . . . . .13

5. Двумерные массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

6. Типовые алгоритмы обработки двумерных массивов и задачи, решаемые с их помощью. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1. Типовые алгоритмы обработки двумерного массива отдельно по столбцам . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . …18

2. Типовые алгоритмы обработки двумерного массива относительно диагоналей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3. Обработка квадратной матрицы относительно диагоналей (рациональный обход). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

7. Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

8. Литература.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24

Введение

Актуальность выбранной темы обусловлена тем, что массивы очень широко используются при разработке различного рода приложений. Массивы являются распространенным и полезным способом сохранения многих различных частей связанных данных. Массивы полезны при создании отсортированных и неотсортированных списков данных, при сохранении таблиц данных и для выполнения многих других задач. С понятием «массив» приходится работать и при решении научно-технических и экономических задач, связанных с обработкой совокупностей большого количества значений.

Объект исследования:

Массивы в программах

Предмет исследования:

Работа с массивами

Цель: рассмотреть основные алгоритмы обработки массивов максимально близко к практическому их применению

Задачи:

1. Изучение типов массивов.

2. Изучение типовых алгоритмов обработки одномерных и двумерных массивов.

3. Группировать задачи по методам решения.

4. Обобщить и систематизировать теоритический и практический материал по теме.

Массив

• Массив это структура, представляющая собой упорядоченную совокупность элементов одного типа, объединенных одним именем. Массивы используются при обработке набора данных одного типа.

• Для получения доступа к элементу массива используется индекс. Индекс определяет местоположения элемента в массиве, является величиной целого типа.

• Каждому массиву отводится место в памяти, последовательно расположенных друг за другом ячеек, в каждую из которых записывается значение соответствующего элемента.

Преимущество использования массивов

Массив является удобным способом хранения нескольких связанных элементов данных в едином контейнере для большего удобства и эффективности программирования.

Массив позволяет сохранять и манипулировать многими элементами данных посредством единственной переменной.

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

Объединяя массивы и циклы можно написать небольшое число операторов, которые обрабатывают большой объем данных. Выполнение тех же задач с использованием отдельных переменных может потребовать написания сотен операторов.

Массив - это множество однотипных элементов, объединённых общим именем и занимающих в компьютере определённую область памяти. Количество элементов в массиве всегда конечно. В общем случае массив - это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип.

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

Массивы могут быть:·

1. одномерными (одна строка - несколько столбцов);·

2. двумерными (несколько строк - несколько столбцов).

Одномерные массивы

Каждому используемому в программе конкретному массиву должно быть дано свое имя. Это имя будем называть полной переменной, поскольку ее значение есть весь массив. Каждая компонента массива может быть явно обозначена путем указания имени массива, за которым следует селектор компоненты - взятый в квадратные скобки индекс, задающий правило вычисления номера нужной компоненты. Это отличие от привычной записи индекса в математике, когда он указывается справа в нижней позиции, объясняется необходимостью использования линейной записи программы, так что многоуровневая запись должна быть исключена. При ссылке на компоненты массива индекс записывается на одном уровне с именем и заключается в квадратные скобки. Таким образом, для ссылки на отдельные компоненты используется запись вида (имя массива) [<�индекс>] которую будем называть частичной переменной (поскольку ее значением является не весь массив, а отдельная его компонента, номер которой задается индексом) - применительно к массивам она называется переменной с индексом. В нашем примере массив получит имя v, а ссылки на отдельные его компоненты производятся с помощью частичных переменных v[ 1], v[2], ..., v[1ОО]. В общем случае в качестве индекса может, быть использовано выражение, значение которого и определяет номер компоненты массива. При этом важно, что в индексное выражение могут входить переменные, так что при изменении их значений меняется и значение индекса, которое определяет номер компоненты массива. Таким образом, одна и та же переменная с индексом в процессе выполнения программы может обозначать различные компоненты массива. Тип значения индексного выражения называют типом индекса. Множество значений типа индекса должно быть перенумерованным множеством, тем самым определяя количество компонент и их упорядоченность. При задании регулярного типа кроме типа индекса необходимо задать тип компонент. Задание такого регулярного типа, как одномерный массив, т.е. вектор, имеет вид:

А: аrrау [(тип индекса)] оf <����������������������������������������

�����������������������������������������������������

• ����ение, вывод элементов массива

• Сумма, произведение элементов

• Выбор по условию

• Максимальный (минимальный) элемент

• Вставка, удаление элементов

Задачи с использованием типовых алгоритмов обработки одномерных массивов

Задача. На плоскости изображено N прямоугольников. Каждый прямоугольник задан координатами левой нижней и правой верхней вершин. Определить, имеют ли прямоугольники общую площадь.

Алгоритм решения:

Если максимальная координата по оси Х левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин и максимальная координата по оси У левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин, то общая площадь есть.

Обработка строк

Объединение строк. Объединение двух строк в одну, присоединяя начало второй строки к концу первой. Объединение обозначается знаком «+».

Например:

Присваивание. Оператор присваивания для строковых данных имеет вид:

имя_ строковой_ переменной: = строковое выражение;

Например:

Длины строки. Выдает количество символов строки:

length (строковое_выражение)

Например:

Копирование. Позволяет скопировать одну область памяти в другую:

copy (строковое выражение, начальный номер символа, количество символов).

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

Например, результатом работы функции

Вставка в строку. В одну строку можно вставить другую строку, указав номер символа, начиная с которого осуществляется вставка:

insert (вставляемая строка, исходная строка, целочисленное выражение)

Удаление части строки. Часть строки можно удалить, строка при этом «сжимается»:

delete (строка, начальный номер, количество символов)

delete (x,3,1);{удаление третьей буквы - буквы «о»}, получилось слово фирма

Типовые алгоритмы обработки строковых переменных

• «Разобрать» число на цифры, поместив каждую цифру в ячейку массива.

• «Разобрать» строку, поместив каждый символ в ячейку массива.

• «Разобрать» предложение, поместив каждое слово в ячейку массива.

Типовой алгоритм

Программная реализация

«Разобрать» строки на буквы

Var a:array [1…10]of char;

Stroka: string;

I,n:integer;

Begin

Readln (stroka);

n:=length(stroka);

For i:=1 to n do a[i]:=copy(stroka,I,1);

…

End.

«Разобрать» число на цифры

Var a:array [1…10] of byte;

Stroka:string;

I,n,k:integer;

Begin

Readln (stroka);

n:=length(stroka);

For i:=1 to n do

Val(copy(stroka,I,1),a[i],k);

…

End.

«Разобрать» предложение на слова

Program pr;

Var a:array[1…10] of string

Stroka:string;

I,n,j,k:integer;

Begin

Readln (stroka);

n:=lengyh(stroka);

For i:=1 to n do

If copy(stroka,I,1)=' 'then k:=k+1;

K:=k+1;

J:=1;

For i:=1 to n do

If copy(stroka,I,1)=' 'then j:=j+1

Else a[j]:=a[j]+copy(stroka,I,1);

…

End.

Задача «Разбор предложения на слова».

Заменить Slovo1 на Slovo2 в предложении. Вывести новое предложение на экран.

Тест.

Дано:

Мама мыла раму

Мыла

Красила

Результат:

Мама красила раму

Сортировка методом «Пузырька»

Задача. Дан массив:

5

8

4

9

3

Необходимо сортировать его в порядке возрастания.

1-й шаг.

5

8

4

9

3

5

4

8

9

3

5

4

8

9

3

5

4

8

3

9

2-й шаг.

4

5

8

3

9

4

5

8

3

9

4

5

3

8

9

3-й шаг.

4

5

3

8

9

4

3

5

8

9

4-й шаг.

3

4

5

8

9

Итого:

3

4

5

8

9

Паскаль:

For j:=n downto 2 do

For i:=1 to j-1 do

If a[i]>a[i+1] then

Begin

X:=a[i]; a[i]:=a[i+1]; a[i+1]:=x;

End;

…

Задача. Ввести предложение. Выдать его на экран, изменив порядок следования букв в каждом слове.

Идея решения. Применив типовой алгоритм «РАЗБОРА» ПРЕДЛОЖЕНИЯ НА СЛОВА, помещаем каждое слово в элемент массива. Далее СОРТИРУЕМ массив слов, сравнивая количество букв в словах.

Тест.

Дано: Мама мыла раму

Результат: умар алым амаМ

Двумерные массивы

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

Для описания двумерных массивов используются те же способы, что и для одномерных массивов.

Таким образом, для создания двумерного целочисленного массива размерностью 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 {перебор столбцов (ячеек) в строке}

Т.е. значение индекса строки (i) увеличится только в том случае, если индекс столбца (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

Процесс перебора элементов двумерного массива:

Ход выполнения: 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;

Типовые алгоритмы обработки двумерных массивов и задачи, решаемые с их помощью

• Обработка всего массива.

• Обработка отдельно по строкам и столбцам.

• Обработка относительно диагоналей.

Типовые алгоритмы обработки двумерного массива отдельно по столбцам

Типовой

алгоритм

Программная реализация(Паскаль)

Сумма

…

For j:=1 to m do

S[j]:=0;

For j:=1 to m do

For i:=1 to n do

S[j]:=S[j]+x[i,j];

For j:=1 to m do

Write(S[j]);

…

Произведение

…

For j:=1 to m do

P[j]:=1;

For j:=1 to m do

For i:=1 to n do

P[j]:=P[j]*x[i,j];

For j:=1 to m do

Write(P[j]);

…

Максимальный

(минимальный) элемент

…

For j:=1 to m do

Begin

Max[j]:=x[i,1];

Min[j]:=x[i,1];

End;

For j:=1 to m do

For i:=1 to n do

Begin

If x[i,j]>max[j] then max[j]:=x[i,j]

If x[i,j]

End;

Вывод максимума/минимума по столбцам

For j:=1 to m do

Write(max[j]);

Writeln;

For j:=1 to m do

Write(min[j]);

Выбор по условию

For j:=1 to m do

Rez[j]:=0

For j:=1 to m do

For i:=1 to n do

If {усл.} then {Rez[i]:=…};

For j:=1 to m do

Write(Rez[j]);

…

Типовые алгоритмы обработки двумерного массива относительно диагоналей

Главная диагональ. В таблице приведены типовые алгоритмы обработка элементов двумерного массива, расположенных НА, ВЫШЕ и НИЖЕ главной диагонали.

Типовой алгоритм

Программная реализация (Паскаль)

Сумма элементов, расположенных НА главной диагонали

…

s:=0;

for i:=1 to n do

s:=s+x[i,i];

…

Сумма элементов, расположенных ВЫШЕ главной диагонали

…

s:=0;

for i:=1 to n do

for j:=1 to n do

if i

…

Сумма элементов, расположенных НИЖЕ главной диагонали

…

s:=0;

for i:=1 to n do

for j:=1 to n do

if i>j then s:=s+x[i,j];

…

Побочная диагональ. В таблице приведены типовые алгоритмы обработка элементов двумерного массива, расположенных НА, ВЫШЕ и НИЖЕ побочной диагонали.

Типовой алгоритм

Программная реализация (Паскаль)

Сумма элементов, расположенных НА побочной диагонали

…

s:=0;

for i:=1 to n do

s:=s+x[i, n-i+1];

…

Сумма элементов, расположенных ВЫШЕ побочной диагонали

…

s:=0;

for i:=1 to n do

for j:=1 to n do

if (i

s:=s+x[i,j];

…

Сумма элементов, расположенных НИЖЕ побочной диагонали

…

s:=0;

for i:=1 to n do

for j:=1 to n do

if (i>n-j+1) then

s:=s+x[i,j];

…

Обработка квадратной матрицы относительно диагоналей (рациональный обход).

Задача: заполнить элементы квадратного массива "1" так, как показано на рисунке:

Ниже и на главной диагонали

Выше и на главной диагонали

Выше и на побочной диагонали

Ниже и на побочной диагонали

100000000

110000000

111000000

111100000

111110000

111111000

111111100

111111110

111111111

111111111

011111111

001111111

000111111

000011111

000001111

000000111

000000011

000000001

111111111

111111110

111111100

111111000

111110000

111100000

111000000

110000000

100000000

000000001

000000011

000000111

000001111

000011111

000111111

001111111

011111111

111111111

Программная реализация на Паскале:

…

for i:=1 to n do

for j:=1 to i do

x[i,j]:=1;

…

Программная реализация на Паскале:

…

for i:=1 to n do

for j:=i to n do

x[i,j]:=1;

…

Программная реализация на Паскале:

…

for i:=1 to n do

for j:=1 to (n-i+1) do

x[i,j]:=1;

…

Программная реализация на Паскале:

…

for i:=1 to n do

for j:=(n-i+1) to n do

x[i,j]:=1;

…

Задача: Обработка квадратной матрицы. Дана матрица N x M, состоящая из натуральных чисел. Найти в строках самые правые наименьшие элементы и определить их местоположение.

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

Для решения задачи:

1. Формируем тело программы и описываем переменные;

2. Вводим размеры массива А и значения его элементов;

3. Просматриваем строки массива справа налево, ищем минимальное значение и запоминаем значение индексов;

4. Для каждой строки выводим значение и местоположение самого правого минимального элемента.

Переменные:

А-двумерный массив;

N,M-количество строк и столбцов массива;

I,J-переменные цикла;

JM-столбец минимального элемента;

MIN-текущий минимум.

Заключение

В курсовой работе рассмотрены методы обработки одномерных и двумерных массивов натуральных и действительных чисел. Этот вопрос очень актуален в наше время, потому что в настоящее время размер обрабатываемых данных постоянно увеличивается.

Литература

5. Гусева А. И. Учимся программировать: PASCAL 7.0. Задачи и методы их решения.- М: «Диалог-МИФИ», 1997.- 256 с.

6. Кузнецов А.А., Апатова Н.В. Основы информатики. 8-9кл.: Учеб. Для общеобразоват. Учеб. Заведений. - 2-е изд., стереотип. - М.: Дрофа 2000. - 176 с.: ил.

7. Ларина Э. С. Олимпиадные задачи по информатике - Волгоград:Учитель, 2007. -111 с.