программирование_занятие_7

//Решение задач на составление и обработку матриц.

изучается:

классификация типов данных

структурированные типы данных

массив

размерность массива

Понятие записи

понятие множества

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

«Структурированные типы данных»

Структурированные типы данных

Ранее были рассмотрены базовые (простые) типы данных (базовые способы хранения информации). Для работы с данными этих типов не требуется никаких уточнений, достаточно только указать тип.

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

Кроме базовых, различают:

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

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

Кодирование требует уточнений.

Набор внутритиповых операций связан с обращением к данным.

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

типы данных

/ \

статические динамические

/ \ \

простые сложные ├─стек

/ \ \────┐ │

стандартные нестандартные ├─массив ├─очередь

(базовые) (переменные) │ │

┌─────┘ │ ├─запись ├─список

├─целое число ├─перечисляемый │ │

│ │ ├─множество └─каталог

├─действительный └─ограниченный │

│ (вещественный) (интервальный) ├─файл

│ │

├─логический ├─граф

│ │

└─символьный (строковый) └─дерево

Чаще всего, из структурированных типов данных встречается массив.

Массив это упорядоченный набор данных одного типа.

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

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

Определяя массив в языке BASIC, пишем служебное слово dim, после которого указываем имя массива. Тип элементов указывается значком %, !, #, $. Размерность определяет количество чисел в скобках. Сами числа – это наибольшее значение индекса. Начальное значение индекса – 0. Наибольшая размерность массивов – 2. По умолчанию, элементы массива – действительные числа.

Следует отметить, что если массив одномерный и в нем не больше 10 элементов, то его объявление не обязательно. То есть использование команды DIM не требуется.

BASIC dim <имя><тип элементов>(<дополнительная информация>)

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

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

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

PASCAL <имя>:array[<дополнительная информация>] of <тип элементов>

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

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

В языке Pascal можно выполнять оператор присваивания с массивами и задать константу-массив.

Программы с использованием массивов достаточно велики и целиком в заданиях ЕГ предлагаются редко. Работу с массивами можно разбить на три шага: получение исходного массива, его преобразование и вывод результата. Рассмотрим задание из ЕГ, связанное с заполнением массива.

Значения двумерного массива задаются с помощью вложенного оператора цикла в представленном фрагменте программы

Бейсик	Паскаль	Алгоритмический
FOR n=1 TO 5 FOR k=1 TO 5 B(n, k)=n+k NEXT k NEXT n	for n:=1 to 5 do for k:=1 to 5 do B[n,k]:=n+k;	нц для n от 1 до 5 нц для k от 1 до 5 B[n, k]=n+k кц кц

Чему будет равно значение B(2,4)?

Универсальный прием решения подобных задач – поставить себя на место компьютера, и просто выполнить команды. Но для этой задачи есть более простое решение:

Отметим, что для всех значений счетчиков n и k в рассматриваемом диапазоне, значение элемента массива совпадает с суммой индексов. То есть B[2,4]=2+4=6.

Универсальное решение заключается в том, что переменным n и k придадим значение 1. В двумерную таблицу на место (1,1) записываем 1+1=2. Тело внутреннего цикла закончилось, значение k увеличиваем на 1, и в таблицу на место (1,3) заносим число 1+2=3.

n=1 k=1..5

n\k	1	2	3	4	5
1	2	3	4	5	6

По окончании тела внешнего цикла, увеличиваем на 1 значение переменной n, переменная k заново начинается с 1.

После заполнения всей таблицы обнаруживаем число 6 в клеточке (2,4).

n=1..5 k=1..5

n\k	1	2	3	4	5
1	2	3	4	5	6
2	3	4	5	6	7
3	4	5	6	7	8
4	5	6	7	8	9
5	6	7	8	9	10

Теперь рассмотрим пример на обработку массива. Исходный массив уже задан: все его элементы равны нулю.

Обработка элемента массива заключается в увеличении его значения на 1.

