Попробуйте описать действия некоторого хорошо знакомого вам лифта Проверьте свой алгоритм с помощью экспериментов (подглядывать в его электрическую схему - нечестно), а затем создайте дискретную модель этой системы и запустите ее на компьютере

► 11. [21] (Фрагментарно обновляемая память.) Следующая проблема часто возникает в задачах синхронного моделирования Система имеет п переменных V[l],. ,V[7i], и на каждом шаге моделирования новые значения некоторых из них вычисляются на основе прежних Предполагается, что вычисления выполняются "одновременно" в том смысле, что эти переменные не принимают новых значений до тех пор, пока не будут выполнены все операции присвоения. Таким образом, одновременное появление выражений

V[l] Ч-V[2] и V[2] ч-V[l]

приведет к обмену значениями V[l] и V[2], это сильно отличается от того, что обычно происходит при последовательном вычислении

Эту ситуацию, конечно же, можно промоделировать с помощью таблицы NEWV[1] , , NEWV [п]. Перед каждым шагом моделирования для этого следует установить NEWV [fc] <- V[fc] для 1 < fc < 71, затем записать все изменения величин V[fc] в NEWVCfc] и наконец установить V [fc] <- NEWV [fc], 1 < fc < тг Но этот "очень прямолинейный" метод не очень подходит по следующим причинам (1) часто п очень велико, а количество изменяемых переменных очень мало, (2) часто переменные упорядочены не в виде таблицы V[l] ,.. , V[7i] , а разбросаны в памяти самым произвольным образом, (3) этот метод не может обработать случай (что обычно является ошибкой), когда одна переменная принимает два значения на одном и том же шаге моделирования

Предполагая, что количество изменяемых на одном шаге переменных очень мало, придумайте эффективный алгоритм, который моделирует нужные действия, используя две вспомогательные таблицы NEWV[fc] и LINK[fc], 1 < fc < тг. Если возможно, алгоритм должен обнаружить ошибку в случае, если одна переменная принимает два значения на одном и том же шаге.

► 12. [22] Почему в описанной в этом разделе программе моделирования лучше использовать дважды связанные списки вместо однократно связанных или последовательных списков?

2.2.6. Массивы и ортогональные списки

Одним из простейших обобщений линейного списка является двумерный (или, в более общем случае, многомерный) массив данных. Например, рассмотрим следующую матрицу размера m х тг:

/А[1,1] А[1,2] ... А[1,п] \ А[2,1] А[2,2] ... А[2,п]

\А[т,1] А[т,2] ... A[m,n]/

В этом двумерном массиве каждый узел А [j , fc] принадлежит двум линейным спискам: списку "строки j" A[j,1],А[j ,2],...,А[j ,п] и списку "столбца fc" A[l,fc], А [2, fc],..., А [m, fc]. Такие ортогональные списки строк и столбцов и образуют двумерную структуру матрицы. Аналогичные замечания относятся и к многомерным массивам данных.

Последовательное распределение. Когда массив хранится по последовательно расположенным адресам, память обычно распределяется так, чтобы

LOC(A[J,K]) = ао+ aiJ+ а2К, (2)

где Оо, Ol и 02-константы. Рассмотрим более общий случай: предположим, что имеется четырехмерный массив элементов длиной в одно слово Q[I,J,K,L], где 0<1<2, 0<J<4, 0<К<10, 0<L<2. Память следовало бы распределить таким образом, чтобы

LOC(Q[I,J,K,L]) = ао + ail + a2J + азК + a4L. (3)

Это значит, что изменение I, J, К или L сразу же приведет к вычислению изменения адреса элемента Q[I,J,K,L]. Наиболее естественный (и наиболее распространенный) способ распределения памяти заключается в упорядочении элементов согласно лексикографическому порядку их индексов (упр. 1.2.1-15(d)), который иногда называют "упорядочение по строкам":

Q[0,0,0,0], Q[0,0,0,1], Q[0,0,0,2], Q[0,0,1,0], Q[0,0,1,1],

Q[0,0,10,2], Q[0.1,0,0], Q[0,4,10,2], Q[l.0,0,0],

Q[2,4,10,2].

Нетрудно видеть, что этот порядок удовлетворяет требованиям (3) и может быть выражен так:

LOC(Q [I, J,К, L]) = LOC (Q [0,0,0,0]) + 1651 + 33J -Ь ЗК -Ь L. (4)

