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

собности данного алгоритма позволяет лишь неограниченное увеличение массива t. Другим способом избавиться от сбоев является специальный подбор функции соответствия, далеко не всегда выражаемой аналитически.

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

Ю. Д. Красильников, Москва, МФТИ, декабрь 1976

Алгоритм 236 предназначен для упорядочения массива по возрастанию «ключа»,. т. е. целого числа, получаемого с помощью функции соответствия /. Отсюда очевидно, что в случае, когда эта функция принимает одно и то же значение для нескольких элементов исходного массива, после сортировки эти элементы окажутся собранными в группу, в которой они не обязательно будут расположены в порядке возрастания. Следовательно, для успешной сортировки массива действительных чисел элементам этого массива, имеющим различные значения, должны соответствовать различные значения ключевой функции.

«Замечание к алгоритму 236» Ротко и Васильченко относится, собственно говоря, не к самому алгоритму, а к неудачно выбранной (для взятого ими массива) функции соответствия, сопоставляющей элементам 2 и 1 одно и то же значение ключа, рав- • ное нулю.

Как cnpaBeflflnBO отмечает в своем «Подтверждении» С. В. Ратафьев, любая функция соответствия имеет конечную разрешающую способность. В общем случае, когда разность между элементами сортируемого массива может быть сколь угодно мала, а диапазон значении элементов сколь угодно велик, указать вид функции соответствия вообще не возможно.

Из вышесказанного ясно, что алгоритм 236 мало приспособлен для сортировки числовых массивов за исключением некоторых специальных случаев. Однако алгоритм с успехом может применяться в тех случаях, когда по самой природе задачи требуется ёортировка по признаку, принимающему конечное множество значений. Например, с помощью алгоритма 236 можно упорядочить список слов в алфавитном порядке по первой букве. Функция соответствия в этом случае должна по коду первой буквы слова принимать значение, равное порядковому номеру данной буквы в алфавите.

С помощью данного алгоритма можно также получить полное лексикографическое упорядочение списка слов (т. е. провести сортировку по составному ключу). Если слова содержат по т букв каждое (что всегда возможно, если считать пробел самой первой буквой алфавита, имеющей в нем нулевой номер), то для этого нужно применить алгоритм т раз. Вначале нужно упорядочить список по гп-й (последней) букве, затем по (га-1)-й букве и т. д.

Алгоритм 236 был транслирован в системе БЭСМ - АЛГОЛ и применен для сортировки массива х-(15,3,7,112,251,5) методом, аналогичным методу упорядочения слов, поскольку каждую цифру элементов этого массива можно считать порядковым номером в алфавите соответствующей буквы.

Для такой сортировки использовалась функция соответствия

f(a) = entier(a/10Tm) -10Xentier(a/10t(m+ 1)),

которая принимает значение т-й цифры целого числа а. Сортировка производилась с помощью оператора

for m: = 0,1,2 do begin matsort(x,n,10,f,y,t);

for i:=l step 1 until n do x[i]: = y[i] end;

где n=6. В результате получено y= (3,5,7,15,112,251).

Следует однако заметить, что в пояснительном тексте к алгоритму 236 имеется одна ошибка. Алгоритм вычисляет кумулятивную функцию распределения

k-i I

< [t] = 2 i 2 W = S i-i=i i=o

В заключение нужно подчеркнуть следующее.

1. Алгоритм 236 предназначен для сортировки массива по некоторому признаку с конечным множеством значений.



2. Алгоритм трудно использовать для сортировки произвольных числовых массивов *, так как множество значений всех представимых в ЭВМ действительных чисел очень велико (хотя и конечно).

3. Недоразумения при использовании алгоритма, подобные приведенным в «Замечании» Ротко и Васильченко, имеют причину в переоценке возможностей алгоритма или в неверном понимании области его применения.

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

Н. А. Дульзон, Томск, май 1977

В алгоритме 256 и в свидетельстве к нему замечены две следующие опечатки.

1. На с. 57, 19-я стр. сверху напечатано**

go to if аЬ5(!)<ер52Д abs(fl)<eps 2 then fin

Должно быть

go to if аЬз(1)<ер82д abs(fl)<epsl then fin

2. Ha c. 57, 7-Я стр. снизу напечатано

sin (nx) - cos= (n) 4-1/4=0.

Должно быть

sin {mx) - cos (их) + 1/4 = 0.

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

Пользуясь случаем присоединиться к известному мнению: тираж пособия не удовлетворяет спроса. Широкое использование отлично отработанных алгоритмов вне всякого сомнения дает большой экономический эффект: экономится рабочее время программистов и машинное время, ускоряется решение конкретных вопросов в различных отраслях, самые неискушенные начинают в своей работе обращаться к ЭВМ.

Замечания и подтверждение к алгоритму 406

и к алгоритмам 16-1006 ,

П. л. Окружной, Рязань, РРТИ, июнь 1976

Выражаю Вам** и всему авторскому коллективу большую признательность за подготовку и выпуск «Библиотеки алгоритмов». Она сыграет неоценимую роль в работе программистов. С выходом в свет «Библиотеки» отпадает необходимость «изобретать-велосипед» при решении рассмотренных в ней задач. Кроме того, она позволяет программисту ознакомиться с методами решения задач, предложенными другими авторами, и сравнить их со своими.

Мне неоднократно приходилось в своей работе обращаться к «библиотеке». Это принесло мне большую пользу, и я хотел бы, чтобы «библиотека» выиграла от такого общения, поэтому предлагаю следующее.

