| punkty | ocena |
|---|---|
| 0-4.999 | 2 |
| 5-8.999 | 3 |
| 9-12.999 | 3+ |
| 13-16.999 | 4 |
| 17-21.999 | 4+ |
| 22- | 5 |
type List = ^Element; Element = record nbr: integer; next: List; end; Stack = record First: List; Count: word; end; procedure Init(var S: Stack); function Empty(S: Stack): boolean; function First(S: Stack): integer; procedure Push(var S: Stack; i: integer); procedure Pop(var S: Stack);
Program MergeSort;
uses Listy, crt;
procedure Dziel(var K,K1,K2: Kolejka);
begin
{ Dzieli kolejkę K na dwie części, które zapisuje do K1 i K2}
end;
procedure Scal(var K1,K2,K: Kolejka);
begin
{ scala posortowane kolejki K1 i K2 w pustą kolejkę K }
end;
procedure SortowaniePrzezScalanie(var K: Kolejka);
var K1,K2: Kolejka;
begin
Init(K1);
Init(K2);
if K.Count > 1 then
begin
Dziel(K,K1,K2);
SortowaniePrzezScalanie(K1);
SortowaniePrzezScalanie(K2);
Scal(K1,K2,K);
end;
end;
var K: Kolejka;
begin
{ Wczytanie z pliku 'dane.txt' liczb do sortowanie do kolejki K }
SortowaniePrzezScalanie(K);
{ Wypisanie kolejki K }
end.
{UNION-FIND}
var Ojciec: array[1..n] of 0..n; (* 0 - brak ojca *)
var Ilosc: array[1..n] of 1..n; (* ilosc reprezentowanych elementow *)
procedure Init_UNION_FIND; (* wpisuje zera do Ojciec i jedynki do Ilosc *)
function FIND(i: integer): integer; (* rekurencyjnie znajduje reprezentanta elementu i *)
(* uzywajac tablicy Ojciec *)
procedure UNION(i,j: integer); (* zakladamy, ze i <> j oraz i i j nie maja ojcow *)
(* laczymy zbiory reprezentowane przez i i j *)
{KRUSKAL}
var Wedges: array[1..m] of record
start, koniec, waga: integer;
end;
ReadGraph; { wczytuje z pliku m krawedzi (trojek liczb) }
SortWedges; { sortuje krawedzie wg wag }
Init_UNION_FIND;
for i:=1 to m do
begin
p:=FIND(Wedges[i].start);
k:=FIND(Wedges[i].koniec);
if p <> k then
begin
{ wypisz krawedz }
UNION(p,k);
end;
end;