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

Содержание

Типовые алгоритмы и задачи, решаемые с их помощью
Типовые алгоритмы обработки одномерных массивов
Задачи использованием типовых алгоритмов обработки одномерных массивов
39. Массив как способ организации данных. Реализация массивов в различных языках программирования. Одномерные и многомерные массивы. Типовые алгоритмы обработки массивов.
40. Подпрограммы (методы) в языках программирования. Формальные и фактические параметры. Глобальные и локальные переменные. Рекурсивное выполнение подпрограммы.
Тема 4.7. Программирование алгоритмов формирования и обработки одномерных массивов
4.7.2. Средства описания и работы с одномерными массивами данных

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

Аннотация: Используя типовые алгоритмы можно решить любую задачу. В лекции очерчен круг НЕОБХОДИМЫХ ТИПОВЫХ АЛГОРИТМОВ (для обработки одномерных массивов и обработки строк), рассмотрены некоторые олимпиадные задачи, которые решаются с использованием этих алгоритмов. Цель лекции: научиться применять изученные типовые алгоритмы при решении классических задач.

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

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

Заполнение, вывод элементов массива
Сумма, произведение элементов
Выбор по условию
Максимальный (минимальный) элемент
Вставка, удаление элементов
Инвертирование (изменения порядка следования элементов заданного массива на обратный)

Программные реализации типовых алгоритмов обработки одномерных массивов приведены в таблице 2.1:

input n dim a(n) for i=1 to n input a(i) next i

const n=10; Var a: array [1..n] of integer; begin for i:=1 to n do readln (a[i]); …

…for i=1 to n print a(i) ; " " ; next i

… p=1 for i=1 to n s=s + a(i) p=p * a(i) next i

… s:=0; p:=1; for i:=1 to n do begin s:=s+a[i]); p:=p*a[i]); end; …

… p = 1 for i = 1 to n if then k=k+1:s=s+a(i):p=p*a(i) next i

… k:=0; s:=0; p:=1; for i:=1 to n do if then begin k:=k+1; s:=s+a[i]; p:=p*a[i]; end; …

… max = a(1): min = a(1) for i = 2 to n if a(i) > max then max = a(i) if a(i) < min then min = a(i) next i

… max:=a[1]; min:=a[1]; for i:=1 to n do begin if a[i] > max then max:=a[i]; if a[i] < min then min:=a[i]; end;

dim a(n + 1) … for i = n to k step -1 a (i + 1) = a(i) next a(k) = x

Var a: array [1..n+1] of… … for i:=n downto k do a[i+1]:=a[i]; a[k]:=x; …

. . . for i = k to n - 1 a(i) = a(i + 1) next

. . . for i = 1 to n/2 swap a(i), a(n-i+1) next

… for i:=1 to (n div 2) do begin х:=a[i]; a[i]:= a[n-i+1]; a[n-i+1] :=х; end …

Ключевые моменты в типовых алгоритмах:

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

if a[i]>max then begin max:=a[i]; imax:=i; end;

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

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

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

В задаче необходимо использовать типовой алгоритм нахождения МАКСИМАЛЬНОГО (МИНИМАЛЬНОГО) ЭЛЕМЕНТА МАССИВА.

Для вычисления общей площади необходимо найти произведение разности:

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

