Песни о Паскале

Глава 49 Сложные массивы

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

Вернемся в тридевятое царство, история которого ещё далека от завершения. В 38-й главе мы узнали, что для исследования материка запустили спутник, передавший на землю номера границ тамошних стран. А программа, сработанная придворным программистом Ником, нашла по этим данным соседей царства А.

Молва о научном успехе дошла до купцов, и заронила в их души зерно надежды. Душевной болью торгашей были немалые пошлины, вносимые при каждом пересечении границы. Нет, купцы не надеялись избавиться от пошлин. Но, прежде чем везти товар, они желали знать о количестве пересекаемых границ, дабы прикинуть, стоит ли овчинка выделки? Раньше купцы ехали, куда глаза глядят и часто терпели убытки. Но теперь – иное дело, – можно предвидеть расходы. Требовалась лишь программа для определения минимального количества пересекаемых границ. С этой просьбой купцы и подкатили к придворному программисту, обещая весомое вознаграждение.

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

Ник принял заказ и погрузился в работу. Однако щедрые посулы купцов не содействовали раздумьям, – вдохновение не являлось, хоть убей! В таких случаях Ник пытался отвлечься; вот и сейчас его рука потянулась к полке и достала первую попавшуюся книгу – это была история средних веков. Книга открылась на странице с рассказом о зарождении средневековой империи. Парень увлекся чтением, забыв на время о своих неудачах. Но вскоре Ника осенило: «Ведь это то, что мне нужно, – блеснуло в его голове, – я должен построить империю!»

Вам приходилось строить империи? Тогда послушайте меня – опытного «императора». Строительство начинается с собственной страны – центра империи. Я готовлю мощную армию и накапливаю прочие ресурсы: оружие, горючее, продовольствие. Все это нужно для «добровольного» присоединения соседей. Затем нападаю на них и покоряю поодиночке. После такой завоевательной кампании рождается новая страна с расширенными границами и другими соседями, которые ещё не ведают о своей судьбе! Дав отдых армии, и накопив ресурсы, я предпринимаю следующую завоевательную кампанию и присоединяю соседей своих бывших соседей. Взгляните на рис. 112, – если строительство империи начать из страны D, то в ходе первой кампании будут поглощены соседи A, C и E, а в ходе второй – их соседи, – страны B, I и F.

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

«Нашел, нашел!» – просветлел Ник, подвигаясь к компьютеру. Главная идея родилась, осталось обдумать детали. В первую очередь, следовало выбрать подходящий способ хранения границ. В 38-й главе для этого использовано несколько переменных-множеств. Теперь так не годится, – догадался Ник, – ведь для каждой завоевательной кампании мне надо организовать цикл. А там где циклы, там и массивы. Стало быть, мне нужен массив множеств. Ник нарек этот тип данных именем TStates.

type TBoundSet = set of 1..255; { множество границ одной страны }

    TStates = array ['A'..'Z'] of TBoundSet; { массив из множеств }

var States : TStates;     { Переменная-массив }

Вы помните, как именовались страны в тех местах? Буквами латинского алфавита. Это надоумило Ника индексировать массив именно символами, – ведь это один из перечислимых типов, а все они пригодны для индексации. Тогда множество границ страны B, имя которой хранится в символьной переменной X, извлекается из массива множеств States так:

var B : TBoundSet; { множество границ одной страны }

…

    B:= States[X]; { здесь X = ’A’…’Z’ – символ-название страны }

Но как в таком случае перебирать элементы массива? Ведь к символу не прибавишь единицу! Спасает функция Succ. Напомню, что она возвращает следующее по порядку значение перечислимого типа, например:

    X:= ’A’;

    X:= Succ(X);     { X = ’B’ }

    X:= Succ(X);     { X = ’C’ }

