Оператор итеративного цикла с предусловием

 

Вид оператора:

While <логическое выражение> do

<простой или составной оператор тела цикла>;

Логическое выражение – это условие продолжения цикла (выполнения тела цикла). Само тело цикла это один оператор или группа операторов (в операторных скобках begin.. end). Если в момент входа в заголовок цикла логическое выражение ложно, цикл не выполнится ни разу. На это следует обращать внимание при программировании с завершением цикла по вводу признака конца. Если ввод данных выполняется целиком в цикле, перед его началом значение вводимой в дальнейшем величины следует сделать искусственно неравным признаку конца. Например:

...

WriteLn(' Какое число будет обозначать слово «Конец»?');

ReadLn(Pr);

A:=Pr+1;

While A<>Pr do

Begin

WriteLn(' Введите очередное число ');

ReadLn(A);

if A<>Pr then

...

end;

...

Этому оператору в блок-схеме соответствует структура, изображенная на рисунке

 

 

 

 

Оператор итеративного цикла с постусловием

 

Вид оператора:

Repeat

< операторы тела цикла>;

until <логическое выражение>;

Логическое выражение – это условие окончания цикла.

Тело цикла выполнится не менее одного раза, предварительные фиктивные значения для данных не требуются. Отметим, что тело цикла и при наличии нескольких операторов, в скобки begin.. end заключать не надо, так как Repeat и until сами выполняют роль скобок.

Как и в случаях с циклами For и While, в теле цикла можно использовать операторы continue и break, например, для работы с числами, пропуская отрицательные, можно использовать такой фрагмент программы:

...

WriteLn(' Какое число будет обозначать слово «Конец»?');

ReadLn(Pr);

Repeat

WriteLn(' Введите очередное число ');

ReadLn(A);

if (A<>Pr) and (A<0) then

continue; { возврат на начало тела цикла }

...

until A = Pr;

...

Этому оператору в блок-схеме соответствует структура, изображенная на рисунке

 

Глава 7. Составные типы данных

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

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

Операции обработки процессор может выполнять только над простыми элементами, входящими в составные данные, поэтому кроме общего имени должны существовать или внутренние имена входящих в них элементов, или какие-либо другие способы их выбора.

Все составные данные делятся на три различных типа

 

 

 

 

 

 

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

Массивы

Основные определения

 

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

Массивы являются наименее сложными из всех составных типов и, поэтому, реализованы во всех алгоритмических языках.

 

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

Благодаря тому, что индекс может задаваться выражением (в частности – именем переменной), Элементы массива удобно использовать в циклах. При этом обращение к разным элементам массива выглядит одинаково: A[i].

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

Массивы бывают одномерные и многомерные. Одномерные массивы иногда называют векторами, двумерные - матрицами.

В общем случае массивом может выступать совокупность однотипных составных данных, например массив структур, массив символьных строк и т.д. Такие массивы реализованы не во всех языках (в Turbo Pascal - разрешены).

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

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

Например, для двумерного массива А[MxN], состоящего из элементов длиной d байт каждый, где M - число строк, а N -столбцов, адрес элемента А[i,j] (@A[i,j]) будет вычисляться по формуле:

@A[i,j] = @A[1,1] + d*(N*(i-1) + (j-1))

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

B Turbo Pascal компоненты массива могут быть любого (в том числе - составного) типа, индексы могут быть любого порядкового типа (т.е. не вещественного), но не Longint. Описание массива можно производить двумя способами: через задание типа-массива и непосредственно.

Например:

Создание массивов с использованием описателей типов

TYPE

mas1 = array[1..100] of integer; { описатель для целочисленных

одномерных массивов длиной не более 100 элементов }

vector = array [1..30] of real; { описатель для вещественных

одномерных массивов длиной не более 20 элементов }

mas2 = array[1..8, 1..10] of Char; { описатель для символьных

двумерных массивов размерами не более 8 строк и 10 столбцов }

matrix = array[1..12] of vector; { описатель для вещественных

двумерных массивов размерами не более 10 строк и 20 столбцов. }

 

Последний описатель можно было бы задать без использования описателя типа vector:

 

matrix = array[1..12, 1..30] of real;

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