Вообще, fc-мерный массив с элементами A[Ii .Хг.... ,1л] длиной с слов при

0<Ii<6fi, О < I2 < cf2, 0<Ifc<6ffc

может храниться в памяти в виде

L0C(A[Ii,l2 Ifc])

= L0C(A[0,0,...,0])-bc(6f2-bl)...(6ffc + l)Ii+--- + c(4-bl)Ifc i-bcIfc

= LOC(A[0,0,...,0])+ Y rlr, (5)

l<r<fc

ar = c П {d, + 1). (6)

r<s<k

Для доказательства этой формулы заметим, что Ог - это объем памяти, необходимой для хранения части массива A[Ii, ... , Ir, Jr+i. • • • .Jfc] j где Ii,..., Ir -константы, a Jr+i,...,Jfc изменяются для всех О < Jr+i < dr+i,..-, О < J/t < dk-Следовательно, по определению лексикографического порядка адрес A[Ii,..., It] будет изменяться точно на эту величину при изменении Ir на единицу.

Формулы (5) и (6) соответствуют значению числа Ii I2 . •. Ifc в системе счисления со смешанным основанием (mixed-radix number system). Например, для массива TIME[W,D,H,M,S] cO<W<4, 0<D<7, 0<Н<24, 0<M<60и0<S<60aд-pec элемента TIME[W,D,H,M,S] будет равен адресу TIME [0,0,0,0,0] плюс величина "W недель -Ь D дней -Ь Н часов + М минут + S секунд" в секундах. Конечно, массив с

2 419 200 элементами может понадобиться только для очень экзотического приложения.

Традиционный метод хранения массивов обычно подходит только для массива с полностью прямоугольной структурой, в которой все элементы A[Ii,l2> ••• имеют индексы в независимых диапазонах /i < Ii < ui, /г < I2 < "2, fc < Ifc < Wfc- В упр. 2 показано, как можно адаптировать формулы (5) и (6), когда нижние границы {li,h,---,h) не равны (0,0,...,0).

Однако во многих случаях массив не является прямоугольным. Чаще всего он представляет собой треугольную матрицу, в которой хранятся только элементы kij,k], например, для О <к < j <п:

/АЕО.О] \

А [1,0] А [1,1]

\А[п,0] А[п,1] ... А[п,п]/

Как правило, известно, что все остальные элементы матрицы равны нулю или A[j,fc] = A[fc,j], так что достаточно хранить в памяти всего лишь около половины всех элементов матрицы. Для хранения нижней треугольной матрицы (7) в (п -Ь 1)(п -Ь 2) последовательных позициях памяти следует отказаться от линейного распределения памяти (2) и использовать распределение в виде

LOC(A[J,K]) =ao-b/i(J)-ЬЛСК), (8)

где fl и /2 - функции одной переменной. (Константа ао может быть включена в функцию fl или /2.) Если способ адресации имеет вид (8), доступ к произвольному элементу А [ j, fc] можно достаточно легко осуществить с помощью двух (очень коротких) вспомогательных таблиц со значениями /1 и /2. К тому же эти функции потребуется вычислить только один раз.

Причем лексикографический порядок индексов массива (7) удовлетворяет условию (8), а для элементов длиной в одно слово получим простую формулу

LOC (А [J, К] ) = LOC (А [0,0] ) + + К.

Однако существует более эффективный способ хранения треугольных матриц одного и того же размера. Предположим, что нужно сохранить две матрицы А [ j, fc] и B[j,fc], где Q < к < i < п. Тогда их можно свести к одной матрице C[j,fc], где О < j <n,Q < к <п + 1, используя условие

A[j.fc] =C[j,fc], B[j,fc] =C[fc,i + l]. (10)

Таким образом, получим

/С[0,0] С[0,1] С[0,2] ...С[0,п-Ь1]\ /А[0,0] В[0,0] В[1,0] ...В[п,0]\

С[1,0] С[1,1] С[1,2] ...С[1,п+1]

А[1,0] А[1,1] В[1,1] ...В[п,1]

\С[п,0] С[п,1] С[п,2] ...С[п,п-Ы]/ \А[п,0] А[п,1] А[п,2] ...В[п,п]/

Так, две треугольные матрицы могут быть компактно упакованы в [п + \){п + 2) ячейках памяти с линейной адресацией типа (2).