od Pája » 6. 9. 2007 13:49
Ahoj!
Sice som nechodil k vam na cvicenia z programovania, ale chcel by som
vas poprosit o pomoc. Tak ako aj viaceri 'kolegovia' nemam este skusku
z programovania. Pri uceni som pouzil aj vasu zbierku uloh z
programovania. Chcel by som vas poprosit, ci by ste nemohli este
napisat 2 tie male priklady a to: destruktivny prienik a destruktivne
zjednotenie BVS. Tieto priklady mi pridu ako velmi tazke, pokusam sa
ich naprogramovat, ale vobec mi to nejde...
Ak by ste si teda nasli cas, bol by som vam velmi vdacny'
pomocná procedura
Kód: Vybrat vše
procedure vlozUzel(var koren: UKUzel; uzel: UkUzel);
begin
if (koren = nil) then begin
koren := uzel;
koren^.left := nil;
koren^.right := nil;
end else if (uzel^.info < koren^.info) then begin
vlozUzel(koren^.left, uzel);
end else if (uzel^.info > koren^.info) then begin
vlozUzel(koren^.right, uzel);
end else begin
dispose(uzel);
end;
end;
Sjednocení
Kód: Vybrat vše
(*
* Do stromu, jehoz korenem je "korenA" prida vsechny prvky ze stromu,
* jehoz korenem je "korenB". Po provedeni procedury bude tedy strom
* s korenem "korenA" obsahovat sjednoceni puvodnich mnozin prvku stromu A a B.
* Po provedeni procedury bude strom B prazdny ("korenB" bude nil).
*)
procedure destruktivniSjednoceni(var korenA, korenB: UkUzel);
var
levyPodstrom, pravyPodstrom: UkUzel;
begin
if korenB = nil then
exit;
levyPodstrom := korenB^.left;
pravyPodstrom := korenB^.right;
vlozUzel(korenA, korenB);
destruktivniSjednoceni(korenA, levyPodstrom);
destruktivniSjednoceni(korenA, pravyPodstrom);
korenB := nil;
end;
Průnik
Kód: Vybrat vše
(*
* Ze stromu, jehoz korenem je "korenB", odstrani vsechny prvky, ktere se
* nenachazeni ve strome, jehoz korenem je "korenA". Strom s korenem "korenA"
* zustane po provedeni procedury nedotcen.
*)
procedure destruktivniPrunik(var korenA, korenB: UkUzel);
begin
if korenB <> nil then begin
destruktivniPrunik(korenA, korenB^.left);
destruktivniPrunik(korenA, korenB^.right);
if not (jeTam(korenA, korenB^.info)) then
odstranKoren(korenB);
end;
end;
Sjednocení je triviální, průnik v podstatě taky, byť uvedené řešení není nejgeniálnější. Po provedení průniku možná budete chtít na strom s kořenem
korenA zavolat toto:
Kód: Vybrat vše
(*
* Odstrani ze stromu, jehoz koren je "koren", vsechny prvky a odalokuje
* pamet, kterou zabiraly.
* Po skonceni procedury bude mit "koren" hodnotu nil.
*)
procedure smazCelyStrom(var koren: UkUzel);
begin
if koren = nil then
exit;
smazCelyStrom(koren^.left);
smazCelyStrom(koren^.right);
dispose(koren);
koren := nil;
end;
Jak vidíte, s pomocí rekurze se dá mnohé vykouzlit. Pokud vám rekurze činí potíže, zkuste si pohrát s touto kravinkou:
http://vyuka.pavel-rimsky.cz/programs/zgr.zip.
[quote]
Ahoj!
Sice som nechodil k vam na cvicenia z programovania, ale chcel by som
vas poprosit o pomoc. Tak ako aj viaceri 'kolegovia' nemam este skusku
z programovania. Pri uceni som pouzil aj vasu zbierku uloh z
programovania. Chcel by som vas poprosit, ci by ste nemohli este
napisat 2 tie male priklady a to: destruktivny prienik a destruktivne
zjednotenie BVS. Tieto priklady mi pridu ako velmi tazke, pokusam sa
ich naprogramovat, ale vobec mi to nejde...
Ak by ste si teda nasli cas, bol by som vam velmi vdacny'
[/quote]
[b]pomocná procedura[/b]
[code]
procedure vlozUzel(var koren: UKUzel; uzel: UkUzel);
begin
if (koren = nil) then begin
koren := uzel;
koren^.left := nil;
koren^.right := nil;
end else if (uzel^.info < koren^.info) then begin
vlozUzel(koren^.left, uzel);
end else if (uzel^.info > koren^.info) then begin
vlozUzel(koren^.right, uzel);
end else begin
dispose(uzel);
end;
end;
[/code]
[b]Sjednocení[/b]
[code]
(*
* Do stromu, jehoz korenem je "korenA" prida vsechny prvky ze stromu,
* jehoz korenem je "korenB". Po provedeni procedury bude tedy strom
* s korenem "korenA" obsahovat sjednoceni puvodnich mnozin prvku stromu A a B.
* Po provedeni procedury bude strom B prazdny ("korenB" bude nil).
*)
procedure destruktivniSjednoceni(var korenA, korenB: UkUzel);
var
levyPodstrom, pravyPodstrom: UkUzel;
begin
if korenB = nil then
exit;
levyPodstrom := korenB^.left;
pravyPodstrom := korenB^.right;
vlozUzel(korenA, korenB);
destruktivniSjednoceni(korenA, levyPodstrom);
destruktivniSjednoceni(korenA, pravyPodstrom);
korenB := nil;
end;
[/code]
[b]Průnik[/b]
[code]
(*
* Ze stromu, jehoz korenem je "korenB", odstrani vsechny prvky, ktere se
* nenachazeni ve strome, jehoz korenem je "korenA". Strom s korenem "korenA"
* zustane po provedeni procedury nedotcen.
*)
procedure destruktivniPrunik(var korenA, korenB: UkUzel);
begin
if korenB <> nil then begin
destruktivniPrunik(korenA, korenB^.left);
destruktivniPrunik(korenA, korenB^.right);
if not (jeTam(korenA, korenB^.info)) then
odstranKoren(korenB);
end;
end;
[/code]
Sjednocení je triviální, průnik v podstatě taky, byť uvedené řešení není nejgeniálnější. Po provedení průniku možná budete chtít na strom s kořenem [i]korenA[/i] zavolat toto:
[code]
(*
* Odstrani ze stromu, jehoz koren je "koren", vsechny prvky a odalokuje
* pamet, kterou zabiraly.
* Po skonceni procedury bude mit "koren" hodnotu nil.
*)
procedure smazCelyStrom(var koren: UkUzel);
begin
if koren = nil then
exit;
smazCelyStrom(koren^.left);
smazCelyStrom(koren^.right);
dispose(koren);
koren := nil;
end;
[/code]
Jak vidíte, s pomocí rekurze se dá mnohé vykouzlit. Pokud vám rekurze činí potíže, zkuste si pohrát s touto kravinkou: [url]http://vyuka.pavel-rimsky.cz/programs/zgr.zip[/url].