Александр Цветков - Язык программирования PASCAL Страница 9

Таким образом, когда мы просмотрим весь массив, окажется, что наша переменная содержит искомое значение:

{определение максимального значения}

max:=A[1];

for i:=2 to N do if A[i]>max then max:=A[i]; writeln('Maximum=',max);

Напишем теперь целиком программу, использовав полученные знания:

Program Massiv;

Const N = 10;

Var A : array [1..N] of integer;

i, max : integer;

begin

for i:=1 to N do // Ввод массива

begin

write( 'Ввeдите ',i,'-й элемент: ');

readln(A[i])

end;

max:=A[1]; // Поиск максимального значения

for i:=2 to N do

if A[i]>max then

max:=A[i];

writeln( 'Maximum=',max);

end.

- 35 -

Задание 12

1. Внимательно прочитать текст. Знать определение массива и способы его описания. (2 балла)

2. Напишите программу, которая вводит с клавиатуры значения массива, состоящего из 10 элементов, а затем выводит его. (2 балла)

3. Модифицируйте предыдущую программу, так чтобы она выводила элементы массива в обратном порядке (используйте цикл for i:=N downto 1 do). (1 балл)

4. По аналогии с примером на стр. 35 напишите программу, находящую минимальный элемент массива и выводящую его значение. (2 балла)

5. Модифицируйте предыдущий пример, так чтобы программа определяла максимальный и минимальный элемент массива. (1 балл)

6. * Напишите программу, которая бы определяла среднее арифметическое значение элементов массива (конечно, это будет вещественная величина типа real) (* 3 балла)

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

(* 3 балла)

Задачи, отмеченные *, являются необязательными и их баллы – дополнительными.

- 36 -

Тема №13. Сортировка массивов

Тема имеет исключительно важное значение

Первой серьезной задачей программирования, с которой сталкивается начинающий программист – это задача сортировки массива. Под сортировкой понимается упорядочивание элементов массива по возрастанию (или по убыванию) без создания копии массива (т.е. «на месте»).

Самый простой алгоритм – это линейная сортировка. Рассмотрим рис. 13.1.

Проведем последовательно сравнение первого элемента со всеми последующими, при если при очередном сравнении (например сразу 4 и 2) выяснится, что элементы стоят в «неправильном» порядке – переставим их местами, затем продолжим сравнение

(рис. 13.2). По окончании одного прохода, можно сказать, что в первом элементе массива находится минимальный элемент (Рис. 13.4).

Рис 13.1

Рис 13.2

Рис 13.3

Рис 13.4

Далее применим указанную процедуру к неотсортированному «остатку» массива (рис. 13.5) до тех пор, пока не переставим два последних элемента (рис. 13.6-13.7).

Рис 13.5

Рис 13.6

Рис 13.7

Рис 13.8

Алгоритм линейной сортировки очень прост, но не экономичен, среднее число просмотров и перестановок пропорционально квадрату числа элементов (точнее -N2 /2 ).

- 37 -

Приведем программу сортировки. Обратите внимание, что мы использовали массив в качестве параметра процедуры. Для этого необходимо создать тип Massiv (стр. 34). Часто для экономии памяти массив передают через var-параметр (стр. 32), даже если не предполагается его модифицировать в подпрограмме. Т.е. заголовок процедуры print мог бы выглядеть следующим образом:

procedure print (var m : Massiv); .

Program LinerSort;

Const N = 10; // Число элементов массива

Type Massiv = array [1..N] of integer; // Определение типа Massiv

procedure swap(var x,y: integer); // Перестановка элементов местами

var z : integer;

begin

z:=x; x:=y; y:=z;

end;

procedure print(m : Massiv); // Вывод массива

var i : integer;

begin

for i:=1 to N do write(m[i]:5);

writeln; // Новая строка

end;

// Переменные главной программы

var a : Massiv; i,j : integer;

begin

