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

Деревенец Олег Виленович

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

{ 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», добавляем к результату }

if S*SA <> [] then R:= R + [State];

end;

WriteCharSet(FileOut, R); Readln; { вывод результата }

Close(FileIn); Close(FileOut);

end.

Программа Ника вычислила, что царство «A» соседствует с царствами «B», «D», «F», «I». Со временем проверка на местности это подтвердила.

Царь щедро наградил программиста, но история на этом не закончилась. О великом научном успехе скоро знала и последняя собака на материке. Но больше других этот успех заинтересовал купцов, плативших пошлины при пересечении границ. Они явились к Нику с предложением, от которого тот не смог отказаться. Хотите продолжения сказки? – оно ждёт вас в главах 49, 57 и 58.