Читать онлайн «Алгоритмы (51-100)»

АКАДЕМИЯ НАУК СССР ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ОБЩИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ ВЫПУСК 3 М. И. АГЕЕВ, В. П. АЛИК, Л. В. МАЛЮК, Ю. И. МАРКОВ АЛГОРИТМЫ (51-100) Под общей редакцией М. И. АГЕЕВА V^ahooc >АНО0СР ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР АН СССР МОСКВА - 1966 М. И. АГЕЕВ, В. П. АЛИК Л. В. МАЛЮК, Ю. И. МАРКОВ Алгоритмы (51-100) Утверждено к печати Ученым советом Вычислительного центра АН СССР * Редактор 11. А. Орлов а. Техн,редактор А. И. Коркина Корректор ТМ. Шведова 1~Св2С7. Подписано в печать 6/14-66 г. iopiam бумаги 60 х 90%/16 Уч. ~и. 1д. л. 5,84. Усл. -печ. л. 6,75. Заказ 53. Тирах 7300 экз. Цена 41 коп. Отпечатано на ротапринтах в Вычислительном центре АН СССР Москва, В-333, улица Вавилова, дом/Х 28 ПРЕДИСЛОВИЕ Данный выпуск содержит алгоритмы, полученные в результате переработки алгоритмов с номерами 51-100, публиковавшихся ранее в журнале "Communications of the ACM", К каждому алгоритму прилагаются переводы соответствующих подтверждений и замечаний, а также свидетельства, составленные авторами выпусков. Алгоритмы публикуются на эталонном алгоритмическом языке АЛГОЛ—60 [11,13,14,15,16], а там, где это возможно без заметного ухудшения алгоритма, — на сокращенном АЛГОЛе—60 [12], с некоторыми его расширениями [допускаются: 1) возведение целых чисел в любую целую степень, 2) различение идентификаторов первыми 12 символами, 3) операция +]• В свидетельствах к алгоритмам указывается прототип переработанного алгоритма, перечисляются виды работ, произведенных над алгоритмом, внесенные в него изменения и приводятся результаты контрольного решения (если оно делалось) по данному алгоритму. При этом для краткости употребляется термин "ординарная переработка", под которой понимается перевод текстового материала, придание алгоритму более наглядной, удобочитаемой формы, приведение его к форме, удобной для перфорации непосредственно со страниц данного выпуска и использования алгоритма в большинстве из ныне работающих в Советском Союзе трансляторов. Все другие модификации алгоритмов (например, внесение в них исправлений, сокращение, оптимизация и т. д. ), а также отличия используемых языковых средств от сокращенного АЛГОЛа—60 и те случаи, когда алгоритм составлялся заново, оговариваются в свидетельствах особо. Алгоритмы с номерами 81,82, 83,95,97 публикуются здесь по существу без изменении, что также оговаривается в свидетельствах. -з- Для отличия от исходных номера переработанных алгоритмов снабжаются буквой "а" (например, алгоритм 51а). После названий алгоритмов в квадратных скобках указываются индексы разделов классификации в соответствии с приложением к данному выпуску). В ссылках на источник аббревиатура "САСМ" означает журнал "Communications of the ACM", [17]. Поскольку поправки к алгоритмам, указываемые в соответствующих "Замечаниях" и "Подтверждениях", вносятся в пергзрабатываемые алгоритмы, то тексты поправок в переводах опускаются, вместо них ставятся многоточия и делаются сноски. Контрольные решения по алгоритмам проводились с использованием транслятора ТА—1 (в опубликованном описании [10] именуемого "программирующей программой") на вычислительной машине М—20, в которой числа представляются с плавающей запятой и 36—разрядной мантиссой.