VAR { здесь выделяется место под все массивы }

Names: mas2;

Numbers, Ages: mas1;

Day_Tempr,Day_Wind: vector;

Tempr1996: matrix;

Создание массивов без использования специальных описателей типов

VAR Ball_Groop_1,B_M170: array[1..30] of real; { выделение места под два одномерных вещественных массива }

B_M175: array[1..30] of real;

Ball_Kurs: array[1:12, 1..30] of real; { выделение места под двумерный вещественный массив }

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

...

Ball_Groop1:= B_M170;

Numbers:= Ages;

If Day_Tempr=Day_Wind then...

Но недопустим ни один из операторов:

 

Ball_Kurs:= Tempr1996;

Ball_Groop1:= B_M175;

B_M175:= B_M170;

While B_M175<> B_M170 do...

Следует отметить, что оператор присваивания переписывает значения из элементов массива, стоящего в правой части в соответствующие элементы массива, имя которого указано в левой части оператора присваивания. Два совместимых массива равны (и результат сравнения равен TRUE), если каждый элемент одного массива равен соответствующему элементу второго массива. При нарушении равенства хотя бы для одной пары элементов результат сравнения - FALSE.

 

Заполнение массива данными

 

Заполнить массив значениями можно тремя способами (как и любую переменную).

Во-первых, можно задать все элементы массива, или начало массива при описании его в разделе CONST. ( В дальнейшем заданные значения можно изменить.)

 

TYPE

mas = array[1..10] of real;

CONST

A1: mas = (-5,4,-3,2,-1);

 

Во-вторых, элементы массива можно заполнить с помощью оператора присваивания:

 

for I:= 1 to M do

for j:= 1 to N do

A2[I,j]:= 1;

Наконец, в-третьих, массив можно полностью или частично заполнить вводом (с клавиатуры или из файла). В этом случае, заполнение включает ввод количества элементов массива (с проверкой допустимости введенного значения) и ввод самих элементов массива в указанном количестве. Если ввод значений предусмотрен с клавиатуры, перед каждым оператором чтения должен быть запрос на ввод. (Работа с файлами рассмотрена в главе 9). Пример заполнения массива числами с клавиатуры:

 

CONST
MIN=2;

MAX=20

...

BEGIN

...

Repeat

Writeln(' Введи длину массива');

Read(N);

if(N<MIN) or (N>MAX) then

Writeln('Недопустимое количество, введите снова');

