В книге приводятся описания алгоритмов по широкому кругу вопросов прикладной математики и программирования на алгоритмическом языке АЛГОЛ-60, публиковавшихся первоначально в журнале «Coniniuiiicatioiis of the АСМ» (США) под номерами 51-100, переведенных на русский язык, исправленных, улучшенных и отлаженных на ЭВМ авторами данного выпуска. Каждый алгоритм снабжен подтверждениями и свидетельствами, содержащими примеры применения, результаты отладки, критические оценки и сравнительные характеристики публикуемых алгоритмов.

В качестве приложений к выпуску приводится алгоритм «Как программировать игру в шахматы», а также замечания и подтверждения к ранее опубликованным алгоритмам, среди которых особое место занимает статья Р. Лондона «Доказательство алгоритмов - новый вид подтверждения».

Книга является настольной для специалистов различного уровня, связанных с работами на ЭВМ.

Рис. 7, табл. 32, библ. 77 назв.

Члены редакционного совета:

Трапезников В. А. (председатель), Челюсткин А. Б. (зам. председателя), Бусленко Н. П., Виленкин С. Я-, Воронов А. А., Гаазе-Рапопорт М. Г., Дудников Е. Г., Ицкович Э. Л., Копеловйч А. П., Круг Г. К-, Мамиконов О. Г., Осколков И. И., Пархоменко П. П., Пинскер М. С, Плискин Л. Г., Поспелов Г. С, Райбман Н. С, Самойленко С. И., Таль А. Д., Флеейшман Б. С, Хургин Я. И., Цыпкин Я. 3., Якобсон Б. М.

Редакция кибернетической литературы

30502-021 046(01)-76

© Издательство «Советское радио», 1976 г.

Предисловие

Данный выпуск служит продолжением серии, начатой выпуском «Библиотека алгоритмов 16-бОб» [38], и включает в себя алгоритмы, полученные в результате дальнейшего совершенствования алгоритмов выпуска «Алгоритмы (51-100)» [23]. Последний содержал алгоритмы 51а-ЮОа, являющиеся, в свою очередь, результатом переработки соответствующих алгоритмов журнала «Communications of the АСМ» (САСМ) [17]. К каждому из алгоритмов данного выпуска Прилагаются соответствующие «Подтверждения» и «Замечания» как из вышеуказанного журнала, так и советских пользователей алгоритмами, а также «Свидетельства», составленные авторами выпуска. Алгоритмы публикуются здесь на эталонном алгоритмическом языке АЛГОЛ-60 [21], описываемом во многих учебниках [13-16, 27, 28]. Там, где это возможно без заметного ухудшения алгоритмов, они предварительно лере-водились авторами выпуска на сокращенный АЛГОЛ-60 [12] с некоторыми его расширениями в сторону полного АЛГОЛа [допускались: 1) возведение целых чисел в любую целую степень, 2) различение идентификаторов по всем содержащимся в них символам, 3) операция и 4) условное именующее выражение]. В частности, все алгоритмы здесь записаны с использованием только строчных букв латинского алфавита *. Прописные буквы используются только в алгоритме 50CJ (см. приложение 1) для идентификаторов, являющихся русскими словами.

В свидетельствах к алгоритмам указывается оригинал переработанного алгоритма, перечисляются виды работ, проведенных над алгоритмом, внесенные в него изменения и приводятся результаты контрольного решения по данному алгоритму. Работы, которые проводились над всеми алгоритмами, для краткости называются здесь «ординарной переработкой». К ней относится перевод на русский язык комментариев, подтверждений и замечаний, придание алгоритму наглядной, удобочитаемой формы путем применения однотипной ступенчатой записи по правилам, опубликованным в статье [22], и использования идентификаторов интернационального характера, а также перевод алгорит-;мов на сокращенный АЛГОЛ. Все другие модификации алгоритмов {например, внесение в них исправлений, сокращение их записи, оптимизация и т. д.), а также отличия используемых языковых средств от сокращенного АЛГОЛа [12] и те случаи, когда алгоритмы составлялись заново, оговариваются в свидетельствах особо.

