АЛГОРИТМ 656

Поиск элемента в сортируемом массиве {рекурсивная процедура) [Ml]

Процедура find {find - поиск) присваивает переменной a[k] такое значение, которое она имела бы, если бы массив а[т:п] был рассортирован. После выполнения процедуры find массив с будет частично рассортирован и последующие обращения к процедуре find будут выполняться быстрее, чем первое, procedure find (m,n,k) dataresult: (a);

value m,n,k; integer m,n,k; array a; if m<n then begin integer i,j; partition (m,n,a,i,j); if ki then find(m,i,k,a) else if k j then find(j,n,k,a) end find;

Свидетельство к алгоритму 656

Алгоритм 656 получен в результате модификации алгоритма 65а для повышения удобств пользования им. В первой строке описания процедуры find был изменен порядок следования параметров, соответственно этому изменились и два рекурсивных обращения к процедуре find в ее собственном теле. Кроме того, в связи с изменением порядка следования параметров процедуры partition алгоритма 636 изменилось и обращение к ней из тела процедуры find.

Алгоритм 656 был транслирован в системе БЭСМ-АЛГОЛ машины БЭСМ-6 совместно с процедурой partition алгоритма 636, в которой оператор p:=random{m,n) был заменен (для упрощения отладки) на оператор р:=\{т+п) 12. Алгоритм дал правильные результаты при-задании параметров т=1, п=б, а-{4, 1, 3, 5, 2) и k=A, 2, 3, 4, 5. После обращения к процедуре find для первых трех значений к маосив а имел вид (1, 2, 3, 5, 4), а для k-4 и 5 - вид (1, 2, 3, 4, 5), т. е., элемент alk] действительно находился на месте k в массиве а.

Свидетельство к алгоритму 65а

Алгоритм 65а получен в результате сокращения .и ординарной переработки процедуры, приведенной в нижеследующем «Подтверждении» Б. Рандела и Л. Рассела («САСМ», 1963, №8). Данный алгоритм можно использовать только на трансляторах, допускающих рекурсивные процедуры.

Подтверждение к алгоритмам 63, 64 и 65 Дж. Хилмор (Н i И m о г е J. S. «САСМ», 1962, № 8) Тело процедуры find было исправлено на ... *

Эти три процедуры были затем успешно проверены на вычислительной машине National Elliott 803, использующей транслятор с языка Elliott ALGOL.

Предлагается нотравленный вариант алгоритма 65. (Прим. ред.)

Авторская оценка 7з(я-т)1п{п-т) для числа парных перестановок, необходимого для сортировки случайной последовательности, была найдена правильной. Однако число сравнений оказалось в общем меньше чем 2(п-m)tn{n-т) даже без модификации, указанной ниже.

Эффективность процедуры quicksort была повышена путем изменения ее тела на * begin integer i,j;

if m<;n-1 then

begin partition(m,n,a,i,j); quicksort (m,i,a); quicksort (j,n,a) end else

if m=n-1 then

begin if a[n]<a[ni] then exchange(a[m],a[n]) end end quicksort;

Подтверждение к алгоритмам 63, 64 и 65

Б. Рандел и Л. Дж. Рассел (R а п d е 11 В., R и s s е 11 L. J. «САСМ», 1963, № 8) Алгоритмы 63, 64 и 65 были проверены с использованием транслятора Pegasus ALGOL 60, разработанного в Англии в г. Хатфилде компанией Havilland Aircraft.

В алгоритмах 63 и 64 не потребовалось никаких изменений, они работали удовлетворительно ... **

АЛГОРИТМ 666

Обращение симметричной матрицы методом квадратных корней [F1]

Процедура inversbb обращает симметричную матрицу ci[l:n, Un], для которой ведущие Миноры не нулевые, с помощью упрощенного варианта метода квадратных корней. Эта процедура заменяет n(n+!l)/2 диагональных и наддиатональных элементов матрицы а элементами матрицы g~*, оставляя поддиагональные элементы неизменными.

Преимущества этого метода состоят в том, что требуется только п рабочих ячеек, не нужно никакой единичной матрицы, не извлекаются никакие квадратные корни, выполняется только п делений. Когда п возрастает, то число умножений приближается к Если gI1,1]=0, то осуществляется выход к нелокализованной метке signat66. (Подробное описание метода см. [4, с. 177-179].) procedure invers66(n) dataresult:(a);

value n; integer n; array a; begin real y,p; integer i,j,k; array v[l:n-1]; for k: = l step 1 until n do

begin if all,l]==0 then go to signal66; p: = l/a[l,l];

for i: = 2 step 1 until n do v[i-l]: = a[l,i];

* Для удобства пользования нижеследующие операторы модифицированы в соответствии с алгоритмами 636 и 656. (Прим. ред.)

** Далее указываются некоторые поправки и дается новый вариант алгоритма 65, использованный для алгоритма 65а. (Прим. ред.)

for i:=l step I until n-1 do begin a[i,n]:=y:=-vfi]Xp; for j:=i step 1 until n-1 do a[i,j]: = a[i+l,j + l]-j-vn]Xy end i; a[n,n]:=-p end k;

for i:=.l step 1 until n do

for j: = i step 1 until n do a[i,j]:=-a[i,j] end invers66;

Свидетельство к алгоритму 666

Алгоритм 666 получен из алгоритма 66а в результате одного очевидного усовершенствования. Ради экономии машинного времени заголовок цикла

for к:=0 step 1 until n-1 do

был заменен заголовком

for к: = 1 step 1 until n do

Алгоритм 66a был подтвержден также и расчетами на машинах БЭСМ-6 (см. «Подтверждение к алгоритмам 4а, 7а,..., 238а» Л. С. Кривонос и 3. А. Шиншиновой [38]) и Урал-2 (см. «Подтверждение к алгоритмам 1а, 7а,..., 143а» и И. Р. Гитмана [25]).

Свидетельство к алгоритму 66а

Алгоритм 66а получен в результате исправления и ординарной переработки алгоритма 66 (Caffrey J. «САСМ», 1961, № 7). Проведено контрольное решение на трансляторе ТА-1. Получены хорошие результаты, которые указаны в «Свидетельстве к алгоритму 58а».

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

Б. Рандел, К. Г. Бройден (Randell В., Broyden С. G. «САСМ», 1962, № 1) Эта процедура была транслирована с использованием транслятора DEUCE-ALGOL. Потребовались следующие исправления... *

Программа, транслированная с использованием 20-разрядной мантиссы с плавающей запятой, была проверена в применении к матрице Вильсона

5 7 6 5 7 10 8 7

6 8 10 9 5 7 9 10

и дала результаты

67.9982 -40,9991 -16.9995 9.9997 -40.9991 24.9995 9.9997 -5.9998 -16.9995 9.9997 4.9998 -2.9999 9.9997 -5.9998 -2.9999 1.9999

(симметричная матрица дополнена программой вывода).

* Указьшается одна поправка к алгоритму 66, учтевная в алгоритме 66а. В данном и следующем переводах «Подтверждений» -используются обозначения, принятые в алгоритме 66а. (Прим. ред.)