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

if x=l then go to signal62. 4. В двух местах произведение 3i было заменено на 3Xt.

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

Дж. Р. Херндон (Herndon J. ,R. «САСМ», 1961, № 12)

При просмотре алгоритма 62 были найдены ошибки... *

Эта процедура получена из стандартной рекуррентной формулы

(/г+т-l)Q"„ , = (2/z-O.vQ. -{n--m)Q!"„.

Обратим и умножим на {п-\-т-l)Q"n ,. Тогда

{2n - l)x - (n-m)Qmn/Qm„ , «-» - (2„ i) - (и -/те) и"»"

Анализ показывает, что для большого п эта бесконечная непрерывная дробь должна быть вычислена примерно до восьми членов для получения восьми разрядов точности, если последний член оценивается, асимптотическим значением, получаемым следующим образом:

Выбирается знак минус, так как в общем случае Q"n<CQ."n-i. Значение Q%{x) =У21п[(д:+ 1)/(х-1)], тогда как Q>i{x)=xQ%{x)--\, и

Qio(Jc)=-l/l/-l.

Другие значения получаются путем использования отношений-Rnix) и (или) рекуррентной формулы

е"»» = - (2 (т - 1) xjV~[) j{n~m + 2){n-{-m-2)

Получение выражения для Q%{ix) нетривиально и производите» следующим образом:

tXQ»o(/)=4in=4ln

х;2 -1- } i х2 -Ь 1

2 iK - l 2 Поэтому tgb=-Q.xl{\-x) и Q°o{ix) == {arctgx-л/2)i. АЛГОРИТМ 636

Разделение элелентов массива [Ml]

Процедура partition {partition - разделение) выбирает значение г случайного элемента из массива а[т:п] и переставляет значения элементов этого массива таким образом, чтобы существовали целые i и j

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

** По-видимому, в оригинале здесь ош-»бка. Нужно

1 Гхг - 1 2X1

"""2"" х+ 1



со следующими свойствами: mi<ijn при условии т<п. Далее если mp<:i, i<:r<j, то ф]<аИ<49]-

Эта процедура использует нелокализованную целую процедуру-функцию random{m,n), которая с равной вероятностью выбирает случайное целое число р между m и п, и нелокализованную процедуру exchange, описание которой имеет вид procedure exchange (a,b);

value a,b; real a,b; begin real s; s: = a; a: = b; b: = s end;

Выходные параметры процедуры partition: a, i и /. procedure partition(m,n) dataresult: (a)result: (i,]);

value m,n; integer m,n,i,j; array a; begin real x; integer p;

p: = random (m,n); x: = a[p];

i: = n; j:=m; nOl: for j: = j step 1 until n do

a[j]>x then go to n02;

j:=Ti;

n02: for i: = i step -1 until m do if a[i]<x then go to n03; i:=m; n03: if i>j then

begin exchange (a[i],ali]); i: = i-1; j:=:j-f 1; go to nOl end; if j<p then

begin exchange(a[j],a[p]); j:=j + i end eise if i>p then

begin exchange{a[i],alp]); -1 end end partition;

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

Процедура partition алгоритма 636 является стереотипным переизданием процедуры partition алгоритма 63а, за исключением первой строки, которая в алгоритме 63а имела вид

procedure partition(a,m,n,i,j); Это изменение сделано ради удобства пользования процедурой. Б пояснительный текст алгоритма также внесены некоторые изменения, повышающие ясность изложения.

Алгоритм 636 был транслирован в системе БЭСМ-АЛГОЛ машины БЭСМ-6 для примеров, приведенных в .нижеследующем «Свидетельстве к алгоритму 63а», т. е. оператор p:=random{m,n) заменялся (ради удобства отладки) оператором р:~3 или /7:~4. Были получены такие же результаты, какие указаны в «Свидетельстве к алгоритму бЗа»

Переводы «Подтверждений к алгоритмам 63, 64 и 65» помещены после алгоритма 656.

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

Алгоритм 63а получен в результате ординарной переработки алгоритма 63 (Ноаге С. А. R. «САСМ», 1961, № 7).



Алгоритм 63а проверен вручную для а= (4, 1, 3, 5, 2); т=1, п=5 и /7=3 и 4. Получены результаты

для р = 3 а= (2, 1, 3, 5, 4); i=2; /=4; для р=4 с= (4, 1, 3, 2, 5); i=4; /=5.

АЛГОРИТМ 646

Быстрая сортировка {рекурсивная процедура) [Ml]

Процедура quicksort (quick - быстрая, sort - сортировка)-это очень быстрый и удобный метод, сортировки массива в памяти машины с генератором случайных чисел. Среднее число сравнений равно 2(п-т)1п{п-т), а среднее число .парных перестановок равно ls(n-т)1п{п-т). Смысл параметров а, т и п тот же, что и в алгоритме 636.

procedure quicksort (m,n) dataresult: (a); value m,n; integer m,n; array a; if m<:n then begin integer i,j; partition (m,n,a,i,j); quicksort (m,i,a); quicksort (j,n,a) end quicksort;

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

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

Алгоритм 646 транслирован в системе БЭСМ-АЛГОЛ на машине БЭСМ-6 совместно с процедурой partition алгоритма 636, в которой оператор р: = random {т,п) был заменен (для удобства отладки) на оператор p:=.(m--n)/2. Алгоритм дал правильный результат при задании параметров т=\, п=о и о;=.(4, 1, З, 5, 2).

Переводы «Подтверждений к алгоритмам 63, 64 и 65» помещены после алгоритма 656.

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

Алгоритм 64а получен в результате сокращения « ординарной переработки алгоритма 64 (Ноаге С. А. R. «САСМ», 1961, № 7). Данный алгоритм использует свойство рекурсивности процедур и может работать только на соответствующих трансляторах (например, на ТА-2 [18]).





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 42 43

0.0024