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

алгоритмы в своей повседневной работе. Приведу только два примера из многих.. Алгоритм 199а (переход от календарной даты к порядковому номеру дня п обратно) был переписан в машинном коде БЭСМ-4 и включен составной частью в подпрограмму «Календарь» в системе начисления зарплаты АН МССР. Помимо прочего, порядковый номер дня позволяет легко определять день недели (достаточно прибавить постоянное-смещение и взять остаток от деления на 7). Алгоритм 157а (аппроксимация рядами, Фурье) был с некоторой переработкой включен как подпрограмма в переданный в Госфонд алгоритмов и программ алгоритм на АЛГОЛе для расчета генерации гармоник . в нелинейных цепях, разумеется с соответствующей библиографической ссылкой на-Ваш сборник.

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

А. Е. Колесников, Кишинев, июнь 1975

ilнoю .был составлен и отлажен в системе TA-1M нижеприведенный нерекурсивный вариант алгоритма 159а. Переделка алгоритма 159а заключалась в следующем.

Введен масснвмагазин st. Для указания глубины погружения в него удалось использовать переменную i. Поскольку выход из процедуры thread возможен лишь-в два места, он определяется по величине i и погружать его в магазин ие нужно. Процедура thread ликвидирована и заменена помеченным участком программы. Так. как при рекурсии приходится передавать управление при возврате внутрь цикла по /, этот цикл расписан в явном виде. Булевский массив ликвидирован, так как для него-удалось использовать тот же магазин.

Использование ячеек магазина такое: в элемент .«[(,2] погружается величина р. Элементы st[i,l] используются для хранения в упакованном виде величин /, е, f, погружаемых в него как в магазин, а также независимо от магазина для хранения эле--ментов бывшего булевского массива. При этом величины ей/ тоже пришлось изменить. Они указывали на знак р своей четностью. Изменение, которое стоило бы внести; и в исходный алгоритм, заключается в том, чтобы они показывали непосредственно знак р, т. е. принимали значение -Ь1 и -1. Для этого f:=f+l надо заменить на f:=-/, e+f-на eXf и т. п. После этого величина / погружается в магазин как целая часть s<[i,l]; величина е+1, равная О или 2, - как десятые, а /+1 - как сотые доли десятичной дроби s?[i,l]. Независимо от этого знаки s<[/,l] заменяют бывший булевский массив.

Алгоритм отлаживался на разных примерах, в том числе на матрице с элементами Q!j j=({-f-/)2 порядка 1-5. Такая матрица вырождается при порядке, большем 3„. так как любые 4 столбца вида (!l+/) (ii+JV, ih+jV (t+lV линейно зависимы. Были получены правильные результаты, приведенные ниже.

Порядок матрицы: 1 2 3 4 5 Определитель: 4 -17 -8 0 0.

геа! procedure determinant (х,п);

value п; Integer п; array х; begin real d,p,r; integer e,i,j,f; array st[l:n,l:2];

for i: = l step 1 until n do st[i,l]: = l;

d: = 0; p:=l; e: = i: = l; thread:

if i>n then d:=d+pXe else if рфО then

begin f: = l; j: = n; loop: if st[j, 1]<0 then f:=-f else

begin st[i,l]:=-abs(st[j,l]); st[i,2]: = p; st[i,l]: = sign(st[i,l])X

(i+O.lXe+O.OlXf+0.11); p:=pxx[i,]"]; e: = eXf; i:=i+l; go to thread;

nl: i:=i-1; p:=st[i, 2]; r: = abs(st[i,l]);

]: = r; r:=(r-j)X10; e: = r-1; f:=(r-e)XlO-11; st[j,l]: = abs(st[i,l]) end;

if jO then go to loop . ..

end;

if il then go to nl;

determinant:=d end determinant;



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

Ч. Блер (Blair Ch. R. «САСМ», 1966, № 5)

Алгоритм 271 был транслирован и прошел без поправок через транслятор ALDAP для машины CDC 1601А. Сравнение среднего быстродействия, показанного в табл. 25, с быстродействием других недавно опубликованных алгоритмов демонстрирует превосходные качества алгоритма 271.

Таблица 25

Ко-чиче-стЕо эле-

Среднее время сортировки,

Алгоритм 201

Алгоритм 207

Алгоритм 245

Алгоритм 271

ментов

integer

real

mteger

real

integer

real

integer

real

20 50 100 •200 500 1000 2000 5000 10000

0,01 0,02 0,08 0,19 0,48 1,5 3,7 9,1 27 65

0,01

0,02

0,08

0,22

0,53

0,03 0,05 0,20 0,39 1,0 2,8 6,6 13 40 93

0,03 0,05 0,20 0,40

2,9 6,9

0,02 0,04 0,11 0,26 0,59 1,7 3,7 8,2 23 49

0,02

0,04

0,12

0,27

0,62

0,01 0,02 0,06 0,13 - 0,28 0,8 1,8 3,9 11 23

0,01

0,02

0,06

0,13

0,30

0.85

Замечания к алгоритму 394

Ю. Д. Красильников, Москва, апрель 1977

В текст алгоритма 394 («САСМ», 1977, № 9) нужно внести следующие исправления.

1. Строка 4 сн. от конца процедуры end decitable

i:=split {t,m,l,n,test,yes,no); должна иметь вид • .

i:=split {t.m.l ,n,test,yes,no);

2. .Строка 6 сн. от конца процедуры

for i: = l step 1 until п do, col[i]: = i;

* Данное подтверждение было прислано в форме письма редактору выпусков.

П. М. Гостев, В. И. Лаврушин, Саратов, ВЦ СГУ, январь 1976

Значение Ваших* сборников «Алгоритмы» для нас, математиков-прикладников, неоценимо. В частности, алгоритм 178а применялся нами при решении задач оптимизации параметров, электро- и радиосхем, статистической обработки экспериментальных данных, для минимизация невязки в методе пристрелки решения краевых задач обыкновенных дифференциальных уравнений. Во всех этих задачах алгоритм 178а показал себя с наилучшей стороны как по точности результатов, так и по затратам машинного времени.

Алгоритм 178а в свое время был проверен нами при поиске минимума функции

г=100-(г/-х)2-Ь(1-х)

[86], а затем на этом примере его эффективность была сравнена с эффективностью других алгоритмов минимизации функций многих переменных, имеющихся в библиотеке СП ЭВМ М-220 М [83]. В результате этих испытаний алгоритм 178а убедительно доказал свое превосходство.



должна иметь вид

for i: = l step 1 until n do col[i]: = i;

3. В описании процедуры select после строки comment Calculate dash count; сле-д)ет оператор dash :=delta :=0;. Поскольку переменная dash типа real, a delta типа integer, то этот оператор должен быть заменен двумя след)ющими: dash:=0; delta: = 0;.

4. Четырьмя строками ниже оператора, упомянутого в п. 3, записано условие

if dash<dmin V(dash = dmin Aabs(delta)<deltamin) then

при первом вычислении которого переменная deltamin не определена. Для исправления этого н)жно Б качестве первого оператора тела процедуры select добавить оператор

