Множества, операции над множествами

Лабораторная работа № 3

Множества, операции над множествами

Изучение методов сортировки данных

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

Теоретическая часть

Понятие массива

Чтобы определить понятие «массив», сначала необходимо определить понятие «простая переменная».

Простая переменная - это одно значение, имеющее имя и занимающее одну ячейку

памяти. Размер этой ячейки зависит от типа переменной.

Например:

Var

X: Real; {простая переменная X, занимает 6 байт памяти}

N: Integer; {простая переменная N, занимает 2 байта памяти}

Обращение к простой переменной производится через ее имя.

Например:

X: =10.4; {X присвоили значение 10.4}

N: =round(X)+5; {N присвоили значение округленного до целого

X (а это 10) + 5= 10+5=15}

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

Номер элемента массива называется индексом элемента массива.

Использование элемента массива не отличается от использования простой переменной, имеющей тот же тип, что и элемент массива.

В Turbo Pascal’е массив объявляется при помощи ключевого слова array, после которого в квадратных скобках указываются границы индексов – верхняя, а после двух точек нижняя.

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

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

Var

A: Array [1..10] of integer; {массив A, состоящий из 10 элементов

целого типа с индексами от 1 до 10}

B: Array [5..8] of real; {массив B, состоящий из 4 элементов

вещественного типа с индексами от 5 до 8}

Пример работы с массивами:

Begin

A[1]: =3; {в элемент массива A с индексом 1 записали число 3}

A[4]: =A[1]+1; {в элемент массива A с индексом 4 записали число 3+1=4}

B[5]: =0.111; {в элемент массива B с индексом 5 записали число 0.111}

B[A[1]+A[4]]: =B[5]*2; {в элемент массива B с индексом=A[1]+A[4]=3+4= 7 записали число 0.222}

End.

Индексы массива

В качестве индекса массива можно использовать любой порядковый тип, кроме типа Longint. Напомним, что порядковый тип – это тип, все значения которого можно перечислить. К таким типам относятся все целые типы(integer, shortint, longint, byte, word), все логические (boolean, wordbool, longbool, bytebool), символьный тип (char), перечисляемые типы и типы-диапазоны.

Примеры использования в качестве индексов порядковых типов:

Var {примеры объявления массивов}

A: Array [Byte] of integer; {массив A, состоящий из 256 элементов, нижняя граница индекса 0, верхняя 255}