Все элементы двумерного массива A размером 10х10 элементов первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы (ниже представлена одна и та же программа, записанная на разных языках программирования).

Бейсик	Паскаль	Алгоритмический
FOR n=1 TO 4 FOR k=n TO 4 A(n,k)=A(n,k)+1 A(k,n)=A(k,n)+1 NEXT k NEXT n	for n:=1 to 4 do for k:=n to 4 do begin A[n, k]:=A[n, k]+1; A[k, n]:=A[k, n]+1; end	нц для n от 1 до 4 нц для k от n до 4 A[n, k]:=A[n, k]+1 A[k, n]:=A[k, n]+1 кц кц

Сколько элементов массива в результате будут равны 1?

Можно сообразить, что обрабатываются все 4 строки массива, но в первой строке элементы обрабатываются с 1, и вправо, и вниз. Сам элемент (1,1) обрабатывается дважды. То есть его значение будет 2.

Во второй строке элементы обрабатываются со второго, и так далее.

Получается итоговый массив, в котором на главной диагонали стоят 2, остальные элементы – 1. Из 16 возможных элементов вычитаем 4 элемента равных 2, остается 12 элементов, равных 1.

Если приведенные рассуждения кажутся надуманными, искусственными, просто выполните фрагмент программы.

Изначально в массиве имеем 0.

n=1 k=1

n\k	1
1	0	0	0	0
	0	0	0	0
	0	0	0	0
	0	0	0	0

Полагаем n=1 и k от 1 до 4. При выполнении тела цикла, элемент (1,1) дважды увеличится на 1, как стоящий на первой горизонтали и на первой вертикали одновременно.

n=2 k=2..4

n\k	1	2	3	4
1	2	1	1	1
2	1	0	0	0
3	1	0	0	0
4	1	0	0	0

Для случая n=2 k от 2 до 4, на 1 увеличиваются элемента, (2,2) и (2,4) строки и (2,2)..(4,2) колонки.

n=2 k=2..4

n\k	1	2	3	4
1	2	1	1	1
2	1	2	1	1
3	1	1	0	0
4	1	1	0	0

По окончании циклов, подсчитав количество 1, имеем ответ 12.

n\k	1	2	3	4
1	2	1	1	1
2	1	2	1	1
3	1	1	2	1
4	1	1	1	2

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

Дан фрагмент программы, обрабатывающей двухмерный массив A размера n.n.

Бейсик	Паскаль	Алгоритмический
k = 1 FOR i = 1 TO n c = A(i,i) A(i,i) = A(k,i) A(k,i) = c NEXT i	k:=1; for i:=1 to n do begin c:=A[i,i]; A[i,i]:=A[k,i]; A[k,i]:=c end	k:=1 нц для i от 1 до n c:=A[i,i] A[i,i]:=A[k,i] A[k,i]:=c кц

Представим массив в виде квадратной таблицы, в которой для элемента массива A[i,j] величина i является номером строки, а величина j – номером столбца, в котором расположен элемент. Тогда данный алгоритм меняет местами

1)	два столбца в таблице
2)	две строки в таблице
3)	элементы диагонали и k-ой строки таблицы
4)	элементы диагонали и k-го столбца таблицы

Полагаем k=1, I=1. Элемент (1,1) меняется сам с собой.

При i=2, имеем обмен элементов (2,2) и (1,2), меняются элементы диагонали и строки. Ответ уже ясен, но для проверки рассмотрим i=2, меняются элементы (3,3) и (1,3). По тексту задачи, первый индекс массива – номер строки, остается неизменным. Одинаковые индексы у диагональных элементов.

Ответ: меняются местами элементы диагонали и первой строки таблицы, то есть k-той, так как k=1. Этот ответ, среди предложенных, имеет номер 3.

k=1 i=1

i\k	1
1	a	Y	Q
		X
			P

