Главная Промышленная автоматика. кой (если она не изменяется во внешней программе) до конца «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.0018 |