Предыдущий выпуск сопровождался тематическим указателем алгоритмов, появившихся в советской и зарубежной печати к моменту составления выпуска. Алгоритмы в этом тематическом указателе груп-

• Из типографских соображений эти латинские йуквы набраны в тексте курсивом, а в описаниях процедур-прямым шрифтом. Например, в алгоритме 516 adjust и adjust означают один и тот же идентификатор. (Прим. ред.)

пиравались в соответствии с классификацией, .принятой в журналам «САСМ». Названия алгоритмов в выпусках сопровождаются индекса-» ми, соответствующими этой классификации. Например, в заголовке «Алгоритм 726. Генератор композиций [А1]» индекс [А1] указывает, что-алгоритм 726 относится к классу А1 («Арифметика. Теория чисел»).. Расшифровка таких индексов имеется в вышеупомянутом тематическом указателе.

В выпусках серии «Библиотека алгоритмов» номера алгоритмов! снабжаются буквой «б» (например, «Алгоритм 726») для отличия их как от исходных, так И от алгоритмов, издававшихся в предыдущей серии [2, 23-26]. В ссылках на источники аббревиатура «САСМ» означает журнал «Communications of the АСМ» [17]. В переводах «Подтверждений» и «Замечаний» перечень поправок .к алгоритмам обычно» опускается, поскольку эти поправки, как правило, уже внесены в переработанный алгоритм. В соответствующих .местах ставятся многоточия-и делаются сноски. Контрольные решения по алгоритмам проводились с использованием транслятора * ТА-1М [10, 45] на машинах М-220 [44] и транслятора БЭСМ-АЛГОЛ [29, 45] на машине БЭСМ-6 (быстродействие- миллион операций в секунду, память-.свыше 32000 ячеек, длина ма.нтиссы чисел - 10 цифр).

В серии «Библиотека алгоритмов» будут публиковаться только-отлаженные алгоритмы. Однако, учитывая известный каждому программисту факт, что никакая отладка и даже многолетнее использование не гарантируют абсолютной безошибочности программ, а также и то, что пределов совершенствования алгоритмов практически не существует, авторы вынуока обращаются ко всем читателям и пользователям С просьбой присылать даои замечания и подтверждения в адрес издательства (для Агеева М. И.). Публикация таких замечаний в последующих выпусках будет продолжена, так же как это сделано-в данном выпуске (см. приложение 2).

Работа по подготовке к изданию алгоритмов предыдущей серии [2, 23-26] была начата В соответствии с объявлением, регулярно (начиная с мая 1964 г.) публиковавшемся в разделе «Алгоритмы» журнала «САСМ»: «Репродукция алгоритмов данного раздела разрешаете» безвозмездно. Если репродукция делалась с целью публикации, то необходима ссылка на автора алгоритма и на выпуск «САСМ», в котором опубликован алгоритм». Первый выпуск «Алгоритмы (1-50)» сразу же после публикации был послан на отзыв редактору раздела «Алгоритмы» журнала «САСМ» президенту АСМ проф. Г. Форсайту и получил полное его одобрение.

Появление в печати предыдущей серии [2, 23-26] было .встречено горячим одобрением не только подавляющего большинства читателей и пользователей, но и самих авторов и издателей исходных алгоритмов (см., например, «Замечания» Г. Форсайта, Дж. Вараха и Г. Цилке в приложении 1 к выпуску «Библиотека алгоритмов 16-506»). Тем не менее, так же как и ib предыдущем выпуске, здесь подчеркивается,, что коллектив сотрудников, выполнявших одновременно работу составителей, переводчиков, переработ1чико1в и отладчиков алгоритмов и собирательно именуемых здесь авторами выпуска, на авторство На отдельные алгоритмы отнюдь не претендует, за исключением разве толь-

* В дальнейшем здесь наряду со словом «транслятор» будут употребляться слов© «транслирующая система» или просто «система». (Прим. ред.)