Ниже приводится самый маленький из полученных квадратов четного порядка:

13 3 2 16

8 10 11 5 12 6 7 9

1 15 14 4

Подтверждение к алгоритму 118

Г. Тачер (Thacher Н. С. «САСМ», 1962, № 12)

Тело процедуры magicodd было проверено на машине LGP-30 с использованием дартмутского транслятора с языка АЛГОЛ-60. Не было, найдено никаких синтаксических ошибок. Процедлфа составляла магические квадраты нечетного порядка удовлетворительно. Для порядков не выше девятого время работы процедуры было следующим (включая вывод на флексорайтер):

Порядок Время, с

3 17i

5 422

7 804

9 1285

Для ,/=3 магический квадрат имеет вид

4 3 8

9 5 1

2 7 6

Расчт етм ПЕР¥ [И]

Данный алгоритм описывает итерационную процедуру для расчета сети ПЕРТ, позволяющую использовать произвольно зшорядоченные операции и номера событий.

При исследовании сетей ПЕРТ соблюдается правило: в матрице размером пХп, строки которой означают предшествующие, а столбцы - последующие события, элемент с индексами (i,/) представляет собой время операции, требующееся для перехода от события i к событию /.

Элементарными преобразованиями в общем случае матрица превращается в верхнюю треугольную матрицу. Верхняя треугольная матрица результанта хорошо упорядочена (т. е. любое время операции в данном столбце не зависит от времен операций в столбцах, стоящих справа от данного).

Такая точная манипуляция в общем случае требует много машинного времени. При прямой оценке, не требующей ссвокупностп зле-.ментарных преобразований, можно рассчитывать сеть со значительно меньшими затратами времени.

Входные параметры: птах - общее количество операций;

i и I - номера предшествующего и посяедующегс событий соответственно;

te - соответствующее ожидаемое время каждой операции; st - время начала работы; етах - общее количество событий. Выходные параметры:

г - массив, содержащий номера событий; начальное значение мае»

сива г несущественно; es - наиболее ранний срок начала события; at - наиболее поздний срок окончания события; етах-общее количество событий.

Размерность массивов te,i,j[l:nmax], at,es,r[l:emax]. procedure pert (nmax,i,j,te,st) dataresult: (emax) result: (r,es,at); value nmax.st; real st; Integer nmax.emax; array te,es,at; integer array i,j,r; begin real a,x; integer n,e,s,t,k; procedure scan(e,t,r);

integer e,t; integer array r;

comment Задается количество событий e-1, содержащихся-в массиве г до вьшолнения процедуры scan, и номер события in или ]п, содержащийся в t. Процедура scan (scan - просмотр) просматривает массив г, определяя, нужно ли добавлять номер события к массиву г или нет. Если нужно, то номер события становится элементом Ге, а t заменяется на е. Если же не нужно, то номер события заменяется на к;

begin integer к; if е 1 then

for к:=е-1 step -1 until 1 do if t=r[k]then

begin t:=k; go to out end k; r[e]:=t; t:=e; e:=e + l; end scan; e: = l;

for n: = l step 1 until nmax do

begin scan(e,j[n],r); scan(e,i[n],r) end n;

comment Далее в зависимости от значения s будем вычислять либо время операции ate и переносить его значения в вектор наиболее ранних сроков ese, либо будем вычислять at без какого-либо переноса. В последнем случае будут получены наиболее поздние сроки окончания;

етах:=е-1; s:=l; a:=st; k:=emax;

for e:=l step 1 until emax do at[e]:=a;

for n:=l step 1 until nmax do *

if r[i[n]]>0 then begin *

if s=2 then go to b2;

x:abs(at[in]])+te[n]; •

nol: no2:

end pert;

go to if x>abs(at[]"[n]]) then nol eise no2; x: = abs(at[i[n]])-te[n]; if x<abs(at[][n]]) then at[j[n]]:=-x; end n;

for e:=l step 1 until emax do if r[e]<0 then begin if at[e] <0 then

begin r[e]:=abs(r[e]); k:=k+l; at[e]:=-abs(at[e]) end if at end else begin

if at[e]<0 then go to s3;

r[e]:=-r[e]; k:=k-1 end e; if kO then go to s2; if 8=2 then go to g2; s:=2;

for n:=l step 1 until nmax do

begin t:=i [n]; i [n] :=j [n]; j [n] :=t end n; a:=0;

for e: == 1 step 1 until emax do begin es[e]:=at[e]; r[e]:=abs(rre]); if at[e]>a then a:=at[e] end e; go to si;

for e:=l step 1 until emax do r[e]:=abs(r[e])

Свидетельство к алгоритму 1196

Алгоритм 1196 отличается от алгоритма 119а только тем, что в заголовке процедуры pert параметр г перенесен из входных в выходные параметры, а параметр етах отнесен как к входным, так и к выходным параметрам. Соответствующие изменения внесены и в пояснительный текст к процедуре pert.

Алгоритм 1196 был транслирован в системе ТА-1М на машине М-220 и дал правильные результаты, для следующих задач из работы Латтернера [28].

Задача 1. [28, с. 81]. (См. рис. 1.) Задавались параметры птах==Ь, st=0, етах=Ъ и