Олег Деревенец - Песни о Паскале

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

Вам приходилось строить империи? Тогда послушайте меня – опытного «императора». Строительство начинается с собственной страны – центра империи. Я готовлю мощную армию и накапливаю прочие ресурсы: оружие, горючее, продовольствие. Все это нужно для «добровольного» присоединения соседей. Затем нападаю на них и покоряю поодиночке. После такой завоевательной кампании рождается новая страна с расширенными границами и другими соседями, которые ещё не ведают о своей судьбе! Дав отдых армии, и накопив ресурсы, я предпринимаю следующую завоевательную кампанию и присоединяю соседей своих бывших соседей. Взгляните на рис. 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]; { Здесь накапливаются имена присоединенных стран }