Главная Промышленная автоматика.

кой (если она не изменяется во внешней программе) до конца «1-го обращения к процедуре perm. К этому моменту массив х восстанавливается в первоначальном порядке, а primWb принимает значение true.

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

procedure perm(п)dataresult: (х);

value п; integer п; array х; tsegin real t; integer k,q; own integer array p,d[2:n];

if prim 115 then

begin priml 15:=false; •. •

for k:==2 step I until n do

begin p[k]:=0; d[k]:=l end к end priml 15; k:=0;

index:p[n]:=q:=p[n]+d[n];

if q=n then

begin d[n]:=-1; go to iter end;

if q =50 then go to trans;

d[n]:=l; к:==к-Ы; iter: if n>2 then

begin n:=n-1; go to index end iter;

q:=l; priml 15:= true; •

irans: q:=q-fk;t:=x[q];

xrq]:-x[q+l];x[q + l]:=t end perm;

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

Алгоритм 1156 является стереотипным переизданием алгоритма 115а.

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

Алагоритм 115а получен в результате ординарной переработки алгоритма 115 (Trotter Н. F. «САСМ», 1962, № 8). При работе с транслятором, который не позволяет использовать собственные массивы, в процедуре perm идентификаторы р и d нужно ввести в список формальных параметров или сделать нелокализованными.

С помощью транслятора ТА-1 после 24=4! обращений к процедуре perm были получены всевозможные перестановки четырех чисел

2468 6248 8642 8426

4268 2648 8624 8462

4628 2684 8264 4862

4682 6 284 2864 4826

6482 6824 2846 4286



Г. Шрак (Schrack G. F. «САСМ», 1962, № 10)

Алгоритм 115 был переведен на язык ФОРТРАН для машины IBM 1620 и работал удовлетворительно. Был проведен хронометраж, для тех же условий, что и в алгоритмах 71 и 86.

Алгоритм 115 действительно самый быстродействующий из встречавшихся до сих пор алгоритмов. Для «=8 алгоритм 115 на 25% быстрее алгоритма 86 (989 с против 1316 с). Значения г„ были*:

rt 6 7 8 г„ 0.92 0.95 0.98

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

Э. Филипс (Phillips Е. S. «САСМ», 1962, № 12)

Алгоритм 115 был переведен на язык ФОРТРАН для машины CDC 160А и работал удовлетворительно. Для п=8 этот метод требует 2822 с. Для сравнения был транслирован алгоритм 86 на той же машине, и он потребовал 3710 с против 1316 с при работе на IBM 1620.

АЛГОРИТМ 1166

Деление одного комплексного числа на другое [Д2]

Процедура complexdiv (complex - комплексный, division - деление) вычисляет комплексное частное от деления а+Ы на c+di. В используемом здесь методе приняты меры к устранению переполнения или возникновения машинного нуля. Такие явления могли бы иметь место при возведении в квадрат компонент знаменателя, если бы использовался обычный метод. Если c=zd-0, осуществляется выход к глобальной метке signalll6.

procedure complexdiv (a,b,c,d) result: (e,f);

value a,b,c,d; real a,b,c,d,e,f; begin real r,den;

if c=0 Л d=0 then go to signall 16; if abs(c)>abs(d) then

begin r:=d/c; den:=c-f rXd;

e:=(a-f bXr) /den; f:=(b-aXr) /den end else

begin r:=c/d; den:=d--r Xc;

e:=(axr-t-b)/den; f:==(bXr-a)/den end

end complexdiv;

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

Алгоритм 1166 является стереотипным переизданием алгоритма 116а, если не считать более подробной записи названия алгоритма..

* В «Подтверждении к алгоритму 71» (Реек J. Е. К., Schrack G. F. «САСМ»,. 1962 № 4) величина /•„ была определена как .„ = f„/n„ i, где tn - время, требующееся для получения всех перестановок вектора с п компонентами. (Прим. red.)



Магический квэйрат ч©?и®г® ттрвщш [Z]

Процедура magiceven {magic - магический, even - четный) по данному размеру п (чисел) стороны квадрата определяет числа от 1 до и размещает их в лексикографическом порядке в массиве xllmXn] (где п--четное число, не меньшее четырех) так, чтобы они образовали «магический квадрат».

В магическом квадрате суммы чисел любой строки, любого столбца и любой диагонали равны между собой. Использованный здесь метод описан в работе М. Крайчкка [19i].

procedure magiceven (n) result: (x);

value n; integer n; mteger array x; begin integer a,b,n2,nn,i; Boolean p,q,r; procedure alpha (p,q,a,h);

value p,q,a,h; integer p,q,a; Boolean h; for i:=p step 1 until q do begin h:=~I h;

x[{,a],:=if h then nn-aXn--l--n-i else aXn-n-fi end alpha; procedure beta (p,q,a,h); value p,q,a,h; integer p,q,a; Boolean h; for i:=p step 1 until q do begin h:=~h;

x[i,a]:= if h then aXn-f 1-i else nn-aXn-bi end beta; procedure gamma (p,q,a,h); value p,q,a,h; integer p,q,a; Boolean h; for !:=p step 1 until q do begin h:= Ih;

x[i,a]:=: if h then aXn--l-i else nn-aXn-bn-i + l end gamma; start: n2:=n-2; nn: = nXn;

Алгоритм 116а получен в результате ординарной переработки и некоторой модификации алгоритма 116 (Smith R. L. «САСМ», 1862, Ш 8). Модификация состояла в обеспечении выхода к глобальной метке signatl\6 при делении на нуль.

С помощью транслятора ТА-1 были произведены деления нескольких комплексных чисел. Из полученных результатов ниже приводятся следующие:

1 + 2г 1 + 2i 14- 2i

j = 0.44--0.08i; 4 =0.4-f 0.2»; 3 = - 0.2-f 0.4,-.

тЙЬ" = -2--": -3-1t =-0.44-0.08/; -I = 0.2-f 0.4*. Эти результаты легко проверяются вручную.





0 1 2 3 4 5 [6] 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

0.0036