?

Log in

No account? Create an account

Наивные чукотские юноши - Общество дровосеков Бердичева по изучению Мишны

Nov. 4th, 2009

12:25 am - Наивные чукотские юноши

Previous Entry Share Next Entry



РRОСЕDURЕ QUIСКЕRSОRТ(А,J);
СОММЕNТ МАССИВ А[1:J] УПОРЯДОЧИВАЕТСЯ ПО ВОЗРАСТАНИЮ;
VАLUЕ J; АRRАУ А; INТЕGЕR J;
ВЕGIN
  INТЕGЕR I,К,М,Р,Q;RЕАL Т,Х;
  INТЕGЕR АRRАУ LТ,UТ[1:LN(АВS(J)+2)/0.693];
  I:=М:=1;
  N: IF J-I>1 ТНЕN ВЕGIN
    Р:=(I+J)÷2;
    Т:=А[Р];
    А[Р]:=А[I];
    Q:=J;
    FОR К:=I+1 SТЕР 1 UNТIL Q  ВЕGIN
      IF А[К]>Т ТНЕN ВЕGIN
        FОR Q:=Q SТЕР -1 UNТIL К  ВЕGIN
          IF А[Q]<Т ТНЕN ВЕGIN
            Х:=А[К];
            А[К]:=А[Q];
            А[Q]:=Х;
            Q:=Q-1;
             ТО L
          ЕND
        ЕND;
        Q:=К-1;
         ТО S
      ЕND;
    L:ЕND ;
    S:А[I]:=А[Q];
    А[Q]:=Т;
    IF 2×Q>I+J ТНЕN ВЕGIN
      LТ[М]:=I;
      UТ[М]:=Q-1;
      I:=Q+1
    ЕND ЕLSЕ ВЕGIN
      LТ[М]:=Q+1;
      UТ[М]:=J;
      J:=Q-1
    ЕND;
    М:=М+1;
     ТО N
  ЕND ;
  IF I≥J ТНЕN  ТО R;
  IF А[I]>А[J] ТНЕN ВЕGIN
    Х:=А[I];
    А[I]:=А[J];
    А[J]:=Х
  ЕND ;
  R:М:=М-1;
  IF М>0 ТНЕN ВЕGIN
    I:=LТ[М];
    J:=UТ[М];
     ТО N
  ЕND
ЕND QUIСКЕRSОRТ

Comments:

[User Picture]
From:reedcat
Date:November 4th, 2009 01:13 pm (UTC)
(Link)
Размерность массива UT - это жесть!.. :)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 4th, 2009 03:01 pm (UTC)
(Link)
(Точнее, массивов LT и UT.)
В корень смотришь - я именно о них.
(Reply) (Parent) (Thread)
[User Picture]
From:cartesius
Date:November 4th, 2009 01:33 pm (UTC)
(Link)
Это на Паскале?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 4th, 2009 03:01 pm (UTC)
(Link)
Это АЛГОЛ-60.
(Reply) (Parent) (Thread)
[User Picture]
From:ygam
Date:November 4th, 2009 05:13 pm (UTC)
(Link)
Я когда-то переводил один алгоритм с Алгола-60 на сиплюсплюс, и только через какое-то время понял, что ошибся с нижней границей массива (1 в Алголе и 0 в сиплюсплюсе).

(как я это понял - интересная история; алгоритм вычислял многомерный интеграл одной функции внутри сферы; я решил проверить, что будет, если в 4хмерном пространстве уменьшить маленький радиус сферы вдвое - интеграл должен уменьшиться приблизительно в 16 раз, но он уменьшился в иное число раз)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 4th, 2009 06:06 pm (UTC)
(Link)
Надеюсь, это было всё ещё на этапе тестирования?

Ради прикола надо мне будет перекодировать всю библиотеку и выложить куда-нибудь. Например, что это такое, я не понимаю:

РRОСЕDURЕ UNR(Х,А,V);
INТЕGЕR Х; RЕАL А,V;
ВЕGIN INТЕGЕR I;
    V:=0;
    FОR I:=1 SТЕР 1 UNТIL 5  ВЕGIN
        Х:=3125×Х;
        Х:=Х-ЕNТIЕR(Х/67108864)×67108864;
        А:=Х/33554432-1;
        V:=V+А
    ЕND;
    V:=V×0.774596;
    V:=0.97×V×(1+0.01×V×V)
ЕND

(Reply) (Parent) (Thread)
[User Picture]
From:stas
Date:November 4th, 2009 06:37 pm (UTC)
(Link)
hash?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:November 4th, 2009 07:04 pm (UTC)
(Link)
Это, похоже, датчик случайных чисел, который возвращает одновременно и равномерно (U), и нормально (R) распределенные значения (важно, что Х передается по имени - на последовательных значениях малых Х результаты сильно неслучайные).

Еще меня смутило то, что при начальном X == 0 датчик не работает, но зато одну операцию сэкономили!
(Reply) (Parent) (Thread)
[User Picture]
From:reedcat
Date:November 6th, 2009 10:27 am (UTC)
(Link)
real procedure normrand(m,sigma,n);
value m,sigma,n; real m,sigma; integer n;
begin real sum; integer i;
sum:=0;
for i:=1 step 1 until n do sum:=sum+random;
normrand:=m+sigma*sum*sqrt(3/n);
end;

хихикс...
Ну ты напомнил... :)
(Reply) (Parent) (Thread)
[User Picture]
From:syarzhuk
Date:November 4th, 2009 09:49 pm (UTC)
(Link)
Мой однокурсник стал доктором наук и преподаёт численные методы; до сих пор большинство программ пишется на Фортране.
На моё недоумение объяснил, что f2c генерирует код так: из фортрановского A(i) = B(i) получается сишное a[i-1] = b[i-1];
переписывать библиотеки заново на C дорого, а фортрановые быстрее
(Reply) (Parent) (Thread)
[User Picture]
From:cema
Date:November 7th, 2009 01:32 am (UTC)
(Link)
Кроме того, оптимизирующие (и, что важно распараллеливающие) фазы компилятора куда проще писать для Фортрана, чем C.
(Reply) (Parent) (Thread)
[User Picture]
From:_navi_
Date:November 5th, 2009 05:16 am (UTC)
(Link)
а пляшущие буквы — это намеренно, или это у меня в консерватории что-то надо поправить?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:November 5th, 2009 05:31 am (UTC)
(Link)
Так в оригинале. Латинских букв, совпадающих по начертанию с русскими (ни буквы Y, которая считалась достаточно похожа на У), в кодировке ГОСТ 10859 не было.
(Reply) (Parent) (Thread)