| punkty | ocena |
|---|---|
| 0-3.999 | 2 |
| 4-6.999 | 3 |
| 7-9.999 | 3+ |
| 10-12.999 | 4 |
| 13-16.999 | 4+ |
| 17- | 5 |
P[0] = x^1 = 1.100 P[1] = x^2 = 1.210 P[2] = x^4 = 1.464 ....oraz dokonać optymalizacji, tzn. wyeliminować niepotrzebne liczenia w pierwszej i drugiej pętli. W trzecim algorytmie należy wypisać wyrażenia odpowiadające niezmiennikowi pętli z konkretnymi danymi.
type
Lista = ^Element;
Element = record
liczba: integer;
nast: Lista;
end;
Stos = Lista;
function Pusty(S: Stos): boolean;
function NaGorze(S: Stos): integer;
procedure Push(var S: Stos; a: integer);
{ należy utworzyć nowy Element
new(e)
i przypisać
e^.liczba := a
i potem wstawić Element e na górze stosu (na początku listy)
}
procedure PopS(var S: Stos);
procedure Przerzuc(var Sin, Sout: Stos); {przerzucanie elementów ze stosu Sin do Sout}
type
Kolejka = record
stos_in, stos_out: Stos;
end;
function Pusta(K: Kolejka): boolean; {czy oba stosy są puste}
function Pierwszy(K: Kolejka): integer;
{podaje liczbę w pierwszym elemencie stos_out przerzucając wcześniej
elementy ze stos_in jeśli trzeba}
procedure Dodaj(var K: Kolejka; a: integer); {robi Push do stos_in}
procedure PopK(var K: Kolejka);
{usuwa pierwszy element ze stos_out przerzucając wcześniej
elementy ze stos_in jeśli trzeba}
Pracownia specjalistyczna: Implementacja przy użyciu kolejek dwóch sortowań z trzech: sortowanie szybkie, leksykograficzne i przez scalanie.
Aby zaimplementować sortowanie przez scalanie przy użyciu kolejek należy zaimplementować kolejki oraz funkcje
void Dziel(kolejka *K, kolejka* K1, kolejka* K2) {
// Dzieli kolejkę K na dwie części, które zapisuje do K1 i K2
}
void Scal(kolejka *K1, kolejka *K2, kolejka *K) {
// scala posortowane kolejki K1 i K2 w pustą kolejkę K
}
void SortowaniePrzezScalanie(kolejka *K) {
kolejka K1; Init(K1);
kolejka K2; Init(K2);
if (K.Count > 1) {
Dziel(&K,&K1,&K2);
SortowaniePrzezScalanie(&K1);
SortowaniePrzezScalanie(&K2);
Scal(&K1,&K2,&K);
}
}
int main(){
kolejka K;
// Wczytanie z pliku 'dane.txt' liczb do sortowanie do kolejki K
SortowaniePrzezScalanie(&K);
// Wypisanie kolejki K
}
{listowa}
var Zbior: array[1..n] of 1..n;
var Pierwszy: array[1..n] of 0..n; (* 0 - brak elementow we zbiorze *)
var Nastepny: array[1..n] of 0..n; (* 0 - brak nastepnego elementu *)
procedure Init1;
(* Zbior[i]:=i, Pierwszy[i]:=i, Nastepny[i]:=0 *)
function FIND1(i: integer): integer;
(* zbior, do ktorego nalezy element i *)
(* tzn. Zbior[i] *)
procedure UNION1(i,j: integer);
(* zakladamy, ze i <> j; dolaczamy zbior j do i *)
{drzewiasta}
var Ojciec: array[1..n] of 0..n; (* 0 - brak ojca *)
var Ilosc: array[1..n] of 1..n; (* ilosc reprezentowanych elementow *)
procedure Init2; (* wpisuje zera do Ojciec i jedynki do Ilosc *)
function FIND2(i: integer): integer;
(* rekurencyjnie znajduje reprezentanta elementu i *)
(* uzywajac tablicy Ojciec *)
procedure UNION2(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;