Помощь - Поиск - Пользователи - Календарь
Полная версия: Cчётчики
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Anastacia Adesso
Ммм вот тут никак не въеду..
Надо какимто образом вставить в обе процедуры (метод Хоара и метод сливания) счётчик, чтоб узнать количество сравниваний.
Тока вот куда?
Плиииз unsure.gif Нажмите для просмотра прикрепленного файла
volvo
По-моему, я уже где-то показывал, как это можно сделать. Попробую найти ссылку, а пока - просто принцип:
Операцию сравнения заменить на функцию:

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

smile.gif

Тогда, например, фрагмент:
while ar[j]>tempr do ...
Перепишется в виде:
while IsGreater(ar[j], tempr) do ...
, ну и не забывай обо ВСЕХ остальных сравнениях, тебе же надо считать все?

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

Счётчик, Куда его поставить?
Anastacia Adesso
Ага, спасибо! С Хоаром разобралась.
Но в другой процедуре всё ещё не найду куда
volvo
Цитата(Anastacia Adesso @ 4.10.2006 14:54)
Но в другой процедуре всё ещё не найду куда

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

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;
...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.