Ещё один подводный камень, вовремя подмеченный Ником, был таков. При вводе имени несуществующей страны программа зациклится, вращаясь в замкнутом круге. Потому при вводе данных организован упрямый цикл REPEAT-UNTIL, вынуждающий пользователя ввести правильные названия стран.

И, наконец, последнее замечание к программе «P_49_1» касается переменной Temp (что значит «временная»). Поскольку текущие границы империи накапливаются в переменной EmpireB и расширяются в ходе кампании, то определять бывших соседей по этим границам нельзя! Поэтому предыдущие границы империи перед началом цикла запоминаются в переменной Temp.

    Temp:= EmpireB; { Запоминаем границы империи до начала кампании }

Теперь рассмотрите программу «P_49_1» и испытайте её.

{ P_49_1 – Решение «купеческой» задачи о пересечении границ }

type TNameRange= 'A'..'Z';     { Диапазон возможных названий стран }

    TNameSet = set of TNameRange; { Множество названий стран }

    TBoundSet = set of 1..255; { множество границ некоторой страны }

    { Массив множеств TStates – это границы всех стран }

    TStates = array ['A'..'Z'] of TBoundSet;

    { Процедура чтения множества чисел (границ) из строки файла }

procedure ReadSet(var aFile: text; var aSet : TBoundSet);

var k : integer;

begin

    while not Eoln(aFile) do begin

    Read(aFile, k);

    aSet:= aSet+[k];

    end;

    Readln (aFile);

end;

    { Глобальные переменные }

var FileIn : text;     { Входной файл, полученный со спутника }

    States : TStates;     { Массив множеств границ }

    Names : TNameSet;     { Множество имен всех стран на карте }

    C1, C2 : char;     { Имена стран "откуда" и "куда" }

    C     : char;     { Рабочая переменная для имен стран }

    EmpireB: TBoundSet; { Границы империи }

    Temp : TBoundSet; { Предыдущие границы империи }

    EmpireN: TNameSet;     { страны империи }

    Counter: integer;     { Счетчик пересечений границ (результат) }

begin     {--- Главная программа ---}

{ Открываем входной файл }

Assign(FileIn, 'P_38_3.in'); Reset(FileIn);

{ Готовим цикл чтения массива множеств }

Names:=[ ]; { Названия стран }

C:= 'A'; { Первый индекс в массиве стран }

while not Eof(FileIn) do begin { Цикл чтения массива множеств }

    ReadSet(FileIn, States[C]); { Чтение одного множества }

    Names:= Names+[C];     { Добавляем имя страны }

    C:= Succ(C);     { Переход к следующей букве }

end;

Close(FileIn); { Теперь входной файл можно закрыть }

repeat { «Упрямый» цикл чтения правильных имен стран }

    Write('Откуда: '); Readln(C1);

    Write('Куда : '); Readln(C2);

    { Переводим имена стран в верхний регистр }

    C1:= UpCase(C1); C2:= UpCase(C2);

    { Если имена не совпадают и оба достоверны, значит ввод правильный,

    в таком случае выходим из цикла, а иначе повторяем ввод }

    if (C1<>C2) and (C1 in Names) and (C2 in Names)

    then Break

    else Writeln('Ошибка! Повторите ввод имен стран');

until False;

{ Подготовка к присоединению стран }

EmpireB:= States[C1]; { Империя начинает расширяться от страны C1 }

EmpireN:= [C1];     { Здесь накапливаются имена присоединенных стран }

Counter:= 0;     { Счетчик "завоевательных кампаний" }

{ Цикл, пока не будет присоединена страна C2 }

repeat

    { Подготовка к "завоевательной кампании" }

    C:='A';     { Первый индекс в массиве множеств границ }

    Temp:= EmpireB; { Запоминаем предыдущие границы империи }

    { Цикл очередной "завоевательной кампании" по всем странам массива }

    while C in Names do begin

    { Если страна имеет общую границу, присоединяем её к империи }

    if (Temp * States[C]) <> [] then begin

    EmpireB:= EmpireB + States[C]; { Добавляем границы }

    EmpireN:= EmpireN + [C]; { Добавляем имя страны }

    end;

    C:= Succ(C); { Следующий индекс в массиве множеств границ }

    end; { очередная кампания завершена }

    Inc(Counter); { Наращиваем счетчик "завоевательных кампаний" }

