Список рекомендуемой литературы
1. Павловская Т. А. Паскаль. Программирование на языке высокого уровня: учебник. СПб.: Питер, 2008. 393 с.
2. Немнюгин С. А. Turbo Pascal. Программирование на языке высокого уровня: учебник. 2-е изд. СПб.: Питер, 2008. 544с.
3. Фаронов В. В. TurboPascal 7.0. Учебный курс: учеб. пособие. М.: Кнорус, 2009. 368 с.
4. Мишенин А. И. Сборник задач по программированию: учебно-метод. пособие. М.: Финансы и статистика, 2009. 224с.
5. Аляев Ю.А. Практикум по алгоритмизации и программированию на языке Паскаль: учеб. пособие / Ю.А. Аляев, В.П. Гладких, О.А. Козлов.- М.: Финансы и статистика, 2007. 528 с.
Глава 4. Технологии программирования на Паскале
Типы данных, определяемые программистом
Простые типы данных, определяемые программистом
Раздел описания типов
В языке Паскаль все данные, используемые программой, должны принадлежать к какому − либо заранее известному типу данных.
Напомним что, все простые типы языка Паскаль можно разделить на стандартные и пользовательские. К стандартным типам относятся типы: Integer, Real, Char, Boolean, а также некоторые другие.
Информация, которую требуется обрабатывать в программе, имеет различную структуру. Для ее адекватного представления используются пользовательские типы данных (хотя правильнее их называть: типы определяемые программистом), которые программист описывает сам в разделе описания типов type. Типу дается произвольное имя, которое можно затем использовать для описания программных объектов точно так же, как и стандартные имена типов.
|
|
|
type имя_типа = описание_типа
...
var имя_переменной : имя_типа
Например,
Type
week=(sunday, monday, tuesday, wednesday, thursday, friday, saturday);
work_week=monday..friday;
day=l..31;
Обратите внимание на то, что при объявлении пользовательских типов между их именем и конструкцией, определяющей тип, ставится знак равенства.
После того, как тип объявлен, в разделе описания переменных можно пользоваться вновь введенным идентификатором.
Раздел описания типов должен находиться перед основным блоком программы.
Можно задать тип и непосредственно при описании переменных:
var имя_переменной : описание_типа
Перечисляемый тип данных
При написании программ часто возникает потребность определить несколько связанных между собой именованных констант, имеющих различные значения. Для этого удобно воспользоваться перечисляемым типом данных, все возможные значения которого задаются списком констант.
type имя_типа = (список имен констант)
Константы в списке перечисляются через запятую, например: type Menu = ( READ , WRITE , EDIT , QUIT ).
Переменным перечисляемого типа можно присвоить либо значение одной из перечисленных констант, либо значение другой переменной того же типа, например:
|
|
|
var m, n : Menu;
…
m := READ; n := m;
Перечисляемый тип относится к порядковым типам данных. Константы в списке нумеруются с нуля. Например, Ord(READ) даст в результате 0, Succ(EDIT) — QUIT. Попытка получения значения, следующего за последним, приведет к ошибке.
Использовать перечисляемый тип в операциях ввода-вывода нельзя. Имена констант в пределах области их описания (программы или подпрограммы) должны быть уникальными.
Интервальный тип данных
С помощью интервального типа задается диапазон значений какого-либо типа.
type имя_типа = константа_1 .. константа_2
Константы должны быть одного и того же порядкового типа. Тип, на котором строится интервал, называется базовым. Константа_1 должна быть меньше или равна константе_2. Примеры описания интервальных типов:
type Hour = 0 .. 23;
Range = –100 .. 100;
Letters = 'a' .. 'z';
Actions = READ .. EDIT;
Как и для других типов, определяемых программистом, интервальный тип можно задать прямо при описании переменной, например: var r : –100 .. 100.
С переменной интервального типа можно делать все, что допустимо для ее базового типа. Ее значение должно находиться в указанном диапазоне, в противном случае произойдет ошибка времени выполнения 'Constant out of range' .
|
|
|
Интервальный тип используется в программах как самостоятельно, так и внутри определения массива.
4.1.2. Массивы
Массивы
В задачах требующих обработки большого количества однотипных величин, вместо использования множества переменных для их хранения, удобнее применить специальную структуру данных - массив.
При использовании простых переменных каждой области памяти, предназначенной для хранения какого-либо значения, соответствует свое имя. Если группе величин одинакового типа дать одно общее имя, а различать их по порядковому номеру (индексу), то можно компактно записывать множество операций с помощью циклов. Полученная структура и будет массивом. Т.е. массив – это набор однотипных величин, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу.
Виды массивов.
По структуре:
· Одномерный (вектор)
· Двумерный (таблица, матрица)
По принципу размещения в оперативной памяти:
· Динамические
· Статические (обычные)
Одномерный массив - это фиксированное количество элементов одного типа, объединенных одним именем, причем каждый элемент имеет свой уникальный номер, и номера элементов идут подряд. Например, введем 30 целых чисел от 25 до 54 и объединим их общим именем А.
|
|
|
| № | 1 | 2 | 3 | … | 29 | 30 |
| А | 25 | 26 | 27 | … | 53 | 54 |
Описание массива
1 способ: в разделе типов.
Чтобы описать массив, надо определить, какого типа его элементы и каким образом они пронумерованы (какого типа его индекс).
type имя_типа = array [тип_индекса] of тип_элемента
Здесь array и of — ключевые слова, тип индекса задается в квадратных скобках. Примеры описания типа:
type mas = array [1 .. 10] of real; [1]
Color = array [byte] of mas; [2]
Active = array [Menu] of boolean; [3]
В первом операторе описан тип массива из вещественных элементов, которые нумеруются от 1 до 10. Во втором операторе элементами массива являются массивы типа mas, а нумеруются они в пределах, допустимых для типа byte, то есть от 0 до 255. В третьей строке в качестве индекса использовано имя типа описанного, а сами элементы могут принимать значения true или false.
Тип элементов массива может быть любым, кроме файлового, тип индексов — интервальным, перечисляемым или byte. Чаще всего для описания индекса используется интервальный тип данных.
Размещение массива в памяти происходит до выполнения программы, поэтому при описании индекса можно применять только константы или константные выражения.
Обычно при описании массива верхняя граница его индекса задается в виде именованной константы, например:
const n = 6;
type intmas = array [1 .. n] of integer;
После задания типа массива переменные этого типа описываются обычным образом: var a, b : intmas.
2 способ: в разделе переменных.
A : array[1.. n ] Of Integer ;
Массив А, в котором будут храниться n целых чисел (значение n должно быть определено до описания массива).
Операции с массивами
С массивами в целом можно выполнять только одну операцию: присваивание. При этом массивы должны быть одного типа: b := a.
Все остальные действия выполняются только с отдельными элементами массива, т.е. нельзя: Write(a); Read(b).
Для обращения к элементу массива после имени массива указывается номер элемента в квадратных скобках: a[4], b[i].
С элементом массива можно делать все, что допустимо для переменных того же типа.
При обращении к элементу массива автоматический контроль выхода индекса за границу массива не производится. Для включения режима автоматического контроля необходимо добавить в любое место программы, предшествующее обращениям к элементу, ключ компиляции {$R+} или установить соответствующий режим в оболочке.
Двумерные массивы
Двумерные массивы можно представить в виде прямоугольной таблицы или матрицы.
Например, как двумерный массив будет описана матрица А размерностью 2х3 (состоящая из двух строк по три элемента в каждой):
Положение каждого элемента определяется двумя числами: номером строки, в которой находится элемент, и номером столбца. Например, а12 − это элемент, стоящий в первой строке и во втором столбце.
Имеется несколько способов объявления двумерных массивов.
Способ 1. В Паскале двухмерный массив можно описать как одномерный, элементами которого являются одномерные массивы. Например, для матрицы А, приведенной выше:
Const n=2; m=3;
Type omyarray=Array[1..m] Of real;
dmyarray=Array[1..n] Of omyarray;
Var v: omyarray; a: dmyarray;
В данном случае переменная v объявлена как одномерный массив из трех элементов вещественного типа. Переменная а описана как двухмерный массив из двух строк, в каждой по три элемента.
Способ 2. Описание массива А можно сократить, исключив определение типа omyarray в определении типа dmyarray:
Const n=2; m=3;
Type dmyarray=Array[1..n] Of Array[1..m] Of < тип элементов >;
Var a: dmyarray;
Способ 3. Еще более краткое описание массива А можно получить, указывая диапазоны изменения индексов для каждой размерности массива:
Const n=2; m=3;
Type dmyarray=Array[1..n, 1..m] Of < тип элементов >;
Var a: dmyarray;
Способ 4. Но все-таки, если нет необходимости описывать тип, то можно просто объявить массив в разделе описания переменных:
Var a: Array[1..n,1..m] Of < тип элементов >;
Обращение к элементу двумерного массива: имя массива [номер строки, номер столбца]. Например, A[1,3]:=5.
Инициализация массива
Выполнение практически всех операций с массивами требует использования циклов.
Для того, чтобы элементы массива получили свои значения существует несколько способов:
1. Ввод элементов с клавиатуры (for i:=1 to n do read A[ i]).
2. Формирование по определенному правилу (например, A [ i ]:= i +2 или B [ i ]:= B [ i -1]*2; или A [1]:=12; For i :=2 to N do A [ i ]:= A [ i ]*2; здесь каждый следующий элемент в два раза больше предыдущего. Значение первого элемента массива должно быть известно до начала цикла).
3. Простое присваивание a [1]:=12. Цикл в этом случае, по понятным причинам, не используется.
4. Формирование при помощи датчика случайных чисел (RANDOM): For i :=1 to N do A [ i ]:= Random (100)-49.
5. Чтение из файла (будет рассмотрено ниже).
Вывод элементов массива
Вывод элементов одномерного массива: for i :=1 to n dowrite A [ i ]:5). Форматированный вывод необходим потому, что иначе значения при выводе «склеятся» в одну строку.
Вывод элементов двумерного массива осуществляется при помощи вложенных циклов. Для «красивого» вывода в виде таблицы (матрицы) необходимо использовать оператор Writeln.
Пример.
For i:=1 to n do
Begin
For j:=1 to m do Write(a[i,j]):5; Writeln;
End;
Обратите внимание, что во внешнем цикле (по i) две команды (цикл for и «пустой» writeln для перехода на следующую строку).
Далее приведены фрагменты типовых задач, которые приходится решать при программировании массивов.
Типовые задачи с массивами
1. Поиск суммы (произведения )
а) Поиск суммы элементов массива
S:=0; for i:=1 to N do S:=S+A[i];
б) Поиск произведения элементов массива
P:=1; for i:=1 to N do P:=P*A[i];
2. Нахождение номеров элементов (или самих элементов) с заданным свойством
for i:=1 to N do If m[i] Mod 2 =0 then Write(i:5);
3. Нахождение количества элементов с заданным свойством. В примере: определение количества положительных (k1) и отрицательных элементов (k2).
k1:=0; k2:=0;
for i:=1 to N do If m[i] >0 then Inc(k1) else
if m[i] <0 then Inc(k2);
Write(k1:5); Write(k2:5);
4. Поиск экстремальных элементов. В примере: поиск максимального элемента.
Var A: array [1..10] of integer;
I, max:integer;
Begin
Max:=A[1];
for i:=2 to N do if A[i] > MAX then MAX:=A[i];
Write(‘MAX=’, max);
end.
5. Определение наличия в массиве элемента с заданным свойством. В примере: определение наличия нуля в массиве чисел.
Const n=20;
Var A: array [1..n] of integer;
I:integer; F:Boolean;
Begin randomize;
for i:=1 to N do begin
A[i]:=-random(20)+15;
if A[i]=0 then F:=TRUE;
End;
If F then write(‘Есть’) else write(‘Нет’) ;
end.
6. Поиск первого (последнего) элемента с данным свойством.
а) определение номера первого отрицательного элемента:
Const n=20;
Var M: array [1..n] of integer;
I:integer;
Begin randomize;
for i:=1 to N do M[i]:=-random(20)+15;
i:=1;
While (i<=n) And (m[i] >0) Do Inc(i);
Write(i) ;
end.
б) определение номера последнего отрицательного элемента:
Const n=20;
Var M: array [1..n] of integer;
I:integer;
Begin randomize;
for i:=1 to N do M[i]:=-random(20)+15;
i:=n;
While (i>=1) And (m[i] >0) Do Dec(i);
Write(i) ;
end.
7. Вставка одного (нескольких) элементов в массив
Общий алгоритм можно сформулировать так:
Найти номер элемента после (или до) которого нужна вставка (K)
После:
1. Первые K элементов остаются без изменения
2. Все элементы, начиная с k-го, сдвинуть на один назад
3. На место (k+1)-го записываем новое значение (Х), т.е. после K-го элемента
До:
1. Первые K-1 элементов остаются без изменения
2. Все элементы, начиная с k-го, сдвинуть на один вперед
3. На место k-го записываем новое значение (Х), т.е. до K-го элемента
8. Удаление одного (нескольких) элементов из массива
Общий алгоритм:
1. Найти номер удаляемого элемента ( k)
2. Сдвинуть все элементы, начиная с k-го, на один элемент влево
3. Последнему элементу присвоить значение 0, и (или) не выводить его.
9. Сортировка массива
Под сортировкой понимают процесс перестановки элементов в определенном порядке. Цель сортировки – облегчить поиск элементов в упорядоченном множестве. В этом смысле элементы сортировки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонных книгах, в оглавлениях, в библиотеках, в словарях, на складах и так далее (почти всюду, где их приходится разыскивать). Поэтому методы сортировки очень важны, особенно при обработке данных в автоматизированных информационных системах.
Существует множество методов сортировки, более подробно вы познакомитесь с ними при изучении других дисциплин.
Рассмотрим простейший (но не самый эффективный) метод сортировки - сортировку простым выбором. Это очень естественный способ сортировки, который обычно первым приходит на ум человеку, впервые столкнувшемуся с этой задачей.
Идея метода такова. Найдем в последовательности элемент с наименьшим значением и поменяем его местами с первым элементом. Затем проделаем те же действия с оставшимися N-1 элементами, затем с N-2 и так далее до тех пор, пока не останется один элемент – последний. Он будет наибольшим.
Обобщенно наш алгоритм можно записать так:
1. I:=1;
2. Пока I ≤ N-1
2.1. найти минимальный элемент и его номер в последовательности AI, …, AN.
2.2. поменять местами AI и минимальный элемент.
2.3. I:=I+1;
Поиск максимального значения и обмен элементов местами были рассмотрены ранее, следовательно, написание такой простой программы сортировки не должно вызвать затруднений.
i:=1;
while i<=n-1 do
begin k:=i; x:=a[i]; j:=i+1;
while j<=n do begin if a[j]<x then
begin x:=a[j]; k:=j; end;
j:=j+1;
end;
a[k]:=a[i]; a[i]:=x; i:=i+1;
end;
Проиллюстрируем процесс (таблица 7).
Таблица 7
Дата добавления: 2018-09-22; просмотров: 537; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!