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

Выходные параметры:

п-1 Гп-1

а=2 л:гС08(ш) и b=x,sm{rw).

Алгоритм особенно эффективен, когда д;г==0 для всех г, больших некоторого Гь и когда хфЬ для BcexTrj.

procedure fourier(x,r,w,n) result: (a,b);

value w,n; real x,w,a,b; integer r,n; begin real t,tr,trl,cosw2;

tr:=trl:=0; cosw2:=2Xcos(w); for r:=n-1 step -1 until 0 do if xO then go to term;

go to final; ..... •

term: tr:=x; .. .

for r:=r-I step -1 until 0 do begin t:=trXcosw2+x-trl;

trl:=tr; tr:=t end r;

final: a:=tr-trlXcosw2/2;

b:=trlXsin(w) -

end fourier;

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

Алгоритм 1286 получен в результате ординарной переработки алгоритма 128 (Wells М. «САСМ», 1962, № 10).

Алгоритм 1286 был транслирован в системе ТА-1М на машине М-220 с исходными данными х=х[г]=1, ш=0.1, 0.2, 0.5, 1.0 и п-1, 10, 20, 30, 40, 50 и 51. Результаты а я b сравнивались со значениями сумм а\ и Ьь полученных по конечным формулам, приведенным в нижеследующем подтверждении. Результаты совпали до семи-восьми десятичных цифр (см. табл. 17).

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

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

Тело процедуры fourier было транслировано на вычислительной машине LGP-30 с транслятором Dartmouth SCALP. После унификации написания идентификатора «all zeros» (5- и 9-я строки в теле процедуры) программа транслирована и прошла без затруднений...

SCALP-nporpaMMa была проверена для конечных рядов:

agcosr=-"<(-;)><-/>cos(nW2)-fl;

. . sln((n-1)хи"2) . , ,о\

b = 2j """" sin(J/S sm(nt/2)

для и)=0.1, 0.2, 0.5, 1.0 и «=1, 2, ..., 51.

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



НИИ w. Для w=.\ и л=51 ошибка в величине а была 0.00109, а в величине Ъ достигала 0.00231. Поскольку .максимальное значение с для п<51 равно 10.5, а максимальное значение Ь - около 20, то наилучший результат, который может быть получен с помощью 7-разрядной арифметики системы SCALP, равен примерно 0.00001. Для сравнения заметим, что программа, суммирующая те же самые ряды с использованием-прямой рекурсии, основанной на формулах сложения синусов и косинусов, дала ошибки 0.00012 и -0.00018. Она работала, однако, только в два раза медленнее.

Таблица 17

«1

1.00000000

1.00000000

0.0000000

0.00000000

2.4050200

2.40502014

19.812778

19.8127789

-8.9394192

-8.93941929

6.6779454

6.67794553

2.1532107

2.15321073

3.1206042

3.12060424

0.73643567

0.736435677

-0.048949585

-0.0489495846

-0.48141560

-0.481415603

1.2680819

1.26808198

0.74234604

0.742346040

-0.099122798

-0.0991227993

Свидетельство к алгоритму 1296 {Е4]

Алгоритм 1296 не публикуется здесь, потому что соответствующий алгоритм 129 составлен неудовлетворительно и содержит многочисленные ошибки, указанные в соответствующем «Замечании к алгоритму 129» (Wasscher Е. J. «САСМ», 1963, № 9). Минимизацию функций можно выполнять с помощью алгоритмов 178а, 203а, 204а, 205а и 251 («САСМ», 1965, № 3).

АЛГОРИТМ 1306

Генератор перестановок с повторениями [G6]

В результате каждого обращения к процедуре perm 130 (сокращение от permutation - перестановка) образуется очередная перестановка первых п элементов вектора с. Если трактовать вектор а как число (а[1], а[2], а[п]), цифрами которого служат элементы а[1],

а[2], а[п], то каждая следующая перестановка будет числом, большим, чем предыдущее. Например, для п=4 и л:=1 перестановки будут получаться в следующей последовательности:

а[1] 1 1 1

а [2] 1

а[3] а [4]

8 -исходная перестановка

Здесь число перестановок равно 4!/(2!х2!)=6.



Наличие одинаковых элементов в массиве а уменьшает число различных перестановок. Перед первым обращением к процедуре элементы массива а должны быть расположены ib неубывающем порядке.

Целый параметр х указывает количество первых элементов массива а, взаимное расположение которых должно сохраниться во всех перестановках. Например, при п=4 и х-3 можно получить перестановки:

а [1] а [2] а [3] а [4]

1 2 3 4 - исходная перестановка 12 4 3 14 2 3 4 12 3

Здесь число перестановок равно 4!/3!=4.

Перед первым обращением к процедуре perm 130 параметр t должен иметь значение Если после выполнения процедуры perm 130 формальный параметр тоге имеет значение true, то процедура способна выдавать новые перестановки.

procedure perm 130 (n,x,t,more) dataresult: (а);

value n,x,t; real t; integer n,x; Boolean more; array a; begin real r; integer i,j,k,m,p; array b[l:n]; for i:=l step 1 until n do b[i]:=0; for i:=n step -1 until 2 do

if a[i] >t Д a[i] >a[i-1] then go to find; more:=fafse; go to exit; find: for k:=n step -1 until i do

if ark]>t A a[k]>a[i-1] then b[k]:=a[k]; for k:=n step -1 until i do

if Ь[к]>ОД ЬГк]<Ь[1] then a[k]:=b[k]; a[i]:=a[i-l];a[i-l]:=b[i]; p:=i-1; m:=n-p; for m:=m/2-0.4 vihife m>0 do for j:=p-M step 1 until n-m do begin i:=j; comp: if a[i]>a[i + m] then

begin r:=a[i + m]; a[i-bm]:=a[i]; a[i]:=r; i:=i-m; if ip-Ы then go to comp end if end j; exit: end perm 130;

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

Алгоритм 1306 получен из алгоритма 130а путем внесения в него поправок, предложенных в нижеследующем «Подтверждении и замечании к алгоритму 130а». Кроме того, глобальная переменная тоге была превращена в формальный параметр для повышения удобств пользования процедурой.

После этих поправок алгоритм 1306 был вновь транслирован и дал правильные результаты для примеров, указанных в описании алгоритма.





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