В алгоритме 406 используются массивы ti, te[l:n]. Для большинства практических задач размерность этих массивов может быть уменьшена, если внести в процедуру criticalpath следующие изменения.

1. В заголовок процедуры включить дополнительно еще один параметр т - общее число событий по проекту. В соответствии с этим первые две строки процедуры будут иметь вид

procedure criticalpath (m,n,i,j,dij) result: (sl,s2,fl,f2,tf,ff); value m,n; integer m,n;

2. В теле процедуры описание integer array ti,te{l:n] заменить на integer arrav ti,te\\:m\.

* Для сортировки числовых массивов лучше пользоваться другими, опубликованными позднее, более простыми в эксплуатации и в то же время быстродействующими алгоритмами 201а, 207а, 245а и 271. См., например, нижеприведенное «Подтверждение к алгоритму 271». Ч. Блера и «Подтверждение к алгоритму 245» Р. Лондона [24]. {Прим. ред.)

Эта опечатка присутствовала и в исходном алгоритме 25 («САСМ», 1960, № 11). {Прим. ред.)

*** Эти замечания были направлены в форме письма редактору выпусков данной серии.



3. в первом операторе цикла строку ti[k]:=0; te[k];=9999 заменить оператором if k<m then begin ti[k]:=0; te[k]:=9999 end

Очевидно, что для любой нетривиальной сети будет m<n, причем разность п-т будет тем больще, чем больше разветвлений в сети. Таким образом, в подавляющем большинстве практических задач достигается существенная экономия машинной памяти.

С предлагаемыми здесь изменениями алгоритм 406 был апробирован на машине «Мир 2» и дал результаты, совпадающие с ручным счетом для всех сетей, которые проходили счет (в частности, и для примеров, приведенных в «Свидетельстве к алгоритму 406»).

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

Р. М. Соколовский, Киев, сентябрь 1976

Алгоритм 50CJ [49] был запрограммирован для машины М 6000 (быстродействие 400000 оп-./с, память до 32К слов) следующим образом: процедуры ОБЗОР ХОДОВ, ВЫПОЛНЕНИЕ ХОДА, ВОЗВРАТ ХОДА и операторы с метками РОКИРОВКА и ВВОД ТАБЛИЦ были выполнены в автокоде М6000, а основная часть программы от метки ОЧИСТКА ДОСОК до метки КОНЕЦ выполнена с использованием интерпретатора языка Бейсик. Присоединенная к библиотеке интерпретатора часть программы на автокоде с таблицами занимает 4К слов памяти, а всего для выполнения программы потребуется не более 12К слов. ,

Например, обращение к процедуре ВЫПОЛНЕНИЕ ХОДА приняло на языке Бейсик следующий вид: MAKEM(N,P,M), где Римеет то же значение, что и параметр р в процедуре ВЫПОЛНЕНИЕ ХОДА, N -это массив РУБЕЖ ХОДОВ, а параметр М задается равным единице, если выполняется ход белыми, и - двум, если ход черными.

Предполагается, что интерпретатор даст в будущем возможность импровизировать в процессе игры в режиме диалога с машиной.

Были решены все задачи, приведенные в алгоритме 50CJ [24, с. 115-116], задачи Белла и много других. Несмотря на применение интерпретатора, время вьшолнения программы было не больше, чем для АЛГОЛ-программы и совпадало с приведенным в свидетельстве к алгоритму 50CJ с разбросом не более ±10%. Такая реализация алгоритма позволит значительно расширить круг его пользователей. Более перспективной реализацией в будущем представляется запись программы в автокоде микро-ЭВМ (восьмиразрядная машина с твердотельным микропроцессором).

Существенных замечаний по алгоритму 50CJ у нас нет. Вместо позиции после решения можно печатать только ключевой ход. Для предотвращения выполнения оператора с меткой ер1 [24, с. 94] при неопределенном значении переменной ОБРАТНО К1УРОВЕНЬ] нужно перед заголовком цикла по Б1 добавить оператор ОБРАТНО К[1]:=СПИСОК[3];, который будет полезен также и для организации печати ключевого хода.

Для предотвращения вьшолнения операторов с метками ер2 и ерЗ [24, с. 94] при неопределенном значении переменной НА ПРОХОДЕ [УРОВЕНЬ-1] их выполнение нужно поставить в зависимость от вьшолнения условия if УРОВЕНЬ =51 then*.

Ранее программировались на языке Бейсик алгоритмы 416 и 426. Результаты полностью совпали с приведенными в соответствующих свидетельствах [24]. Алгоритмы нашли себе применение.

Замечание к алгоритму 50CJ

М. и. Агеев, Москва, август 1976

При дальнейшей работе с алгоритмом 50CJ [49, приложение 1] в нем была обнаружена одна ошибка, которая имелась и в исходном алгоритме 50 [60] А. Белла. Эта ошибка состоит в том, что оператор с меткой ер4 [49, с. 113] нужно подставлять (без метки ер4) в процедуру ВЫПОЛНЕНИЕ ХОДА не только на место оператора

ер4: ЬЬЗ: ДОСКА ЧУЖИХ[ОТ]:=с[УРОВЕНЬ];

* Последнюю поправку можно реализовать более экономно по времени, если расширить массив НА ПРОХОДЕ до границ [0:5] и перед меткой ВВОД БЕЛЫХ ФИГУР поместить оператор НА ПРОХОДЕ [0]: = 0. (Прим. ред.)





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