// Заполнение массива случайными числами в диапазоне от 0 до 99

for i:=1 to N do a[i]:=random(100);

print(a); // Вывод массива

for i:=1 to N-1 do // Внешний цикл до N-1 (обратите внимание!)

for j:=i+1 to N do // Внутренний цикл от i+1 (обратите внимание!) if (a[i]>a[j]) then swap(a[i],a[j]); // Перестановка элементов

print(a); // Вывод отсортированного массива

end.

Задание 13

1. Внимательно прочитать текст. Оформите сортировку массива в виде отдельной процедуры (здесь уже применение var-параметра будет обязательным). (2 балла)

2. Добавьте в процедуру сортировки операторы, которые позволил ли бы узнать сколько раз происходят перестановки в процессе сортировки. Выясните этот вопрос для N=10, 100, 1000.

(3балла) - 38 -

Тема №14 Работа с файлами

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

В ABC Pascal есть два вида файлов: текстовые и типизированные. В типизированных файлах обмен с внешними устройствами производится без какого либо преобразования данных, т.е., например, числа типа integer непосредственно копируются на диск, занимая по 4 байта каждое. Попытка просмотра такого файла в текстовом редакторе обречена на неудачу, мы увидим лишь бессмысленный набор знаков. Однако скорость ввода/вывода для таких файлов будет максимальной. Типизированные файлы мы рассмотрим позже в связи с типом данных record.

Работа с текстовым файлами очень похожа на работу с обычным консольным вводом/выводом. Числовые данные преобразуются в цифры в соответствии с заданными форматами (стр. 15 и стр. 26). Строковый и символьный тип данных выводится без преобразований. Следует учесть, что текстовый файл может быть открыт либо на чтение, либо на запись

Созданный текстовый файл можно прочитать в простом текстовом редакторе (notepad, aditor, в редакторе ABC Pascal, [можно и в Word[12]]). В текстовом файле ABC Pascal используется кодировка Win-1251, в которой один символ занимает один байт.

Текстовый файл можно создать в редакторе (в соответствии с указанными правилами) и прочитать в программе на ABC Pascal.

Рассмотрим сразу простой пример – вывод таблицы квадратов первых 10 чисел в текстовый файл table.txt.

Program TextOut;

const name = 'text.txt'; // имя файла в текущем каталоге

var f : text; // файловая переменная

n : integer; // переменная для цикла for

begin

assign (f,name); // связывание файловой переменной с именем файла на диске

rewrite (f); // создание и открытие файла на запись

for n:=1 to 10 do writeln(f,n:2,sqr(n):4); // вывод в файл writeln(f,...);

close (f); // закрытие файла, сохранение всех еще незаписанных данных на диск

end.

В этом пример надо обратить внимание на несколько операторов:

1. f : text – переменная специального встроенного типа «текстовый файл»;

2. assign (f,name) – сопоставление файлу f в программе файла name на диске;

3. rewrite (f) – «перезаписывает» файл f, т.е. либо создает новый пустой файл, либо уничтожает старый (будьте осторожны поэтому) и опять создает новый пустой файл;

4. writeln (f,…) – модификация уже известного оператора writeln, отличается от привычного только тем, что первый параметр – имя файловой переменной

5. close (f) – файлы надо обязательно закрывать, особенно файлы, открытые на запись (как в приведенном примере), иначе часть данных может быть утеряна.

- 39 -

Вместо оператора rewrite, файл можно открыть оператором append, в этом случае будет произведено открытие уже существующего файла в режиме дозаписи в конец файла.[13]

Рассмотрим теперь пример чтения уже существующего файла, в качестве файла используем созданный в предыдущем примере файл text.txt.

Program TextIn;

Uses CRT;

const name = 'text.txt'; // имя файла в текущем каталоге

var f : text; // файловая переменная

a,b : integer; // переменные для чтения

begin

assign (f,name); // связывание файловой переменной с именем файла на диске