Книга: Песни о Паскале

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

Глава 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, пустые места обозначены точками, а деревья – звездочками. Засадите поле случайным образом и распечатайте его. Затем найдите левый верхний и правый нижний углы для ограды и постройте её символом решетки. Ограда должна охватывать деревья, но не выходить за пределы поля (то, что выходит за пределы, не строить). Распечатайте сад с оградой.

Оглавление книги