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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Cчётчики

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

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

Автор: volvo 4.10.2006 19:46

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

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 Не понял... Я же вроде тебе же показывал, как это делается?

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

Цитата(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;
...