Задание усложнено тем, что двумерный массив может быть представлен в виде одномерного массива строк, то есть первый индекс определяет элемент внешнего массива – строку (как в этом задании). Но его можно рассматривать и как одномерный массив колонок, в этом случае первый индекс указывал бы номер столбца. Оба представления равноправны, например в предыдущей задачи на 1 увеличивались и элементы колонок, и элементы столбцов:

A[n, k]:=A[n, k]+1;

A[k, n]:=A[k, n]+1;

Нужно внимательно читать условие заданий и выяснить, какой индекс отвечает за строку, а какой за столбец.

Обобщения массива.

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

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

В записях требует уточнений: количество и тип полей.

Как это оформляется в языке pascal показано ниже.

Структурированные типы данных - запись

PASCAL <имя записи>:record

<имя поля>:<тип поля>;

<имя поля>:<тип поля>;

...

end;

В языке BASIC нет небазовых типов, кроме массивов. Но элемент файла прямого доступа фактически является записью. Особенностью является, что все поля – строкового типа, различаются только длиной. Хранение чисел осуществляется как строки цифр.

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

При оформлении, после имени самой записи ставится точка, затем имя поля.

PASCAL <имя записи>.<имя поля>

Элементы записи могут быть любого типа (кроме файлового), в том числе и массивы, и другие записи.

Примеры записей

Строка расписания (уроков, автобусов, ТВ программ, …)

Другое обобщение понятия массив – множество.

Множество отличается от массива отсутствием порядка.

Множество - неупорядоченный набор элементов одного типа.

Оформление в языке программирования PASCAL:

Пусть имеем перечислимый тип t1.

Тогда <имя типа> = set of t1; определяет множество.

* Способ образования.

Элементы нового типа - группы выбранных элементов (в том числе и пустое множество) типа t1.

Операции над множествами в языке PASCAL

пересечение множеств a и b a*b

объединение множеств a и b a+b

разность множеств a и b a-b

Для множеств возможны:

Проверка на равенство множеств a и b a=b

Проверка на неравенство множеств a и b a<>b

Проверка, является ли a подмножеством от b a<=b , b>=a

Проверка на принадлежность элемента e множеству a e in a

Все проверки дают результат логического типа.

Типизированные константы

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

Имена типов объявляются в разделе описания типов после служебного слова TYPE. После имени следует знак равенства и полное описание определяемого типа. В дальнейшем вместо описания типа ставится только его имя.

В языке BASIC есть возможность включать данные в текст программы: В строке после слова DATA через запятую перечисляются данные. Переменные получают значения из строки DATA ... по команде READ <имя перменной>

При необходимости повторить чтение данных из строки DATA номер этой строки, перед выполнением команды READ, указывается в команде RESTORE.

В языке PASCAL можно включать данные в текст программы с помощью типизированных констант (в разделе описаний, после слова const).

Общий способ описания типизированных констант:

<имя>:<тип>=<значение> - фактически переменные с начальным значением

Примеры:

<имя>:<тип-массив>=(<значение>,...,<значение>);

<имя>:<тип-двумерный массив>=

((<значение>,...,<значение>),

...

(<значение>,...,<значение>));

<имя>:<тип-запись>=(<имя поля>:<значение>; ...;<имя поля>:<значение>);

<имя>:<тип-множество>=[<элемент>,<ограничение элементов>,...];

<имя>:<тип-указатель>=NIL;

Завершение

По окончании нашего урока, вы должны знать ответы на вопросы:

Что такое массив?, Какими параметрами он характеризуется (определяется)?

Что такое запись? Что такое множество? Что можно с ними делать?

Как оформляется и для чего служит раздел описания типов в паскале?

Как оформляются и для чего служат типизированные константы в паскале?

Попробуйте решить задачи:

Опишите на русском языке или одном из языков программирования алгоритм получения из заданного целочисленного массива размером 30 элементов другого массива, который будет содержать модули значений элементов первого массива (не используя специальной функции, вычисляющей модуль числа).