until C2 in EmpireN; { Пока не будет присоединена страна C2 }

{ Печать результата }

Writeln('Пересечений границ: ', Counter); Readln;

end.

Так была решена задача о минимальной сумме пошлин. Купцы, было, обрадовались, но вскоре явились с новым поклоном. Много ль толку от знания расходов, если не знаешь пути, по которому надо двигаться? «Сделай нам, братан, что-то типа навигатора для поиска кратчайшего пути между странами. Так, чтобы нам меньше этих пошлин платить, – умоляли купцы, – мы не поскупимся!» Ник обещал подумать, и продолжение истории следует.

Кто не любовался яркой световой рекламой? Рекламный щит составлен из лампочек, а изображение «рисуется» их включением и отключением, – этим управляет микропроцессор. Компьютер у нас под рукой, почему бы не соорудить такой рекламный щит прямо на экране? Научим компьютер выполнять с изображением на нашем щите три действия: два зеркальных отражения (относительно горизонтальной и вертикальной осей), а также инверсию изображения (рис. 113).

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

Размер картинки выберем таким, чтобы она помещалась на экране монитора. В текстовом режиме экран содержит 25 строк по 80 символов в каждой. Мы ограничимся 20 строками по 40 символов. Тогда воображаемая вертикальная ось нашего щита пройдет между 20-м и 21-м столбцами, а горизонтальная – между 10-й и 11- строками.

Разобравшись с видимым представлением щита, обратимся к невидимому: придумаем способ хранения в памяти «лампочек» щита. Годятся ли символьные переменные, – те же крестики и нолики? Да, но мне приглянулся способ, лучше отвечающий природе рекламного щита. Ведь каждая из лампочек может быть либо включена либо погашена, – их состояние можно отразить в булевых переменных. А сколько их понадобится? Не так уж мало – 800 штук (20 строк по 40 в каждой). Разумеется, нужен массив, но каким он будет? Предположим, что тип «рекламный щит» (Desk) объявлен так:

type TDesk = array [1..800] of Boolean;

Здесь разумеем, что первые 40 элементов массива хранят верхнюю строку щита, следующие 40 элементов, – вторую строку и так далее. Не очень удобно, правда?

Можно сделать иначе: сначала объявить отдельную строку щита TLine как массив из 40 лампочек.

type TLine = array [1..40] of Boolean;

И тогда весь щит представится массивом из 20 таких строк, – это будет массив массивов.

type TDesk = array [1..20] of TLine;

То же самое можно записать развернуто, вот так:

type TDesk = array [1..20] of array [1..40] of boolean;

Подчеркнутое означает отдельную строку щита. Паскаль разрешает собрать все индексы объявления внутри одних скобок и записать всё это ещё короче.

type TDesk = array [1..20, 1..40] of boolean;

Так мы получили структуру, которую математики называют матрицей, а программисты – двумерным массивом. Матрицы состоят из строк и столбцов. Для доступа к элементам матрицы нужны два индекса, один из которых указывает номер столбца, а другой – номер строки. Например, элемент матрицы Desk, стоящий в 5-м столбце 3-й строки, доступен так:

    Desk[3, 5]

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

const Cx = 40; { количество столбцов (ширина) }

    Cy = 20; { количество строк (высота) }

type TDesk = array [1..Cy, 1..Cx] of boolean; { тип «рекламный щит» }

var Desk : TDesk; { переменная «рекламный щит» }

Здесь пределы для индексов указаны через константы Cx и Cy. Заполнить матрицу значением FALSE можно двумя вложенными циклами:

    for y:=1 to Cy do

    for x:=1 to Cx do Desk[y, x]:= False;

