Версия для печати темы

Автор: Anastacia Adesso 4.10.2006 19:29

Ммм вот тут никак не въеду..
Надо какимто образом вставить в обе процедуры (метод Хоара и метод сливания) счётчик, чтоб узнать количество сравниваний.
Тока вот куда?
Плиииз  HOARSALI.PAS ( 2.16 килобайт ) Кол-во скачиваний: 495

Автор: volvo 4.10.2006 19:46

По-моему, я уже где-то показывал, как это можно сделать. Попробую найти ссылку, а пока - просто принцип:
Операцию сравнения заменить на функцию:

function IsGreater(a, b: LongInt): boolean;
begin
  IsGreater := (a > b);
  {
    Ну, как ты понимаешь, ЗДЕСЬ производилось сравнение,
    поэтому именно тут увеличивай счетчик
  }
end;

Тогда, например, фрагмент:

while ar[j]>tempr do ...

Перепишется в виде:

while IsGreater(ar[j], tempr) do ...

, ну и не забывай обо ВСЕХ остальных сравнениях, тебе же надо считать все?

P.S.
Не понял... Я же вроде тебе же показывал, как это делается?

http://forum.pascal.net.ru/index.php?s=&showtopic=11030&view=findpost&p=69658

Автор: Anastacia Adesso 4.10.2006 19:54

Ага, спасибо! С Хоаром разобралась.
Но в другой процедуре всё ещё не найду куда

Автор: volvo 5.10.2006 4:40

Чем она кардинально отличается от Хоара? По-моему, ничем...

procedure merge(var ar:masiv; n:integer);

  type
    T = (cmLess, cmEqual, cmGreat);
  function Compare(a, b: longint): T;
  begin
    if a < b then Compare := cmLess
    else if a > b then Compare := cmGreat
         else Compare := cmEqual;
    inc(count);
  end;

  procedure Slit( k, q: longint);
  var
    m: longint;
    i,j,t: integer;
    d: masiv;
  begin
    m:=k+(q-k) div 2;
    i:=k; j:=succ(m); t := 1;
    while (i<=m) and (j<=q) do begin
      if compare(ar[ i ], ar[ j ]) in [cmLess, cmEqual] then begin
        d[t]:=ar[ i ]; Inc(i)
      end
      else begin
        d[t]:=ar[ j ]; Inc(j)
      end;
      inc(t)
    end;

    while i<=m do begin
      d[t]:=ar[ i ]; inc(i); inc(t)
    end;
    while j<=q do begin
      d[t]:=ar[ j ]; inc(j); inc(t)
    end;
    for i:=1 to pred(t) do ar[pred(k+i)]:=d[i]
  end;

  procedure sort(i,j:integer);
  var t: integer;
  begin
    if i>=j then exit;
    if j-i=1 then begin
      if compare(ar[ j ], ar[ i ]) = cmLess then begin
        t:=ar[ i ]; ar[ i ]:=ar[ j ]; ar[ j ]:=t
      end
    end
    else begin
      sort(i,i+(j-i) div 2);
      sort(i+(j-i) div 2+1,j);
      slit(i, j)
    end;
  end;

begin
  sort(1,n);
end;
...