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

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

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

Рис.112 – Строительство империи

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

«Нашел, нашел!» – просветлел Ник, подвигаясь к компьютеру. Главная идея родилась, осталось обдумать детали. В первую очередь, следовало выбрать подходящий способ хранения границ. В 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 – это границы всех стран }