То же самое делается быстрее и короче известной вам процедурой заполнения FillChar:

    FillChar(Desk, SizeOf(Desk), false);

Здесь значение SizeOf(Desk) составит 800 – это количество элементов матрицы.

Можно обрабатывать и отдельные строки, и отдельные столбцы матрицы. Например, заполнить значением TRUE 5-й столбец:

    for y:=1 to Cy do Desk[y, 5] := True;

А для заполнения 3-й строки организовать такой цикл:

    for x:=1 to Cx do Desk[3, x] := True;

Если вам понятна техника работы с матрицами, перейдем к программе «P_49_2».

Начнем с процедуры ReadDesk, что вводит матрицу из файла. Условимся считать, что крестикам в матрице Desk соответствует TRUE, а ноликам – FALSE. Входной файл обрабатываем построчно: сначала очередную строку читаем во вспомогательную строковую переменную S, а затем символы этой строки преобразуем в булевы значения оператором сравнения (вы помните, что оператор сравнения дает булев результат?).

    Desk[y,x]:= S[x]='+'; { TRUE, если S[x] содержит крестик }

Следовательно, для ввода матрицы нужны два вложенных цикла: внешний – по строкам и внутренний – по столбцам.

Схоже работает и процедура WriteDesk, выводящая матрицу на экран. Здесь внутренний цикл формирует строку из 40 символов, каждый из которых может быть либо крестиком либо ноликом. Выбор пары символов – дело вкуса, в нашем случае пара определяется строковой константой CSymbols.

const CSymbols : string = '0+';

Нужный символ из этой строки выбирается по индексу.

    S:= S + CSymbols[1+ Ord(Desk[y, x])];

Так, для значений Desk[y,x], равных FALSE, будет выбран первый символ строки ('0'), а для TRUE – второй ('+'), что равнозначно следующему громоздкому оператору.

    if Desk[y, x]

    then S:= S + CSymbols[2]

    else S:= S + CSymbols[1]

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

Процедура инверсии рекламного щита ещё проще, – она меняет значения элементов матрицы на противоположные. Наконец, в главной программе после чтения из файла исходного изображения организован цикл ввода и обработки команд пользователя. Вводя одну из трёх команд (1, 2 или 3), пользователь крутит изображение туда-сюда, а также инвертирует его. Вот полный текст этой программы.

{ P_49_2 – Рекламная панель "крестики-нолики" }

const Cx = 40; { количество столбцов (ширина) }

    Cy = 20; { количество строк (высота) }

type TDesk = array [1..Cy, 1..Cx] of boolean;

var Desk : TDesk;

    { Чтение исходного состояния панели из текстового файла }

procedure ReadDesk(var F: Text);

var x, y: integer; { x – индекс столбца, y – индекс строки }

    S: string;

begin

FillChar(Desk, SizeOf(Desk), false);

y:=1;

while not Eof(F) and (y<=Cy) do begin

    Readln(F, S);

    x:=1;

    while (x<=Length(S)) and (x<=Cx) do begin

    Desk[y,x]:= S[x]='+';

    Inc(x); { x:= x+1 }

    end;

    Inc(y);     { y:= y+1 }

end

end;

    { Вывод текущего состояния панели в текстовый файл }

procedure WriteDesk(var F: Text);

const CSymbols : string = '0+';

var x, y: integer; S: string;

begin

for y:=1 to Cy do begin

    S:='';

    for x:=1 to Cx do S:= S + CSymbols[1+ Ord(Desk[y, x])];

    Writeln(F, S);

end;

end;

    { Вспомогательная процедура обмена местами булевых переменных }

procedure Swap (var a, b : boolean);

var t : boolean;

begin

t:=a; a:=b; b:=t;

end;

    { Отражение относительно вертикальной оси }

procedure Vert;