input "введите количество прямоугольников"; n dim x1(n), x2(n),y1(n), y2(n) for i=1 to n input x1(i), x2(i), y1(i), y2(i) next xmax=x1(1) xmin=x2(1) ymax=y1(1) ymin=y2(2) for i=1 to n if x1(i) > xmax then xmax=x1(i) if x2(i) < xmin then xmin=x2(i) if y1(i) >ymax then ymax=y1(i) if y2(i) < ymin then ymin=y2(i) next if xmax
var x1, x2, y1, y2: array [1..10] of integer; n, i, xmax, xmin, ymax, ymin: integer; begin writeln ('введите количество прямоугольников'); readln (n); for i:=1 to n do readln (x1[i], y1[i], x2[i], y2[i]); xmax:=x1[1]; xmin:=x2[1]; ymax:=y1[1]; ymin:=y2[2]; for i:=1 to n do begin if x1[i] > xmax then xmax:=x1[i]; if x2[i] < xmin then xmin:=x2[i]; if y1[i] >ymax then ymax:=y1[i]; if y2[i] < ymin then ymin:=y2[i]; end; if (xmax
Задача: Латинским квадратом называется массив, в строках и столбцах которого нет одинаковых элементов. Вывести на экран латинский квадрат размером NxN .


Идея решения: Заполнить 1 строку квадратного массива ( NxN ) числами от 1 до N . Вторая строка массива получается путем циклического сдвига элементов первой строки и т. д. (табл. 2.2). Циклический сдвиг можно реализовать, используя типовой алгоритм ВСТАВКИ-УДАЛЕНИЯ (в зависимости от направления циклического сдвига).
Таблица 2.2. Заполнение латинского квадрата путем циклического сдвига элементов 

1
2
3
4
5


5
1
2
3
4


4
5
1
2
3


3
4
5
1
2


2
3
4
5
1


input "размерность http://www.intuit.ru/2010/edi" >

Решение на Паскале:

var a: array [1..10,1..10] of integer; n,i,j,x: integer; begin writeln ('размерность='); readln (n); for j:=1 to n do a[1,j]:=j; for i:=2 to n do begin for j:=1 to n do a[i,j]:=a[i-1,j]; x:=a[i,n]; for j:=n downto 2 do a[i,j]:=a[i,j-1]; a[i,1]:=x; end; for i:=1 to n do begin for j:=1 to n do write(a[i,j]); writeln; end; end.

Источник

39. Массив как способ организации данных. Реализация массивов в различных языках программирования. Одномерные и многомерные массивы. Типовые алгоритмы обработки массивов.

Массив– это упорядоченная (пронумерованная) последовательность однотипных элементов. Массив имеет общее для всех элементов имя. Номер элемента в массиве называют егоиндексом. В качестве индекса можно использовать любые значения порядкового типа:например, целые числа, символы (пример: от а до е).

Доступ к элементам массива осуществляется по индексу, который указывается после имени массива в квадратных скобках. Например: А[2]=12, C[‘d’]=234.

Массивы реализованы практически во всех структурных и объектно-ориентированных языках программирования.

Рассмотрим структуру массива на примере языка TurboPascal:

40. Подпрограммы (методы) в языках программирования. Формальные и фактические параметры. Глобальные и локальные переменные. Рекурсивное выполнение подпрограммы.

Подпрограмма– это самостоятельный фрагмент программы, реализующий определённый алгоритм и допускающий многократное обращение к нему из различных частей программы. Язык Турбо Паскаль содержит два типа подпрограмм: 1. Процедуры 2. Функции. Процедуры в Паскале. Структура процедуры аналогична структуре программы и состоит из заголовка и блока (тела программы). Procedure () begin end; Структура процедуры почти полностью совпадает со структурой программы. Но имеются исключения: I. Заголовокначинается с зарезервированного словаProcedure, кроме того содержит список параметров.Параметры– это средства связи процедуры с программой и другими процедурами, механизм обмена данными. Параметры процедуры бывают двух видов: - параметры-значения, или входные параметры – это исходные, (входные) данные, передаваемые в процедуру. Их значения после окончания работы процедуры остаются неизменными. Описание параметров-значений:: . - параметры-переменные, или выходные параметры – это результаты работы процедуры, передаваемые обратно в программу или другую процедуру. Их значения поле окончания процедуры изменяются. Описание выходных параметров:Var : . Например, процедура может иметь такой заголовок: Procedure Calculate (x,y:integer; var z: integer, var f: real); Имя этой процедуры Calculate. Она имеет 4 параметра: два входных (или параметра значения) – это параметрыxиyцелого типа; два выходных (или параметра-переменных) – я целого типа иfвещественного типа, т.к. типы у них различны, перед описанием каждого указано зарезервированное словоVar. Блок описаний может содержать те же разделы, что и блок описаний программы (Const,Type,Var,Procedure,Function),за исключением описания подключения модулей библиотек Uses. Данные, описанные в блоке описаний процедуры, называются локальнымии могут быть использованы только в процедуре. Данные, описанные в блоке описаний программы, называются глобальными и могут быть использованы как в самой программе, так и во всех её процедурах. Тело процедуры также представляет собой составной оператор, но заканчиваетсяEnd; ВЫЗОВ ПРОЦЕДУРЫ может осуществляться из основной программы или процедуры, описанной после вызываемой. При вызове указываетсяимя процедуры и список фактических параметров, т.е. тех, которые будут подставлены на местоформальных (используемых в списке параметров процедуры). Количество, порядок и типы фактических параметров должны совпадать с количеством, порядком и типами формальных параметров. Например, процедуруCalculate, заголовок которой был описан выше, можно вызвать следующим образом: Calculate(a,b,c,d);- при условии, чтоa,b, с имеют типInteger,d–Real. Calculate(23,p+14,q,w);- еслиpиqимеют типInteger,aw–Real. Практически всё сказанное о процедурах верно и для функций. Отличие функции от процедуры состоит в том, что функция не имеет выходных параметров, она возвращает единственное значение – это значение функции. Входные параметры называются ещёаргументами функции. Описание функции: Function (): ; Begin End; В теле функции обязательно должна быть команда присваивания вида: :=; Которая и позволит функции возвратить вычисленное значение. Например, опишем функцию вычисления среднего арифметического двух целых чисел: Function middle(a,b:integer):real; Begin Middle:=(a+b)/2 End; Процедуры и функции, производящие вызов «самих себя» называютрекурсивными. Рекурсией называется ситуация, когда какая-то подпрограмма прямо или через другие подпрограммы вызывает себя в качестве подпрограммы. Реализуемый при этом алгоритм называется рекурсивным. 41 Объектно-ориентированное программирование: класс, объект, поле, метод. Принципы объектно-ориентированного подхода. Их реализация в современных языках программирования. 42 Языки разметки HTML и XML. Каскадные таблицы стилей.

Источник

Тема 4.7. Программирование алгоритмов формирования и обработки одномерных массивов

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

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

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

Массив – это совокупность однотипных переменных (элементов массива). Имя у всех переменных одно и то же, а для доступа к конкретному элементу массива используется дополнительный идентификатор – его порядковый номер.

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

Наряду со стандартными структурами данных, могут использоваться структуры данных, определяемые пользователем. Эти структуры данных определяются средствами объектно-ориентированного программирования с помощью классов. Понятия классов и работа с ними будут рассмотрены далее в Разделе 5.

4.7.2. Средства описания и работы с одномерными массивами данных

Массив – последовательность переменных одинакового типа, объединенных общим именем. Например: одномерный массив а(9) состоит из 10 элементов с общим именем а: a(0),a(1),a(2),a(3). a(9), упорядоченных по индексу i, который имеет значения от 0 до 9:

Источник