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

iot j:=l step 1 uiitii u[n] do beg n i[n]:=j; forsl (n-l,p,u,i) end endforsl;

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

Алгоритм 1376 иолучен в результате внесения в алгоритм 137а одной поправки: спецификации

array и; integer array i;

были заменены спецификацией

integer array i,u;

Алгоритм 1376 был транслирован в системе 4-70, и с его помощью был «свернут» оператор

for il:=l step 1 until 3 do for i2:=l step 1 until 4 do

x[il,i2]: -if il=i2 then 1 else 0; Для этого были описаны массивы i,u[l:2], x[l:3, 1:4] и заданы п=2, ы[1]-3, ы[2]=4, а также procedure р;

x[i[l],![2]]:=if i[l]==i[2] then 1 else 0;

В результате выполнения обращения fors\(2,p,u,i) была получена матрица

что и должно было быть.

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

Алгоритм 137а получен в результате ординарной переработки и модификации алгоритма 137 (Dahm D. М., Wells Ь\. «САСМ», 1962, № И). Модификация выразилась в замене нелокализованных массивов 1 я и формальными параметрами i и и для освобождения идентификаторов i и и от приданного им в процедуре фиксированного смысла.

АЛГОРИТМ 1386

Свертывание оператора цикла с экономией памяти {рекурсивная процедура] [02]

Процедура fors2 выполняет ту же функцию, что и процедура forsl, но более экономно расходует память мапгины. Предполагается, однако, что процедура forsl более экономична по времени.

procedure fors2(n,p,u,i);

value n; integer n; integer array i,u; procedure p; if n=0 then p else

for i[n]:==l step 1 until u[n] do fors2(n-l,p,u,i);



АЛГОРИТМ 1396

Диофантовы уравнения ах+Ьу=с [А1]

Процедура diophant находит целые жО и уО, являющиеся частным решением уравнения аУ<х+Ьху=с, где заданы целые с, Ъ, с.

Параметр т нужно задавать в пять раз большим, чем количество цифр в максимальном по модулю из чисел а, & и с. В процедуре используются глобальные метки indeterminate (не определено) и по solution (нет решения). При трансляции процедуры метки nl, л2 ,..., п7 можно не перфорировать и не вводить в машину, поскольку они служат лишь для пояснения алгоритма.

Общее решение xi, yi получается из частного по формулам хг= =xO±ixb и yi=y04iXa, где i - целое.

procedure diophant (a,b,c,m) result: (xO,yO);

value a,b,c,rn; integer a,b,c,xO,yO,m;

begin integer n,r,s,d,i,u,v; integer array q[l:m];

n:=i:=0; nl: d:=s:=abs(a); r:=abs(b); n2: for i: = i-bl while rO do begin n:=i; q[i]:=s-r;

d:=r; r:=s-rXq[i]; s: = d end i;

n3: if d=0 then

go to if c=0 then indeterminate else no solution; if c4-dxdc then go to no solution; n4: a: = a/d; b:=b/d; c:=c/d; n5: if n=6 then

begin v:=0; u: = l end esle begin v:.= 1; u:=0;

for i:=n-1 step -1 until 1 do

begin s:=v; v:=u-vXq[i]; u:=s end i

end;

n6: xO:=cXuXsign(a); yO:=:cXvXsign(b);

Алгоритм 1386 получен из алгоритма 138а в результате внесения в него такой же поправки, какая была внесена в алгоритм 137а.

Алгоритм 1386 был транслирован в системе 4-70 для такого же теста, что и алгоритм 1376, и была получена такая же матрица х, какая была получена в предыдущем алгоритме.

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

Алгоритм 138а получен в результате ординарной переработки и модификации алгоритма 138 (D ahm D. М., Wells М. «САСМ», 1962, № И). Модификация выразилась ,в замене нелокализованных массивов / и (7 и нелокализованной переменной п параметрами i, и я п соответственно для освобождения этих идентификаторов от приданного им в процедуре фиксированного смысла.



п7: c:=x0b;

хО: = хО-cXb; уО:,==уО+сХа end diophant;

nl, п2-находится общий наибольший делитель d коэффициентов а и Ъ. Если Ь=0, то rf=c; п2 - в векторе q запоминаются последовательные отношения qi алгоритма Евклида, соответствующие формуле ri-i=riqi+ri+i при 2, п; 0<Гг+1<г; го=с; Гп+1=0. Здесь

же определяется п - число делений; пЗ - случай d=0 встречается, когда а-\-Ь=0;

п4 -уравнение приводится к виду, когда а п b взаимно простые;

п5 - находятся и я v такие, что au+bv=l;

п6 - находится частное решение;

п7 - вычисляются малые значения частного решения.

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

Алгоритм 1396 является стереотипным переизданием алгоритма 139а. В «Свидетельство к алгоритму 139а» внесены необходимые исправления.

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

Алгоритм 139а получен в результате модификации, сокращения и ординарной переработки алгоритма 139 (Реек J. Е. L. «САСМ», 1962, .№ 11). Модификация делалась в соответствии с рекомендациями «Подтверждения к алгоритму 139», перевод которого публикуется ниже.

Алгоритм 1.39а был транслирован с исходными данными нижеприведенного «Подтверждения» Г; Боулдена. Получены результаты, совпадающие с указанными в табл. 20. О диофантовых уравнениях см., например, в работе А. О. Гельфонда [9].

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

Г. Боулден (В owl d ей Н. J. «САСМ», 1965, № 3)

Алгоритм 139 был переведен на расширенный АЛГОЛ фирмы «Burroughs» после исправления следующей опечатки. В строке после «if d=then» нужно заменить: «a:=a/d,» на «a:=a/d;».

Были проверены случаи, показанные в табл. 20, в которой колонки 4 и 5 содержат результаты. Эти результаты правильны, но, возможно, не очень полезны. Разумеется, оценка «полезны» в данном контексте довольно субъективна; во псяком случае пользователь всегда может получить любое решение, «полезное» для его целей. Мы решили рассматривать малое значение х как наиболее полезное и получили его, вставив перед «print (хО,уО)» операторы

с:=хОЬ; xO:i=xO-сХЬ; уО:=уО+сХа. Следующие замечания сделаны с целью улучшения программы... *

Рекомендуются четыре модификации, учтенные в алгоритме 139а. (Прим. ред.)





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.0038