var x, y: integer;

begin

for y:=1 to Cy do

for x:=1 to Cx div 2 do Swap(Desk[y, x], Desk[y, Cx-x+1])

end;

    { Отражение относительно горизонтальной оси }

procedure Horisont;

var x, y: integer;

begin

for y:=1 to Cy div 2 do

    for x:=1 to Cx do Swap(Desk[y, x], Desk[Cy-y+1, x])

end;

    { Инверсия рекламной панели }

procedure Invers;

var x, y: integer;

begin

for y:=1 to Cy do

    for x:=1 to Cx do Desk[y, x]:= not Desk[y, x]

end;

var FileIn : Text;

    cmd : integer;

begin     {=== Главная программа ===}

Assign(FileIn, 'P_46_2.in'); Reset(FileIn);

ReadDesk(FileIn);

Close(FileIn);

repeat

    WriteDesk(Output);     { вывод «щита» на экран }

    Writeln;

    Write('1- Вертикальная; 2- Горизонтальная; 3- Инверсия, 0- Выход : ');

    Readln(cmd);     { Ввод команды }

    case cmd of

    1: Vert;     { отражение относительно вертикальной оси }

    2: Horisont; { отражение относительно горизонтальной оси }

    3: Invers;     { инверсия }

    else Break;     { выход из цикла и завершение программы }

    end;

until cmd=0;

end.

Добавлю ещё два слова о константе CSymbols.

const CSymbols : string = '0+';

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

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

• Элементами массивов могут быть как простые, так и сложные типы данных, например, другие массивы или множества.

• Массив массивов называют двумерным массивом или матрицей.

• Для доступа к элементам матрицы необходимы два индекса: один – для столбца, другой – для строки.

А) По ходу строительства империи её бывшие границы – каналы – оказываются внутри новой страны и мешают перемещению граждан, – их лучше сровнять. Дополните программу «P_49_1» с тем, чтобы она печатала эти бывшие границы. Или слабо?

Б) Измените внутреннее представление рекламного щита так, чтобы вместо булевых элементов использовать символы. Внесите необходимые изменения в программу и проверьте её.

В) В 38-й главе для нахождения простых чисел мы воспользовались множеством. К сожалению, мощность множеств в Паскале невелика (256), поэтому находить большие простые числа мы не могли. Но выход есть – это массив булевых переменных. По сути, это множество, судите сами. Объявим массив из 1000 элементов.

const CSize = 1000;

type TBoolSet = array [1..CSize] of Boolean;

var BS : TBoolSet;

Теперь условимся, что массив, заполненный значением FALSE, – это пустое множество. А если множество содержит числа A и B, то соответствующие им элементы массива BS[A] и BS[B] содержат TRUE. Тогда операции с этим придуманным нами типом-множеством можно выполнять так (справа показаны аналогичные операции с обычным множеством чисел S).

FillChar(BS, SizeOf(BS), false); { S:= [] – пустое множество }

FillChar(BS, SizeOf(BS), true); { S:= [1..1000] – полное множество }

BS[N]:= true;     { S:= S + [N] – добавление элемента }

BS[N]:= false;     { S:= S – [N] – удаление элемента }

if BS[N] then …     { if N in S then … – проверка вхождения }

Воспользуйтесь таким массивом для поиска простых чисел в диапазоне от 1 до 1000.

Г) Садовая ограда. Вернувшись с курорта, фермер Лефт обнаружил на своем поле чудом выросший сад. Для сохранения деревьев он обнес его прямоугольной оградой. Пусть ширина и высота поля заданы константами CX и CY, пустые места обозначены точками, а деревья – звездочками. Засадите поле случайным образом и распечатайте его. Затем найдите левый верхний и правый нижний углы для ограды и постройте её символом решетки. Ограда должна охватывать деревья, но не выходить за пределы поля (то, что выходит за пределы, не строить). Распечатайте сад с оградой.