Until (N>MIN) and (N<=MAX); { здесь MIN и MAX задают диапазон изменения индекса

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

for i:=1 to N do

begin

WriteLn(‘Введите очередное число в массив’);

ReadLn(A3[i]);

end;

...

 

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

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

 

Включает обычно вывод заголовка массива, возможно с указанием его длины, и затем вывод заполненных элементов массива в удобной для просмотра на экране (и при распечатке) форме. При выводе на дисплей можно ориентироваться на ширину экрана (80 позиций), при печати – на 60 (вдоль тетрадного листа), 76 (поперек тетрадного листа или при выводе на стандартный лист).

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

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

Например, если числа целые и находятся в диапазоне от –999 до +999, формат должен быть не менее:5 (с учетом разделяющих пробелов). Если диапазон целых чисел неизвестен, следует рассчитывать на максимум. Для самых длинных целых чисел (–32768) он составит:7 и выводить удобно по 10 значений в строке.

Для вещественных чисел, если использовать экспоненциальную форму записи, достаточно оставлять три значащие цифры, что с учетом знака, точки и порядка числа составит:10 и дополнительный пробел, например, _–0.836Е-02, а выводить имеет смысл по пять чисел в строке.

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

При выводе в конце каждой строки следует давать команду Writeln для перехода на новую строку. Определить, что пора менять строку, можно по остатку от деления текущего номера элемента на количество значений в строке. Ниже приведен пример вывода на печать одномерного вещественного массива по "k" значений в строке:

 

...

Writeln(' Исходный массив из ',N,' элементов');

for i:=1 to N do

if i mod k = 0 then { если номер элемента

WriteLn(A4[i]:8:2) кратен "к", переходим на новую строку}

else

Write(A4[i]:8:2) { печать в текущей строке}

Writeln; {переход на новую строку в конце печати}

...

 

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

 

...

Writeln(' Исходный массив из ',M,'x',N,' элементов');

for i:=1 to M do

begin

for j:=1 to N do

Write(A[i,j]:6); {печать текущей строки }

Writeln; {переход на новую строку экрана перед новой строкой массива}

end;

...

 

 

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

 

Перестановка целочисленного массива из N элементов (N<=100) в обратном порядке.

Метод решения задачи предлагается следующим: Чтобы массив оказался записанным в обратном порядке, первый элемент (A[1]) надо поменять местами с последним (A[N]), второй (A[2]) – с предпоследним (A[n-1]) и т.д. (A[i],<à A[N+1-i]). Перестановку будем выполнять, используя рабочую переменную (R). Количество переставляемых пар – N div 2.

Таким образом, при условии заполнения массива из файла (подробно работа с файлами будет рассмотрена позже), программа будет выглядеть так:

Program Revers;

{ VGI, MIT }

Var Fin,Fout:text;

A: array[1..100] of integer;

i,N,R: integer;

BEGIN

Repeat

WriteLn(’Задайте длину массива’);

ReadLn(N);

if N>100 then

WriteLn(’Нельзя больше 100’);

Until N<=100;

Assign(Fin,’S:\kurs_1\_data\DatI.txt’);

Reset(Fin);

for i:=1 to N do

Read(Fin,A[i]);

Close(Fin);

Assign(Fout,’Revers.txt’);

ReWrite(Fout);

WriteLn(Fout,’Исходный массив’);

for i:=1 to N do

if i mod 10 = 0 then { печатаем по десять чисел в строке }

WriteLn(Fout,A[i]:7)

Else

Write(Fout,A[i]:7);

WriteLn(Fout);

for i:=1 to N div 2 do

Begin

R:=A[i];

A[i]:=A[N+1-i];

A{N+1-i]:=R;

end;

WriteLn(’Измененный массив’);

for i:=1 to N do

if i mod 10 = 0 then

WriteLn(Fout,A[i]:7)

Else

Write(Fout,A[i]:7);

WriteLn(Fout);

Close(Fout);

END.

 

Второй пример. Удаление строки с минимальным значением из двумерного вещественного массива размерами M x N элементов, где M и N не превосходят 7.

Алгоритм решения состоит из следующих частей:

1. Ввод числа строк

2. Ввод числа столбцов

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

4. Открытие выходного файла и распечатка в него исходного массива

5. Поиск места, где расположен минимальный элемент массива

6. удаление строки с минимальным элементом. Удаление производится, путем переписывания на место удаляемой строки, строки, лежащей ниже (следующей). Затем, в строку, которую откопировали в вышележащую, переписывается следующая строка и т.д. Наконец, M-я строка копируется на (M-1)-е место.

7. количество строк исправленного массива уменьшается на 1.

8. Полученный массив распечатывается

 

Реализация алгоритма (с некоторыми пропусками) выглядит так:

Program DelLine;

{ VGI, MIT }

Var Fin,Fout:text;

A: array[1..7,1..7] of real;

i,j,N,M,imin,jmin: integer;

Amin: real;

BEGIN

Repeat

WriteLn(’Задайте число строк’);

ReadLn(N);

if N>7 then

WriteLn(’Нельзя больше 7’);

Until N<=7;

{ аналогично задается число столбцов N}

...

Assign(Fin,’S:\Kurs_1\_Data\DatF.txt’);

Reset(Fin);

for i:=1 to M do

for j:=1 to N do

Read(Fin,A[i,j)’

Close(fin);

Assign(Fout,’DelLine.txt’);

ReWrite(Fout);

WriteLn(Fout,’Исходный массив’);

for i:=1 to M do

Begin

for j:=1 to N do

Write(Fout, A[i,j]);

WriteLn(Fout);

end;

{ поиск места минимального элемента }

imin:=1;

jmin:=1; { сначала считаем минимальным 1-й элемент массива}

for i:=1 to M do

for j:=1 to N do

if A[i,j]<A[imin,jmin] then

Begin

imin:=i;

jmin:=j;

end;

{ Удаление строки с номером imin }

for i:=imin to M-1 do

for j:=1 to N do

A[i,j]:= A{i+1,j];

M:=M-1;

{ печатаем измененный массив, также, как и исходный и закрываем

файл с протоколом}

...

Close(Fout);

END.

 

 

Сортировки массива

 

При работе ЭВМ большую роль играет процесс выбора нужной информации из имеющихся данных. Если данные хранятся не в упорядоченном виде, время, затрачиваемое на поиск данных оказывается очень большим. Чтобы найти нужную запись из N записей, в среднем нужно перебрать N/2 записей (и это при условии, что любая запись найдется, иначе требуется больше попыток). Если же записи упорядочены, то при простейшем алгоритме двоичного поиска требуется lg₂(N) попыток. Если в базе находится 10000 записей, поиск в первом случае потребует в среднем 5000 попыток, а во втором – не более 14 попыток. Именно по этой причине, все данные в ЭВМ должны храниться в упорядоченном виде.

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

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

Запись - элементарный объект упорядочивания, может быть просто числом или составным типом - символьной строкой, документом сложной структуры и т.д. Каждая запись обладает некоторым признаком, в соответствии с которым ее можно сравнивать с другими на предмет их очередности (порядка). Такой признак называется ключем. Для ключей определено соотношение порядка, т.е. их можно сравнивать на "больше", "меньше" и "равно".

Пересортировать записи - означает расставить их так, чтобы ключи записей изменялись монотонно (или не убывали – сортировка по возрастанию, или не возрастали - сортировка по убыванию).

Понятие качества алгоритма сортировки.

Чем больше количество записей (N), тем больше действий (сравнений и переписываний) нужно сделать, чтобы упорядочить набор. При этом если при увеличении N в два раза число действий увеличивается в 8 раз, длительность алгоритма считается пропорциональной N3, если увеличивается в 4 раза - пропорциональной N2 и т.д. Чем меньше длительность, тем лучше алгоритм. Обычно алгоритмы сортировок пропорциональны N2, лучшие - пропорциональны N*ln(N). Универсального наилучшего алгоритма не существует: для разных наборов данных наискорейшими будут различные алгоритмы.

Сортировки бывают двух типов: внутренняя сортировка и внешняя сортировка.

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

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

Основные методы сортировок.

Выделяется 5 основных методов сортировки, из них различными модификациями получено множество (несколько десятков) рабочих алгоритмов сортировок. Эти методы (их суть описана ниже) называются: 1 - вставками; 2 - обменом; 3 - выбором; 4 - пересчетом; 5 - слиянием. Первые 4 метода - внутренние сортировки, последний - внешняя сортировка.

Объекты сортировки.

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

┌──────────┬──────────┬───────────┐

│адр.1 зап.│ключ1 зап.│запись N 1 │

└──────────┴──────────┴───────────┘

┌──────────┬──────────┬───────────┐

│адр.2 зап.│ключ2 зап.│запись N 2 │

└──────────┴──────────┴───────────┘

....

┌──────────┬──────────┬───────────┐

│адр.n зап.│ключn зап.│запись N n │

└──────────┴──────────┴───────────┘

В зависимости от соотношения размеров записей и ключей выбирают разные виды сортировок.

1. Если записи маленькие (числовые), упорядочивают сами записи. Это - сортировка записей.

2. Если записи большие по размерам (например, документы), а ключи - маленькие, составляют таблицу из ключей с адресами записей:

┌──────────┬──────────┐

│адр.1 зап.│ключ1 зап.│

└──────────┴──────────┘

┌──────────┬──────────┐

│адр.2 зап.│ключ2 зап │

└──────────┴──────────┘

....

┌──────────┬──────────┐

│адр.n зап.│кл. n зап.│

└──────────┴──────────┘

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

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

┌──────────┐

│адр.1 зап.│

└──────────┘

┌──────────┐

│адр.2 зап.│

└──────────┘

....

┌──────────┐

│адр.n зап.│

└──────────┘

эта таблица сортируется в соответствии с ключами, которые находятся по этим адресам и записи затем переписываются один раз в соответствии с порядком переставленных адресов. Это - сортировка адресов.