Песни о Паскале - [76]

Слабо ли вам повторить подвиг контрразведчика? Воспроизведите программу, написанную Шерлоком Ивановичем, я подскажу вам только её первую строку.

{ P_38_2 – подвиг контрразведчика }

В тридевятом царстве

Это случилось на затерянном в океане материке, что носил на себе несколько царств-государств. Жители материка – те ещё скряги – тратили для названий своих стран всего по одной букве: «A», «B», «C» и так далее. И мы будем их так называть. Границами стран служили каналы, специально для того прорытые; каналы были пронумерованы. Некоторые страны выходили к океану, берега которого тоже были пронумерованы и служили границами.

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

Слово царя – закон, и вскоре спутник кружился на орбите. С высоты ясно наблюдались берега океана и каналы, составлявшие границы царств. Рис. 87 показывает то, что «увидел» спутник. Буквами обозначены названия стран, а числами – участки границ. В центре континента темным цветом выделено обширное царство «A». К нему примыкают несколько стран, отмеченные серым, – это его соседи. Страны, примыкающие к царству «A» уголками своих границ, соседями не считаются. Они и все прочие «не соседи» отмечены белым цветом, а вокруг – океан.

К сожалению, примитивная техника тех лет не смогла отправить на землю эту фотографию. Спутник передал лишь номера границ каждого государства в виде текстового файла, содержащего строчки чисел.

Рис.87 – Вид на материк из космоса

Выдернув из принтера ещё теплую распечатку файла, первый министр примчался во дворец, протянул листок монарху и покорно припал к подножию трона. Царь встрепенулся, стал разглядывать бумажку, вертеть её так и сяк, и даже на зуб попробовал. Наконец терпение государя иссякло: «Болван, – обратился он к министру, – покажи тут наших соседей. Что? Не можешь? Так проваливай с глаз долой!». И смятая распечатка угодила в лицо министра. «А ведь хотел, как лучше…» — стучало в башке убегающего премьера. «А получилось, как всегда!» — догнал его вопль взбешённого монарха.

Куда податься бедолаге? Разумеется, к самому умному, – к придворному программисту. «Выручай, браток, я тебе премию выпишу!». Инженеры, создавшие спутник, тоже не остались в стороне и растолковали программисту суть проблемы. Расправив скомканную царской рукой бумагу, Ник – так звали придворного программиста – увидел вот что.

29 21 30 31 32
17 18 19 29 28
3 4 5 20 19 18
6 7 22 21 20
8 9 25 24 23 22
10 11 26 30 23 24 25
12 13 15 27 26
14 1 2 17 16 15
16 28 32 31 27

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

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

А пока вы раздумываете, я исполню свой долг перед историей и покажу решение заморского коллеги. Ник сразу понял, что имеет дело с двумя видами множеств: множеством границ, обозначенных числами, и множеством стран, обозначенных буквами (вы помните, что страны именовались буквами?). Парень смекнул, что две страны соседствуют тогда, когда пересечение множеств их границ не пусто (это значит, что у них есть общие границы). Дальше его мысли устремились так быстро, что пальцы едва успевали тыкать по клавишам. Вот плод его труда.

{ P_38_3 – поиск стран–соседей }

type TBoundSet = set of byte;       { множество границ }
      TStateSet = set of Char;       { множество стран }

      {––––– Распечатка множества стран (символов) –––––}
procedure WriteCharSet(var aFile: text; const aSet : TStateSet);
var c : char;
begin
      for c:='A' to 'Z' do if c in aSet then Write(aFile, c:2);
      Writeln(aFile);
end;
      {––––– Ввод множества границ (чисел) –––––}
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, FileOut: text;
      R: TStateSet;       { множество соседей (результат) }
      SA, S : TBoundSet;       { границы царства «A» и прочих }
      State: char;       { буква с названием очередной страны }

begin       {––––– Главная программа –––––}
      Assign(FileIn, 'P_38_3.in'); Reset(FileIn);
      Assign(FileOut, ''); Rewrite(FileOut);
      R:= []; SA:=[]; State:='A'; { начнем с царства «A» }
      ReadSet(FileIn, SA); { из первой строки читаем границы для «A»}
      while not Eof (FileIn) do begin { цикл по странам }
      State:= Succ(State);       { буква следующей страны }
      S:=[]; ReadSet(FileIn, S); { читаем границы страны }
      { если граничит с царством «A», добавляем к результату }