Главная Промышленная автоматика. Выходные параметры: п-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
Свидетельство к алгоритму 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.0016 |