• В Паскале есть средства для работы с регистрами – это логические операции и сдвиги. Они трактуют числа как массивы битов.

А слабо?

А) Напишите программу для исследования операций сдвига (подобную программе «P_48_1»).

Б) Наряду с рассмотренными здесь обычными сдвигами, в процессорах заложены операции циклического (кругового) сдвига. При таком сдвиге (рис. 111) выдвигаемый бит не теряется, а попадает соответственно в младший бит (при сдвиге влево) или в старший бит (при сдвиге вправо).

Рис.111 – Циклический сдвиг влево

В Паскале нет операций циклического сдвига. Напишите функции для циклического сдвига слова влево и вправо. Подсказка: перед сдвигом каждого бита проверяйте состояние теряемого бита, а затем восстанавливайте его в младшем или старшем разряде.

Глава 49

Сложные массивы

Элементом массива может быть любой тип данных, и даже другой массив. Разбор следующих задач убедит вас в этом.

На поклон к Науке

Вернемся в тридевятое царство, история которого ещё далека от завершения. В 38-й главе мы узнали, что для исследования материка запустили спутник, передавший на землю номера границ тамошних стран. А программа, сработанная придворным программистом Ником, нашла по этим данным соседей царства А.

Молва о научном успехе дошла до купцов, и заронила в их души зерно надежды. Душевной болью торгашей были немалые пошлины, вносимые при каждом пересечении границы. Нет, купцы не надеялись избавиться от пошлин. Но, прежде чем везти товар, они желали знать о количестве пересекаемых границ, дабы прикинуть, стоит ли овчинка выделки? Раньше купцы ехали, куда глаза глядят и часто терпели убытки. Но теперь – иное дело, – можно предвидеть расходы. Требовалась лишь программа для определения минимального количества пересекаемых границ. С этой просьбой купцы и подкатили к придворному программисту, обещая весомое вознаграждение.

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

Имперское строительство

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

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

      TStates = array ['A'..'Z'] of TBoundSet;

      { Процедура чтения множества чисел (границ) из строки файла }