deltamin:=last-f irst+2;

На основе алгоритма 394 мною была написана процедура, генерирзющая по вводимой таблице решений зсловный оператор языка АЛГОЛ-60, эквивалентный этой таблице.

ПРИЛОЖЕНИЕ 2

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

Расширение шахматной программы для решения

многоходовых задач

М. и. Агеев, Москва, июнь 1974

В-вводной части к алгоритму 50CJ [49] заказывалось, что этот алгоритм может быть обобщен для решения задач на большее (чем два) число ходов. Позднее такая работа была проделана, и рез)льтаты ее приводятся здесь в виде перечня изменений к программе алгоритма 50CJ таких, которые делают ее способной решать как дв)х-, так и трехходовые задачи. Здесь же даются указания, как сделать программу способной решать задачи еще на большее (чем три) число ходов.

1. Перечень изменений к программе для решения трехходовок

В программу алгоритма 50CJ были внесены след)ющие изменения.

1. Список типа integer был дополнен новыми переменными ББ, ЧЧ, s и ss. Первые из этих переменных при решении двухходовок играют так)ю же роль,

как и переменные Б2 и 42 в алгоритме 50CJ, т. е. являются параметрами циклов, принимающими значения индексов переменных массива СПИСОК на втором ходе (белыми и черными соответственно). При решении же трехходовок эти две переменные в соответствии с их ролью могли бы быть обозначены как БЗ и 43, поскольк) тогда они являются параметрами циклов, принимающими значения индексов переменных массива СПИСОК на третьем ходе.

Указание 1. При расширении программы (по описываемому здесь методу) для решения задач на мат в два, три и четыре хода список типа integer нужно дополнять переменными БЗ, 43, ББ, ЧЧ, s, ss. Дальнейшее расширение этого списка для решения задач на мат в п ходов делается аналогично.

Переменная s - это число ходов в данной задаче. Значение этой переменной задается пользователем программой, и должно вводиться в машину перед исходными данными, определяющими заданн)ю позицию. Значение переменной ss определяется программой автоматически.

2. Размерность массивов с, q, НОМЕР, РУБЕЖ ХОДОВ, ОБРАТНО К, НА ПРОХОДЕ, определяемая числом ходов в данной задаче по формуле 2XS-I-1, была изменена на [1:7] (вместо [1:5]). Аналогично размерность массива СПИСОК, определяемая по форм)ле (2Xs-l-l)X100, где 100 - максимально возможное (предположительно) число ходов фигурами на одном уровне (полуходе), была заменена на [1:700].

3. Описание

Boolean ВОЗМОЖЕН ПАТ

было заменено на

Boolean array ВОЗМОЖЕН ПАТ [1:2]

Указание 2. При расширении программы для задач на мат в п ходов верхняя гранрща массива ВОЗМОЖЕН ПАТ должна быть равна по значению п-1.





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