B: Array [Char] of real; {массив B, состоящий из 256 элементов, нижняя граница индекса #0(символ с кодом 0),

верхняя граница индекса #255(символ с кодом 255)}

i: Byte; {переменная, используемая как индекс массива A}

c: Char; {переменная, используемая как индекс массива B}

Begin {примеры обращения к элементам массива}

A[45]: =0; {В элемент массива A, имеющий индекс 45, записали 0 }

B[‘t’]: =2.4; {В элемент массива B, имеющий индекс ‘t’, записали 2.4}

i: =200; {i присвоили значение 200 }

c: =’#’; {c присволили значение ‘#’ }

A[i]: =23400; {В элемент массива A, имеющий индекс i=200,

записали 23400}

B[c]: =123.456; {В элемент массива B, имеющий индекс c=’#’,

записали 123.456}

End.

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

Например:

Var {примеры объявления массивов}

C: Array [-10..5] of integer; {массив C, состоящий из 16 элементов,

нижняя граница индекса -10, верхняя 5}

D: Array [‘A’..’Z’] of char; {массив D, состоящий из 26 элементов,

нижняя граница индекса ’A’,

верхняя граница индекса ‘Z’}

j: -10..5; {переменная, используемая как индекс массива C}

c1: ‘A’..’Z’; {переменная, используемая как индекс массива D}

k: integer; {эту переменную можно использовать в качестве индекса

массива C, т.к. –10..5 – это диапазон значений целого типа}

c2: char; {эту переменную можно использовать в качестве индекса

массива D, т.к.’A’..’Z’ – это диапазон значений символьного типа}

begin {примеры обращения к элементам массивов}

C[-4]: =3;

D[‘F’]: =’%’;

j: =4; C[j]: =-10;

c1: =’R’; D[c1]: =’q’;

k: =-3; C[k]: =80;

c2: =’G’; D[c2]: =’Й’;

end.

Чаще же всего используют диапазон значений целого типа, причем нижний индекс обычно берут равным 1.

Например:

Var

E: Array [1..10] of integer; {массив E, состоящий из 10 элементов,

нижняя граница индекса 1, верхняя 10}

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

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

SizeOfArray = NumElement * SizeOfElement

где SizeOfArray – размер массива

NumElement – количество элементов в массиве

SizeOfElement – размер одного элемента

Адрес первого (по порядку) элемента массива является адресом массива (будем обозначать его AdrArray). Адрес i-го элемента массива (его будем обозначать AdrI) можно вычислить по формуле:

AdrI = AdrArray + (i – нижняя_граница_индекса) * SizeOfElement

Для примера рассмотрим массив B, определенный выше. Нижняя граница индекса этого массива = 5. Первый (по порядку) элемент массива - B[5]. Пусть его адрес = 100. Размер каждого элемента 6 байт, поскольку тип элементов - Real.

Вычислим адреса остальных элементов массива

Adr6 = 100 + (6-5)*6 = 100 + 1*6 = 106

Adr7 = 100 + (7-5)*6 = 100 + 2*6 = 112

Adr8 = 100 + (8-5)*6 = 100 + 3*6 = 118

Графически покажем взаимное расположение элементов этого массива:

Адрес

элемента

Элемент

100 B[5]

106 B[6]

112 B[7]

118 B[8]

Замечание: Один массив может занимать в памяти не более 65520 байт. Нельзя, например, определить такой массив C:

Var C: array[1..50000] of integer;

- каждый элемент этого массива занимает в памяти 2 байта, элементов 50000, значит весь массив занимает 100000 байт > 65520 байт.

Пользовательский тип – массив

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

Пример:

Type

Arr = array[1..20] of integer; {определили тип массива целых чисел

содержащего 20 элементов}

Var

A, B: Arr; {A и B – массивы целых чисел, содержащие по 20

элементов}

Дальше с массивами A и B можно работать как с обычными массивами:

A[3]: =2; B[4]: =A[3]; и т.д.

Кроме типа массива в программе можно определить и специальный тип для индексов. Этот тип должен быть интервальным.

Пример:

Type

IndexEl = 1.. 20; {тип индекса элемента}

Arr = array[IndexEl] of integer; {тип массива целых чисел

содержащего 20 элементов}

Var

A, B: Arr; {A и B – массивы целых чисел, содержащие по 20

элементов}

i, j: IndexEl; {переменные, используемые для указания

индекса элемента }

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

Все массивы, которые приведены выше, называются одномерными – у элементов одномерных массивов в квадратных скобках указывается только один индекс (у таких массивов только одно измерение).

Кроме одномерных массивов могут быть и двумерные, и трехмерные, и прочие n-мерные массивы. «Мерность» массивов определяется количеством индексов, указываемых в квадратных скобках, для того чтобы определить элемент массива.

Пример:

A[7] – A – одномерный массив

S[2, -3] – S – двумерный массив

W[1, 0, 0] – W – трехмерный массив

Z[-1, 3, 4, 3, 0] – Z – пятимерный массив

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

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

Одномерный массив можно представить в виде строки. Например, массив целых чисел можно представить строкой целых чисел, например такой: 3 2 4 1 3. Двумерный массив можно представить в виде прямоугольной таблицы, например такой:

2 3 4 5

0 4 8 3

7 1 5 3

Чтобы определить такой массив, в программе надо написать:

Var

A: array[1..3, 1..4] of integer;

Здесь в массиве A первый интервал индексов - 1..3 – обозначает индекс номера строки, а второй интервал индексов – 1..4 – обозначает индекс номера столбца. Для обращения к элементу двумерного массива необходимо в квадратных скобках сначала указать номер строки, а затем номер столбца.

Например:

Writeln(A[2, 3]); {будет выведено число 8}

Writeln(A[3, 1]); {будет выведено число 7}

Writeln(A[1, 1]); {будет выведено число 2}

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

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

Задача 1: Ввод массива с клавиатуры

Алгоритм состоит из двух пунктов:

1. Ввод количества элементов.

2. Ввод элементов массива поодиночке в цикле.

Фрагмент программы:

… {

ввод количества элементов}

repeat

write('Введите n: ');

readln(n);

until (n> =1) and (n< =maxN);

{2 - ввод элементов массива поодиночке}

for i: =1 to n do

begin

write('a[', i, ']');

readln(a[i]);

end;

…

Задача 2: Заполнение массива случайными числами.

Алгоритм состоит из трех пунктов:

1. Перезапустить генератор случайных чисел.

2. Ввести количество элементов n (или сгенерировать

случайное значение n).

3. Сгенерировать значения для всех элементов.

Фрагмент программы:

… {

перезапускаем генератор случайных чисел}

randomize;

{2 - генерируем случайное значение n}

n: =random(maxN);

{3 - генерируем n элементов массива}

for i: =1 to n do

a[i]: =random(100); {каждый элемент примет значение

из интервала 0..99}

…

Краткая информация об используемых стандартных процедурах и функциях:

Randomize - инициализирует генератор случайных чисел случайным значением (случайное значение зависит от момента перезапуска, т.е. зависит от времени).

Random (Num) - возвращает случайное целое число, находящееся в интервале 0.. (Num-1) (Например, если Num=100 (как в нашем примере), то Random возвращает числа в интервале от 0 до 99). Если Num< =0, то Random всегда будет возвращать 0. Чтобы получить значения в интервале, отличном от [0..Num-1], необходимо к значению, возвращаемому Random, прибавить

смещение начала интервала.

Пример 1: необходим интервал [-50.. 50].

Длина интервала 101, смещение начала интервала –50.

random(101)-50

Пример 2: необходим интервал [20.. 30].

Длина интервала - 11, смещение начала интервала 20.

random(11)+20

Пример 3: необходим интервал [-1000.. -500]

Длина интервала 501, смещение начала интервала -1000

random(501)-1000

Задача 3: Вывод массива.

Алгоритм состоит из двух пунктов:

1. Вывод имени массива.

2. Вывод массива по элементам.

Фрагмент программы:

… {

вывод имени массива}

writeln ('Массив А[', n, ']');

{2 - вывод элементов массива}

for i: =1 to n do

writeln('A[', i, ']=', a[i]);

…

Массива

Задача 4: Подсчитать сумму элементов массива.

Алгоритм содержит два пункта:

1. Сумма S=0.

2. Проход по всем элементам массива и прибавление их значений к

сумме S.

Приведем полный текст программы – решение этой задачи:

{Пример обработки одномерного массива}

{ Задание: Ввести массив. Подсчитать сумму элементов массива.}

Program SumExample;

Const {определение констант}

maxN = 20; {максимально возможное количество элементов в массиве}

Type {определение типов}

IndexEl = 1.. maxN; {индексы массива лежат в интервале от 1 до maxN}

arrInt = array[interval] of integer; {массив целых чисел содержащий до maxN элементов}

Var

a: arrInt; {массив}

n: interval; {размерность массива}

i: IndexEl; {переменная для сканирования массива}

S: integer; {сумма элементов массива}

Begin

{ ввод массива с клавиатуры }

write(‘Введите n=’);

read(n); {ввод количества элементов}

for i: =1 to n do

read(A[i]); {ввод самих элементов}

{Подсчет суммы элементов массива}

{1} s: =0;

{2} for i: =1 to n do

s: =s+A[i];

{Вывод полученного значения суммы}

writeln(‘сумма элементов массива S=’, S);

end. {конец программы}

Задача 5: Вычислить среднее арифметическое элементов массива.

Алгоритм содержит три пункта. Первые два совпадают с предыдущей задачей:

1. Сумма s=0.

2. Проход по всем элементам массива и прибавление их значений к сумме s.

3. Сумму делим на количество элементов массива sa=s/n.

Фрагмент программы:

Var {дополнительные переменные}

s: integer; {сумма элементов массива}

sa: real; {среднее арифметическое элементов массива}

…

Begin

...

{1} s: =0;

{2} for i: =1 to n do

s: =s+A[i];

{3} s: =s/n;

…

Варианты заданий

Задачи совсем простые

Вариант A1:

В массиве все четные элементы обнулить.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив 1 3 0 5 0

Вариант A2:

В массиве все нечетные элементы заменить на 1.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив 1 1 4 1 6

Вариант A3:

В массиве все элементы, стоящие после нечетных,

заменить на 0.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив 1 0 4 5 0

Вариант A4:

В массиве все элементы, стоящие перед четными,

заменить на 9.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив 1 9 4 9 6

Вариант A5:

В массиве все элементы стоящие между четными заменить

на 1.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив 1 2 4 1 6

Вариант A6:

В массиве все элементы, стоящие после минимального,

заменить на 0.

Пример: из массива A[5]: 3 2 1 5 6 должен получиться

массив 3 2 1 0 0

Вариант A7:

В массиве все элементы, стоящие перед максимальным,

заменить на 0.

Пример: из массива A[5]: 3 2 1 5 4 должен получиться

массив 0 0 0 5 4

Вариант A8:

В массиве все элементы, стоящие после максимального,

заменить на 0.

Пример: из массива A[5]: 3 2 1 5 4 должен получиться

массив 3 2 1 5 0

Вариант A9:

В массиве все нечетные элементы, стоящие после

максимального, заменить на 0.

Пример: из массива A[5]: 3 7 1 5 4 должен получиться

массив 3 7 0 0 4

Вариант A10:

В массиве все четные элементы, стоящие левее

минимального, заменить на 0.

Пример: из массива A[5]: 3 2 1 0 4 должен получиться

массив 3 0 1 0 4

Задачи простые

Вариант B1

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

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив A[4]: 1 3 5 6

Вариант B2

Из массива удалить последний из четных элементов.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив A[4]: 1 3 4 5

Вариант B3

Из массива удалить последний из нечетных элементов.

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив A[4]: 1 3 4 6

Вариант B4

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

Пример: из массива A[5]: 1 3 4 5 6 должен получиться

массив A[4]: 3 4 5 6

Вариант B5

После максимального из четных элементов вставить 0.

Пример: из массива A[5]: 1 9 8 3 5 должен получиться

массив A[6]: 1 9 8 0 3 5

Вариант B6

После первого четного элемента вставить 0.

Пример: из массива A[5]: 1 6 8 3 4 должен получиться

массив A[6]: 1 6 0 8 3 4

Вариант B7

После последнего нечетного элемента вставить 0.

Пример: из массива A[5]: 1 3 8 3 5 должен получиться

массив A[6]: 1 3 8 3 5 0

Вариант B8

Удалить максимальный из четных элементов.

Пример: из массива A[5]: 2 3 4 7 5 должен получиться

массив A[4]: 2 3 7 5

Вариант B9

Удалить максимальный из кратных трем элементов.

Пример: из массива A[5]: 2 3 4 7 5 должен получиться

массив A[4]: 2 4 7 5

Вариант B10

После последнего кратного четырем элемента вставить

Пример: из массива A[5]: 1 3 8 3 4 должен получиться

массив A[6]: 1 3 8 3 4 0

Задачи средние

Вариант C1

Из массива удалить четные элементы, стоящие после

максимального.

Пример: из массива A[5]: 2 7 4 6 5 должен получиться

массив A[3]: 2 7 5

Вариант C2

Из массива удалить четные элементы, имеющие значение

больше среднего арифметического всех элементов

массива.

Пример: из массива A[5]: 8 7 2 6 5 должен получиться

массив A[3]: 7 2 5 (среднее арифметическое всех

элементов =(8+7+2+6+5)/5=5.6)

Вариант C3

Из массива удалить элементы, имеющие значение меньше

среднего арифметического четных элементов массива.

Пример: из массива A[5]: 8 7 2 6 5 должен получиться

массив A[3]: 8 7 6 (среднее арифметическое четных

элементов =(8+2+6)/3=5.33)

Вариант C4

Из массива удалить элементы, стоящие после

максимального и имеющие значение меньше среднего

арифметического всех элементов массива.

Пример: из массива A[5]: 8 6 9 4 5 должен получиться

массив A[3]: 8 6 9 (среднее арифметическое четных

элементов =(8+6+9+4+5)/5=6.4)

Вариант C5

Из массива удалить четные элементы, стоящие между

максимальным и минимальным элементами.

Пример: из массива A[7]: 1 8 8 4 7 0 5 должен

получиться массив A[5]: 1 8 7 0 5

Вариант C6

Из массива удалить элементы, кратные трем, стоящие

между максимальным и минимальным элементами.

Пример: из массива A[7]: 1 9 3 4 9 0 0 должен

получиться массив A[5]: 1 9 4 0 0

Вариант C7

Из массива удалить элементы, имеющие четный индекс и

стоящие между максимальным и минимальным элементами.

Пример: из массива A[7]: 9 3 4 9 1 0 0 должен

получиться массив A[5]: 9 4 1 0 0

Вариант C8

Из массива удалить элементы, встречающиеся в массиве

более одного раза.

Пример: из массива A[7]: 9 3 4 9 1 0 0 должен

получиться массив A[3]: 3 4 1

Вариант C9

Из массива удалить элементы, встречающиеся в массиве

только один раз.

Пример: из массива A[7]: 9 1 4 9 1 9 0 должен

получиться массив A[5]: 9 1 9 1 9

Вариант C10

Из массива удалить нечетные элементы, встречающиеся в

массиве только один раз.

Пример: из массива A[7]: 4 1 4 3 1 9 0 должен

получиться массив A[5]: 4 1 4 1 0

Задачи посложнее

Вариант D1

Из массива удалить самую длинную цепочку четных

элементов.

Пример: из массива A[8]: 4 1 4 2 1 2 4 6 должен

получиться массив A[5]: 4 1 4 2 1

(самая длинная цепочка четных чисел включает элементы

с 6 по 8: 2 4 6)

Вариант D2

Из массива удалить цепочки из четных элементов,

состоящие менее чем из трех элементов.

Пример: из массива A[8]: 4 3 4 2 1 2 4 6 должен

получиться массив A[5]: 3 1 2 4 6

Вариант D3

Из массива удалить цепочки из нечетных элементов,

состоящие менее чем из трех элементов.

Пример: из массива A[8]: 3 3 4 5 2 3 7 9 должен

получиться массив A[5]: 4 2 3 7 9

Вариант D4

Из массива A удалить те элементы, которые встречаются

и в массиве A и в массиве B по крайней мере по 2

раза.

Пример: массив A[8]: 3 3 4 5 2 3 5 9

массив B[7]: 1 2 3 4 5 2 5

По 2 раза в обоих массивах встречается только

элемент, равный 5.

Массив A после удаления примет вид: A[6]: 3 3 4 2 3 9

Вариант D5

Из массива из каждой цепочки четных элементов удалить

самый маленький элемент.

Пример: из массива A[9]: 3 6 4 5 2 3 4 6 4 должен

получиться массив A[6]: 3 6 5 3 6 4

Вариант D6

Из массива A удалить те цепочки четных элементов, в

которых есть хотя бы один элемент из массива B.

Пример: массив A[9]: 3 2 4 5 2 3 2 6 5

массив B[6]: 1 3 4 7 8 9

Массив A после удаления примет вид:

A[7]: 3 5 2 3 2 6 5

Вариант D7

Из массива A удалить те цепочки нечетных элементов,

в которых нет ни одного элемента из массива B.

Пример: массив A[10]: 3 2 7 5 2 1 2 6 3 9

массив B[5]: 1 2 5 4 8

Массив A после удаления примет вид:

A[7]: 2 7 5 2 1 2 6

Вариант D8

Из массива A удалить те цепочки нечетных элементов,

в которых нет ни одного элемента из массива B.

Пример: массив A[10]: 3 2 7 5 2 1 2 6 3 9

массив B[5]: 1 2 5 4 8

Массив A после удаления примет вид:

A[7]: 2 7 5 2 1 2 6

Вариант D9

Между массивами A и B обменять их самые длинные

цепочки из одинаковых элементов.

Пример: массив A[10]: 3 2 2 5 2 1 1 1 3 9

массив B[8]: 1 2 5 5 4 8 3 3

В массиве A самая длинная цепочка:

1 1 1 (элементы с 7 по 9)

В массиве B самая длинная цепочка:

5 5 (элементы с 3 по 4)

Массив A после перестановки в него цепочки из массива

B: A[9]: 3 2 2 5 2 5 5 3 9

Массив B после перестановки в него цепочки из массива

A: B[9]: 1 2 1 1 1 4 8 3 3

Вариант D10

Между массивами A и B обменять их самые длинные

цепочки из четных элементов.

Пример: массив A[10]: 3 2 4 6 2 1 1 1 8 9

массив B[7]: 1 0 5 5 4 3 3

В массиве A самая длинная цепочка:

2 4 6 2 (элементы со 2 по 5)

В массиве B самая длинная цепочка:

0 (элемент 2)

Массив A после перестановки в него цепочки из массива

B: A[7]: 3 0 1 1 1 8 9

Массив B после перестановки в него цепочки из массива

A: B[10]: 1 2 4 6 2 5 5 4 3 3

Лабораторная работа № 3

Множества, операции над множествами

12	Поделиться: