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

Глава 59 Крупные проекты

Вы заметили, насколько разбухли наши программы? Если так пойдет и дальше, то скоро вам понадобятся инструменты, применяемые в крупных проектах.

Пока я возился с новой программкой, мой холодильник опустел, а на кухне скопилась немытая посуда. Впрочем, это пустяки в сравнении с заботами наших предков – крестьян, что жили сотни лет назад. Смотрите: вот мужик в окружении десятка голодных ртов, а там ещё князь с дружиной. И всех накорми, одень, согрей. А делать все самому: пахать и сеять, избу рубить, ткать, шить и лапти плести. Эта морока называлась натуральным хозяйством.

С годами жизнь помаленьку наладилась: явились купцы, оживили торговлю и ремесла. Многие крестьяне бросили плуг, и ушли кто в кузнецы, кто в башмачники, а тот стал ткачом, – так возникло разделение труда. Потом появились фабрики и первые станки. И вот настало наше время – время огромных фабрик и сложнейших станков.

Взять хотя бы производство автомобиля – не самого сложного изделия по нынешним временам. А сколько народу копошится вокруг! Автомобильные заводы грандиозны, хотя здесь лишь собирают машины из частей, что делают на других заводах. Части сложных изделий называют узлами или модулями. Модуль – это часть изделия, которую можно изготовить и проверить отдельно от целого. Сборка изделий из модулей дала и высокое качество товара, и бешеную производительность труда. Так новые технологии породили и роскошные машины, и свободное время, убиваемое нами в автомобильных пробках.

Говорят, что история повторяется, ведь с технологиями программирования случилось то же самое, но гораздо быстрее. Ещё полвека назад одну программу мастерил один человек, – то была эпоха первых компьютеров и «натурального хозяйства» в программировании. По мере развития компьютеров росли и аппетиты пользователей, усложнялись решаемые задачи. Сообразно задачам усложнялись программы, и производство их в одиночку стало немыслимо. Потребовались разделение труда и специализация программистов, – точь-в-точь как в промышленности. И теперь производством сложных программ заняты программистские «фабрики».

Так что же это такое, технологии программирования? Алгоритмы какие-то? Или сверхсильные компьютеры? Нет, технологии – это орудия труда и средства его разумной организации. В чем они состоят применительно к нашему ремеслу?

Вам срочно потребовалась новая программа? Так призовите больше программистов и пусть они трудятся разом! Легко сказать, но как это сделать? Могут ли три писателя сразу сочинять один роман? Первый строчит начало, второй – середину, а третий – окончание? Или три художника писать одну картину? Но в программировании такое возможно! – выручает модульная организация программ.

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

Разделять на модули полезно даже небольшие проекты. Ведь модули – это своего рода склады, хранящие процедуры, функции и другие полезные вещи, – эти запасы пригодятся в других проектах. Модули в Паскале называют ещё библиотеками. Если так, то их содержимое – процедуры и функции – можно уподобить книгам. В поставку IDE включен ряд библиотек, содержащих массу полезных процедур, функций и типов данных. Это богатство служит для связи с операционной системой, устройствами ввода-вывода, и помогает строить красивые оконные интерфейсы. Фирменные библиотеки сделают ваши программы по-настоящему профессиональными, вам надо лишь разобраться в технологии модульного программирования.

Рассмотрим заурядный случай. Положим, вы работаете над проектом строк эдак на пятьсот, что составляет десяток страниц печатного текста. Немалая часть вашей программы – процедуры, функции – уже отлажена, проверена и может пригодиться в других работах. Файл программы разбух, и потому работать с ним неудобно. К чему эти готовые куски маячат перед глазами и мешают рыться в проблемных частях? Зреет здравая мысль: а не вынести ли их куда-нибудь в другой файл? Но так, чтобы связь с ними, не терялась. А потом, при необходимости, воспользоваться этими кусками в других проектах. Эти разумные мысли ведут вас к модульному программированию.

Сейчас мы разобьем на модули одну из наших программ. Нужен «доброволец», пусть им будет программа «P_56_1». Мы распилим её на две части подобно тому, как фокусник распиливает артистку в цирке. Не пугайтесь, — программа, как и артистка, останется живёхонька и здоровёхонька. Напомню, что «P_56_1» – это шуточная программа для перестановки строк файла в обратном порядке. Вот её схема, где тела процедур я заменил многоточиями, а часть комментариев удалил. Для экономии места дальше я буду показывать программу схематично.

{ P_56_1 – перестановка строк файла }

type PRec = ^TRec;

    TRec = record

    mStr : string;

    mNext : PRec;

    end;

var Stack : PRec; { Голова стека }

procedure Push(const arg : string);

{... }

end;

function Pop(var arg : string): boolean;

{... }

end;

{ – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - }

var F : text; S : string;

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

{... }

end.

Вероятно, средства для работы со стеком пригодятся нам где-то ещё, и есть смысл сохранить их на складе. Разделим программу на две части. Первую часть, до пунктирной линии – подпрограммы Push, Pop, объявление типа и переменную Stack – скопируем в другой файл и назовем его «MyLibr» – моя библиотека. Сохраним библиотеку в папке с нашими программами. Здесь вам пригодится умение работать с несколькими окнами и держать открытыми оба файла.

Скопированный кусок в исходной программе теперь не нужен, – выбросим его, а то, что осталось, сохраним под именем «P_59_1».

{ P_59_1 – Первичный файл проекта }

var F : text; S : string;

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

{... }

end.

Файл с главной программой называют первичным (Primary), стало быть, «P_59_1» – это первичный файл нашего проекта. Будет ли он компилироваться? Ясно, что нет. Ведь там вызываются удаленные из файла процедура и функция. Надо подсказать компилятору, что они переехали в файл «MyLibr». Для такой переадресации служит список импорта, который возглавляет ключевое слово USES. Пользоваться списком импорта легко, – достаточно поместить его в начале программы, перечислив после слова USES имена нужных модулей (несколько имен разделяются запятыми). В нашем случае внешним модулем является файл «MyLibr», поэтому дополненный списком импорта первичный файл станет таким.

{ P_59_1 – Первичный файл проекта }

uses MyLibr; { импортируемый модуль }

var F : text; S : string;

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

{... }

end.

Как видите, расширение файла в списке USES не указывают, а сам список завершает точка с запятой. Теперь все, что компилятор не найдет в основной программе, он будет искать в файле «MyLibr». Говорят, что первичный файл импортирует модуль «MyLibr». Компилируется такой проект из двух файлов как обычно – нажатием клавиши F9. Впрочем, для успешной компиляции время ещё не пришло.

Теперь обратимся к файлу «MyLibr». На первый взгляд он содержит всё нужное для компиляции, но это не так. Ведь это не программа, а лишь часть её – модуль. Файлу надо придать особую форму – форму библиотечного модуля, что достигается вставкой в него четырех обязательных ключевых слов (ниже они выделены).

unit MyLibr;     { имя библиотечного модуля }

interface     { секция интерфейса }

{...}

{- – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – -}

implementation { секция реализации }

{...}

end.

Обратите внимание на последнее слово END с точкой. Так же, как в главной программе, оно обязательно и завершает библиотечный модуль.

Но открывает файл ключевое слово UNIT (модуль), – оно назначает модулю имя. Имя указывают за словом UNIT через пробел, эта строка завершается точкой с запятой. Имя модуля должно совпадать с именем файла, но без расширения PAS. Впрочем, имя может быть и длиннее – до 63-х символов, но первые восемь из них должны повторять имя файла. Итак, присвойте модулю имя MyLibr.

Следующие два ключевых слова: INTERFACE (интерфейс) и IMPLEMENTATION (реализация) делят модуль на две части. Эти части так и называются: секция интерфейса и секция реализации. Важно правильно расставить эти ключевые слова. Кстати, точка с запятой за ними не ставится!

Начнем с секции реализации, хотя по порядку она идет второй. Эта секция должна вмещать всё (или почти всё), что требуется для работы модуля: объявления типов, констант, переменных, а также процедуры и функции. Иными словами, в неё сейчас свалим то, что перетащили из основной программы. Итак, слово IMPLEMENTATION мы поставим перед описанием типов, и в результате библиотечный файл станет таким.

unit MyLibr;     { имя библиотечного модуля }

interface     { секция интерфейса }

{- – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – -}

implementation { секция реализации }

type PRec = ^TRec;

    TRec = record

    mStr : string;

    mNext : PRec;

    end;

var Stack : PRec; { Голова стека }

procedure Push(const arg : string);

{... }

end;

function Pop(var arg : string): boolean;

{... }

end;

end.

Теперь обратимся к секции интерфейса. Хотя слово INTERFACE уже на месте, но секция пока пуста. Каково её назначение? Здесь пора рассказать о видимости объектов, размещенных в модуле. Точнее, о видимости их за пределами этого модуля. Оказывается, что всё, что помещено нами в секцию реализации, невидимо извне, скрыто от посторонних глаз. Так устроено по причинам, которые мы обсудим позже. Но для компиляции проекта надо приоткрыть часть модуля внешнему миру. Иначе из главной программы (которая проживает в другом файле) не будут видны нужные ей идентификаторы библиотечного модуля. Для этого и нужна секция интерфейса.

На обозрение выставим только те идентификаторы, которые нужны внешним модулям. Что именно? Как это узнать? Самый верный способ – запустить компиляцию первичного модуля, и тогда компилятор покажет первый незнакомый идентификатор, – его описание и разместим в секции интерфейса. Повторная компиляция выявит следующий неизвестный идентификатор. Так постепенно мы обнаружим, что первичный модуль нуждается в переменной Stack, процедуре Push и функции Pop. Впрочем, вам это было и так ясно.

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

unit MyLibr;     { имя библиотечного модуля }

interface     { секция интерфейса }

type PRec = ^TRec;

    TRec = record

    mStr : string;

    mNext : PRec;

    end;

var Stack : PRec; { Голова стека }

procedure Push(const arg : string);     { заголовок процедуры }

function Pop(var arg : string): boolean;     { заголовок функции }

{- – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – -}

implementation { секция реализации }

procedure Push(const arg : string);

{... }

end;

function Pop(var arg : string): boolean;

{... }

end;

end.

Описание типа и переменная Stack объявлены лишь один раз – в секции интерфейса, – отсюда они видны как внутри, так и вне библиотечного модуля. Повторное их объявление в секции реализации будет ошибкой. Заголовки процедур и функций в секциях интерфейса и реализации должны совпадать. Но в секции реализации разрешено не повторять списки параметров, и тогда компилятор возьмет их из секции интерфейса.

Всё, что размещено в секции интерфейса, называют списком экспорта библиотечного модуля. Таким образом, первичный модуль программы импортирует то, что экспортирует библиотечный модуль, – так налаживается связь между модулями. На рис. 146 показаны окна с файлами нашего проекта: вверху – первичный файл, внизу – файл библиотечного модуля.

Теперь все готово для компиляции и запуска нашего проекта. Перейдите в окно первичного модуля и нажмите сочетание Ctrl+F9, – оба файла будут откомпилированы, и программа запустится как обычно. Я не зря прошу перейти в окно именно первичного модуля. Если при нажатии Ctrl+F9 активным будет другое окно, компилятор выдаст обидное сообщение: «Cannot run a unit» – нельзя запустить модуль. В самом деле, модуль – это лишь часть программы, он не может быть исполнен. Компилятор же считает, что в активном окне содержится главная программа и пытается её запустить.

Чтобы не спотыкаться здесь, настройте в IDE имя первичного файла, то есть файла с главной программой, – здесь это «P_59_1». Для этого обратитесь к пункту меню Compile –> Primary file… и укажите там нужный файл (рис. 147). Теперь компилятор будет знать, с какого файла начинать компиляцию. Но и библиотечный файл «MyLibr» он тоже будет обрабатывать всякий раз, когда вы измените в нём что-то, – это очень удобно.

А если начнёте другой проект? Тогда не забудьте сменить имя первичного файла, либо сбросьте это имя через пункт меню Compile –> Clear Primary file.

Прежде чем завершить наш многофайловый проект, слегка улучшим его и покажем полные тексты первичного и библиотечного модулей.

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

Stack:= nil; { Инициализация стека пустым значением }

Когда-нибудь – в будущих проектах – вы забудете об этой важной мелочи, и наживете несколько часов головной боли. Но, если эту инициализацию перенести в модуль MyLibr, то можно впредь не вспоминать о ней. Для этого создадим в модуле ещё одну секцию – секцию инициализации. Она располагается в модуле последней и открывается ключевым словом BEGIN, вставленным перед завершающим словом END. Между этими словами записывают операторы инициализации, – все это похоже на главную программу в первичном модуле. В нашем случае секция будет такой.

unit MyLibr;

{... }

begin     { секция инициализации модуля }

Stack:= nil; { Инициализация стека }

end.

Когда сработает эта инициализация? Вы знаете, что стрельба начинается с операторов главной программы в первичном модуле «P_59_1». Это справедливо, пока не подключены библиотечные модули. С ними порядок исполнения программы слегка изменится. Первыми будут выполнены операторы в секциях инициализации подключенных модулей, причем в том порядке, в каком эти модули перечислены в списке USES (если там указано несколько модулей). И лишь затем начнёт выполняться главная программа в первичном модуле. Этот порядок гарантирует компилятор, ваше вмешательство здесь не требуется.

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

Внешний библиотечный модуль.

unit MyLibr;     { имя библиотечного модуля }

interface     { --- секция интерфейса --- }

procedure Push(const arg : string); { заголовок процедуры }

function Pop(var arg : string): boolean;     { заголовок функции }

{- – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – - – -}

implementation { --- секция реализации --- }

type PRec = ^TRec;     { Тип указатель на запись }

    TRec = record     { Тип запись для хранения связанных строк }

    mStr : string; { хранимая строка }

    mNext : PRec; { указатель на следующую запись }

    end;

var Stack : PRec; { Голова стека }

    { Процедура размещения строки в стеке }

procedure Push(const arg : string);

var p : PRec;

begin

New(p);     { создаем новую переменную-запись }

p^.mStr:= arg;     { размещаем строку }

{ размещаем в голове стека }

p^.mNext:= Stack; { указатель на предыдущую запись }

Stack:=p;     { текущая запись в голове стека }

end;

    { Процедура извлечения строки из стека }

function Pop(var arg : string): boolean;

var p : PRec;

begin

Pop:= Assigned(Stack); { Если стек не пуст, то TRUE }

{ Если стек не пуст… }

if Assigned(Stack) then begin

arg:= Stack^.mStr;     { извлекаем данные из головы стека }

p:= Stack;     { временно копируем указатель на голову }

Stack:= Stack^.mNext; { переключаем голову на следующий элемент }

Dispose(p);     { удаляем ненужный элемент }

end

end;

begin     { --- секция инициализации модуля --- }

Stack:= nil; { Инициализация стека пустым значением }

end.

Теперь в интерфейсной части модуля маячат лишь процедура Push и функция Pop. Первичный файл проекта с главной программой станет таким.

{ P_59_1 – Первичный файл проекта }

uses MyLibr;

var F : text; S : string;

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

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

Assign(F, 'P_56_1.pas'); Reset(F);

{ Пока не конец файла, читаем строки и помещаем в стек }

while not Eof(F) do begin

    Readln(F, S); Push(S);

end;

Close(F);

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

Assign(F, 'P_56_1.out'); Rewrite(F);

{ Пока стек не пуст, извлекаем и печатаем строки }

while Pop(S) do Writeln(F, S);

Close(F);

end.

Откомпилируйте проект, запустите и проверьте, жива ли распиленная «дамочка»?

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

Прежде всего, уточним структуру модуля. Из рис. 148 следует, что она схожа со структурой программы. В состав модуля, по мере необходимости, включаются те же самые персонажи: константы, типы данных, переменные, процедуры и функции. Все это может располагаться в одной из двух секций. То, что требует экспорта, выставляют напоказ в секции интерфейса, а остальное прячут в секции реализации. Что касается процедур и функций, то в секцию интерфейса выносят при необходимости лишь копии их заголовков, а сами подпрограммы поселяют в секции реализации. Константы, типы и переменные, объявленные в секции интерфейса, в секции реализации не повторяют.

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

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

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

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

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

    MyLibr.Push(S);

    while MyLibr.Pop(S) do...

Этим мы подсказали компилятору, что процедуры Push и Pop берутся из модуля MyLibr и боле ниоткуда.

Модуль, указанный в префиксе, должен упоминаться в списке USES. Но есть одно исключение – это модуль по имени SYSTEM. В этом библиотечном модуле собраны процедуры и функции, встроенные в Паскаль. Модуль SYSTEM в списке USES никогда не упоминают.

Иногда программисты называют свои процедуры и функции так же, как встроенные в модуль SYSTEM, – это не запрещено. И тогда для уточнения имен пользуются префиксами с именами библиотек, например:

    System.Writeln(F);     { стандартная процедура }

    MyModule.Writeln(S); { моя «самоделка» }

Завершая обзор структуры модуля, обратим внимание на необязательные списки импорта USES в секциях интерфейса и реализации (рис. 148). Через эти списки библиотечный модуль импортирует нужные ему элементы из других модулей. Составляя списки, следуйте простому правилу: если внешний модуль требуется только в секции реализации, упоминайте его в списке USES секции реализации, а иначе – в секции интерфейса. Упоминать модуль в обоих списках нельзя. А когда импортировать нечего, список импорта не вставляют.

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

Перед сборкой проекта все входящие в него библиотечные модули компилируются, в результате получаются файлы, расширения которых зависит от используемого компилятора. Так, для Borland Pascal файлы получат расширение TPU (это сокращение от «Turbo Pascal Unit»). Для Free Pascal это будут пары файлов с расширениями O и PPU. Модули можно компилировать как по отдельности, так и вместе со всем проектом. Рассмотрим оба случая.

Для компиляции отдельного модуля откройте его в редакторе и нажмите сочетание Alt+F9, или выберите пункт меню Compile –> Compile. Компилятор выполнит свою обычную работу по проверке ошибок и, при отсутствии таковых, сформирует библиотечный файл. На экране появится сообщение об успешной компиляции (рис. 150).

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

Модули компилируются и в ходе сборки проекта. При нажатии клавиши F9 (или при выборе в меню Compile –> Make) компилятор просматривает списки импорта USES как в главной программе, так и в модулях. Обнаружив очередной модуль, компилятор сравнивает время редакции его исходного файла (PAS) со временем создания откомпилированного файла. Если исходный файл оказался свежее откомпилированного или последний пока не существует, то модуль компилируется. Так или иначе, но перед сборкой проекта все его модули будут скомпилированы. Только после удачной компиляции первичного файла и всех связанных с ним модулей создаётся исполняемый EXE–файл.

Я уже упоминал о библиотеках, входящих в состав IDE, – они поставляются и в исходном, и в откомпилированном виде. Вы можете применять эти библиотеки наряду со своими, предварительно ознакомившись с ними по документации или по встроенной справке. Ощутить полезность фирменных библиотек можно по этой небольшой программе.

uses CRT; { Из CRT импортируются процедуры Sound, NoSound, Delay, ClrScr }

procedure Beep; { короткий гудок }

begin

    Sound(300);     { включение динамика на частоте 300 Гц }

    Delay(500);     { задержка на полсекунды }

    NoSound;     { отключение динамика }

end;

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

    ClrScr;     { очистка экрана }

    Writeln(’Привет, Мартышка!’);

    Beep;     { короткий гудок }

    Readln;

end.

Здесь на предварительно очищенный экран выводится приветствие, сопровождаемое коротким гудком. В программе используется ряд процедур из библиотеки CRT, – там собраны средства для работы с экраном. Для успешной компиляции надо указать компилятору путь к файлу «CRT.TPU». При установке среды программирования фирменные библиотеки обычно попадают в папку «…\Units» (многоточием обозначена папка установки IDE). Уточнив положение библиотек, подскажите компилятору путь к месту их проживания через пункт меню Options –> Directories… (рис. 151).

В данном примере предполагаем, что компилятор установлен в директорию «C:\BP», а библиотечные модули размещены в папке «C:\BP\UNITS».

Порой несколько разных программ используют общие для них процедуры и функции. Если при их компиляции подключить общую библиотеку, то процедуры из неё войдут в каждую из программ, увеличивая их общий «вес». Кому-то пришла в голову мысль отделить библиотеку от использующих её программ так, чтобы библиотека загружалась в память лишь единожды в момент запуска первой из применяющих её программ. И тогда, при старте последующих программ, нужные им средства оказываются уже загруженными в память. Это уменьшает общий объём оперативной памяти, потребляемой всеми работающими программами. Динамически загружаемые библиотеки (DLL) могут разрабатываться не только на Паскале, но и на других языках (например, на Си или Ассемблере).

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

• Модуль содержит все необходимое для выполнения логически связанных действий: константы, типы, переменные, процедуры и функции.

• Каждый модуль обладает именем и содержит две обязательные секции: секцию интерфейса и секцию реализации.

• Имя модуля должно совпадать с именем файла без расширения.

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

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

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

А) Разбейте на два модуля проект «P_58_1» – обход графа в ширину. Что должно быть видимо за пределами модуля? Что поместить в секцию инициализации?

Задачи на темы предыдущих глав

Б) Императорские заботы. После постройки империи (главы 57 и 58) бывшие независимые государства стали провинциями и породили новые проблемы. Для доставки туда правительственных бумаг император нанял гонцов. Чтобы доставка была по возможности скорой, гонцы следовали кратчайшими путями лишь в одном направлении – от центра к окраинам империи. Сколько гонцов для этого нужно? – вот первый вопрос. Сколько времени потребуется для достижения самых дальних окраин, если переход из провинции в провинцию отнимает сутки? – это второй вопрос. В конечных пунктах (на окраинах) перед возвращением гонцам нужен отдых, что это за окраины, где надо построить гостиницы? – это третий вопрос.

Подсказка: возьмите за основу программу «P_58_1» – обход графа в ширину – и внесите необходимые дополнения в процедуру Expand.