Izpitno vprašanje DIRI2005 11600

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vprašanje

Iz podatkov 3, 7, 934, 323, 436, 56, 68, 45, 563, 57, 56, 511, 9879, 234, 355, 53, 35, 34, 111, 22 sestavi dve kopici. Prva naj bo taka, da je oče večji in druga taka, da je oče manjši od sinov. Pri prvi kopici uporabi algoritem, ki predvideva, da podatke dobivamo sproti in pri drugi takega, kjer podatke poznamo vnaprej! Razloži razliko med tema dvema postopkoma.

Odgovor

Prva kopica bo MAX kopica in podatke dobivamo sproti.

Upoštevamo: MAX kopica je dvojiško drevo (s posebno lastnostjo). Vrednost v očetu ni manjša od vrednosti v sinovih. Je levo poravnano. Takšno kopico lahko predstavimo v tabeli (brez praznih mest). Elemente indeksiramo od 1 naprej. Če je i-ti element v tabeli oče, ima za svojega levega sina (2*i)-ti element in za svojega desnega sina (2*i+1)-ti element.

Najprej dobimo prvi podatek (3) in ga postavimo na 1.mesto v tabeli:

  • 3

nov podatek (7) postavimo na 2.mesto:

  • 3 , 7

ker sestavljamo MAX kopico, kjer je na 1.mestu v tabeli oče in na drugem mestu njegov levi sin, ki je manjši od očeta, se podatek 7 prebije na vrh in 1. in 2.podatek zamenjati svoji mesti. Dobimo delno urejeno tabelo:

  • 7, 3

nov podatek (934) postavimo na 3.mesto:

  • 7, 3, 934

na tretjem mestu v tabeli je pri MAX kopici desni sin očeta, ki je na 1.mestu, element 934 se prebije na vrh in s 1.podatkom zamenjati mesti. Dobimo delno urejeno tabelo:

  • 934, 3, 7

nov podatek (323) postavimo na 4.mesto:

  • 934, 3, 7, 323

element 323 se prebija proti vrhu. Primerjamo ga z očetom (3), ker je oče manjši, zamenjata položaja. Novi oče (934) je večji, zato je konec zamenjav. Dobimo:

  • 934, 323, 7, 3

nov podatek (436) postavimo na 5.mesto:

  • 934, 323, 7, 3, 436

zadnji element se prebija proti vrhu, primerjamo ga z očetom (323), ker je oče manjši, ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 934, 436, 7, 3, 323

nov podatek (56) postavimo na 6.mesto:

  • 934, 436, 7, 3, 323, 56

podatek 56 se prebija proti vrhu, primerjamo ga z očetom (7), ker je oče manjši, ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 934, 436, 56, 3, 323, 7

nov podatek (68) postavimo na 7.mesto:

  • 934, 436, 56, 3, 323, 7, 68

podatek 68 se prebija proti vrhu, primerjamo ga z očetom (56), ker je oče manjši, ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 934, 436, 68, 3, 323, 7, 56

nov podatek (45) postavimo na 8.mesto:

  • 934, 436, 68, 3, 323, 7, 56, 45

podatek 45 se prebija proti vrhu, primerjamo ga z očetom (3), ker je oče manjši, ju zamenjamo. Novi oče (436) je večji, konec zamenjav. Dobimo:

  • 934, 436, 68, 45, 323, 7, 56, 3

nov podatek (563) postavimo na 9.mesto:

  • 934, 436, 68, 45, 323, 7, 56, 3, 563

podatek 563 se prebija proti vrhu, primerjamo ga z očetom (45), ker je oče manjši, ju zamenjamo. Novi oče (436) je tudi manjši, ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 934, 563, 68, 436, 323, 7, 56, 3, 45

nov podatek (57) postavimo na 10.mesto:

  • 934, 563, 68, 436, 323, 7, 56, 3, 45, 57

podatek 57 se prebija proti vrhu, primerjamo ga z očetom (323),ker je oče večji je vse v redu, nič se ne spremeni. Dobimo:

  • 934, 563, 68, 436, 323, 7, 56, 3, 45, 57

nov podatek (56) postavimo na 11.mesto:

  • 934, 563, 68, 436, 323, 7, 56, 3, 45, 57, 56

podatek 56 se prebija proti vrhu, primerjamo ga z očetom (323), ker je oče večji, se nič ne spremeni. Dobimo:

  • 934, 563, 68, 436, 323, 7, 56, 3, 45, 57, 56

nov podatek (511) postavimo na 12.mesto:

  • 934, 563, 68, 436, 323, 7, 56, 3, 45, 57, 56, 511

podatek 511 se prebija proti vrhu, primerjamo ga z očetom (7), ker je oče manjši, ju zamenjamo. Novi oče (68) je tudi manjši, zato ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 934, 563, 511, 436, 323, 68, 56, 3, 45, 57, 56, 7

nov podatek (9879) postavimo na 13.mesto:

  • 934, 563, 511, 436, 323, 68, 56, 3, 45, 57, 56, 7, 9879

podatek 9879 se prebija proti vrhu, primerjamo ga z očetom (68), ker je oče manjši, ju zamenjamo. Novi oče (511) je tudi manjši, ju zamenjamo. Novi oče (934) je tudi manjši, ju zamenjamo. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 56, 3, 45, 57, 56, 7, 68

nov podatek (234) postavimo na 14.mesto:

  • 9879, 563, 934, 436, 323, 511, 56, 3, 45, 57, 56, 7, 68, 234

podatek 234 se prebija proti vrhu, primerjamo ga z očetom (56), ker je oče manjši, ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 234, 3, 45, 57, 56, 7, 68, 56

nov podatek (355) postavimo na 15.mesto:

  • 9879, 563, 934, 436, 323, 511, 234, 3, 45, 57, 56, 7, 68, 56,355

podatek 355 se prebija proti vrhu, primerjamo ga z očetom (234), ker je oče manjši, ju zamenjamo. Novi oče (934) je večji, konec zamenjav. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 355, 3, 45, 57, 56, 7, 68, 56, 234

nov podatek (53) postavimo na 16.mesto:

  • 9879, 563, 934, 436, 323, 511, 355, 3, 45, 57, 56, 7, 68, 56, 234, 53

zadnji element (53) se prebija proti vrhu, primerjamo ga z očetom (3), ker je oče manjši, ju zamenjamo. Novi oče (436) je večji, konec zamenjav. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 45, 57, 56, 7, 68, 56, 234, 3

nov podatek (35) postavimo na 17.mesto:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 45, 57, 56, 7, 68, 56, 234, 3, 35

zadnji element (35) se prebija proti vrhu, primerjamo ga z očetom (53), oče je večji, ostaneta na svojih položajih. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 45, 57, 56, 7, 68, 56, 234, 3, 35

nov podatek (34) postavimo na 18.mesto:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 45, 57, 56, 7, 68, 56, 234, 3, 35, 34

zadnji element (34) se prebija proti vrhu, primerjamo ga z očetom (45), oče je večji, ostaneta na svojih položajih. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 45, 57, 56, 7, 68, 56, 234, 3, 35 , 35

nov podatek (111) postavimo na 19.mesto:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 45, 57, 56, 7, 68, 56, 234, 3, 35 , 35, 111

zadnji element se prebija proti vrhu, primerjamo ga z očetom (45), ker je oče manjši, ju zamenjamo. Novi oče (436) je večji, konec zamenjav. Dobimo:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 111, 57, 56, 7, 68, 56, 234, 3, 35, 35, 45

nov podatek (22) postavimo na 20.mesto:

  • 9879, 563, 934, 436, 323, 511, 355, 53, 111, 57, 56, 7, 68, 56, 234, 3, 35, 35, 45, 22

zadnji element se prebija proti vrhu, primerjamo ga z očetom (57), oče je večji, ostaneta na svojih mestih. Dobimo končno tabelo (ki je MAX kopica):

  • 9879, 563, 934, 436, 323, 511, 355, 53, 111, 57, 56, 7, 68, 56, 234, 3, 35, 35, 45, 22

Druga kopica bo MIN kopica in podatke poznamo vnaprej.

Upoštevamo: MIN kopica je dvojiško drevo (s posebno lastnostjo). Vrednost v očetu ni večja od vrednosti v sinovih. Je levo poravnano. Takšno kopico lahko predstavimo v tabeli (brez praznih mest). Elemente indeksiramo od 1 naprej. Če je i-ti element v tabeli oče, ima za svojega levega sina (2*i)-ti element in za svojega desnega sina (2*i+1)-ti element. Prvih n/2 elementov ima sinove. Če je sodo število elementov v tabeli ima n/2-ti element le levega sina.

  • v tabeli imamo naslednje podatke: 3, 7, 934, 323, 436, 56, 68, 45, 563, 57, 56, 511, 9879, 234, 355, 53, 35, 34, 111, 22

vzamemo n/2-ti element, to je v našem primeru (imamo 20 elementov) 10.element (57), njegov levi sin je 20.element (22), ker sestavljamo MIN kopico, potopimo očeta v smeri (edinega!) manjšega sina. Ker ta element nima desnega sina je konec. Dobimo:

  • 3, 7, 934, 323, 436, 56, 68, 45, 563, 22, 56, 511, 9879, 234, 355, 53, 35, 34, 111, 57

obravnavamo 9.element (563), njegova sinova sta levi - 18. (34) in desni - 19. (111) element. 9.element potopimov v smeri manjšega sina, ki je na 18.mestu. Ta nima sinov, zato je konec potapljanja. Dobimo:

  • 3, 7, 934, 323, 436, 56, 68, 45, 34, 22, 56, 511, 9879, 234, 355, 53, 35, 563, 111, 57

obravnavamo 8.element (45), njegova sinova sta levi - 16. (53) in desni - 17. (35) element. 8.podatek potopimo v smeri manjšega sina, to je 17.element. Ta nima več sinov, zato je konec potapljanja. Dobimo:

  • 3, 7, 934, 323, 436, 56, 68, 35, 34, 22, 56, 511, 9879, 234, 355, 53, 45, 563, 111, 57

obravnavamo 7.element (68), njegova sinova sta levi - 14. (234) in desni - 15. (355) element. Ker sta oba sinova večja, ne potapljamo. Elementi ostanejo na svojih mestih. Ostane:

  • 3, 7, 934, 323, 436, 56, 68, 35, 34, 22, 56, 511, 9879, 234, 355, 53, 45, 563, 111, 57

obravnavam 6.element (56), njegova sinova sta levi - 12. (511) in desni - 13. (9879) element. Ker sta oba sinova večja od očeta, ne potapljamo. Elementi ostanejo na istem mestu. Ostane:

  • 3, 7, 934, 323, 436, 56, 68, 35, 34, 22, 56, 511, 9879, 234, 355, 53, 45, 563, 111, 57

obravnavamo 5.element (436), njegova sinova sta levi - 10. (22) in desni - 11. (56) element. 5.element potopimo v smeri manjšega sina, to je 10. (22) element. 10.element ima desnega sina na 20.mestu (57), ker je 10.element večji ga potopimo v smeri manjšega sina na 20.mestu. Dobimo:

  • 3, 7, 934, 323, 22, 56, 68, 35, 34, 57, 56, 511, 9879, 234, 355, 53, 45, 563, 111, 436

obravnavamo 4.element (323), njegova sinova sta levi - 8. (35) in desni - 9. (34) element. 4.element potopimo v smeri manjšega sina, v tem primeru 9. (34). 9.element (323) ima sinova na 18. (563) in 19. (111) mestu. Ker je večji, ga potopimo v smeri manjšega sina na 19.mestu. Ta nima več sinov zato je konec potapljanja. Dobimo:

  • 3, 7, 934, 34, 22, 56, 68, 35, 111, 57, 56, 511, 9879, 234, 355, 53, 45, 563, 323, 436

obravnavamo 3.element (934), njegova sinova sta levi - 6. (56) in 7. (68) element. 3.element potopimo v smeri manjšega sina na 6.mestu. Sedaj sta njegova sinova na 12. (511) in 13.(9879) mestu. Element na 6.mestu potopimo v smeri mnajšega sina na 12.mestu. Ta nima sinov zato se potapljanje konča. Dobimo:

  • 3, 7, 56, 34, 22, 511, 68, 35, 111, 57, 56, 934, 9879, 234, 355, 53, 45, 563, 323, 436

obravnavamo 2.element (7), njegova sinova sta levi - 4. (34) in desni - 5. (22) element.Ker sta oba večja so vsi na pravih mestih, do potapljanja ne pride. Ostane:

  • 3, 7, 56 34, 22, 511, 68, 35, 111, 57, 56, 934, 9879, 234, 355, 53, 45, 563, 323, 436

obravnavamo 1.element (3), njegova sinova sta levi - 2. (7) in desni - 3. (56) element. Ker sta oba večja, so vsi na pravih mestih in se nič ne spremeni. Dobimo končno tabelo (ki je MIN kopica):

  • 3, 7, 56 34, 22, 511, 68, 35, 111, 57, 56, 934, 9879, 234, 355, 53, 45, 563, 323, 436

Razlika med tema dvema postopkoma:

  • Pri prvem postopku: element ki ga dobimo vedno postavimo na zadnje mesto v tabeli. Potem pa se nov element prebija navzgor, primerjamo ga z očetom, če je večji (manjši - pri MIN kopici) se z očetom zamenjata. Postopek ponavljamo do zadnjega elementa.
  • Pri drugem postopku: vzamemo zadnjega očeta in ga primerjamo s sinovoma. Potopimo ga, če je večji od sinov in sicer v smeri manjšega sina (pri MAX kopici ga potopimo v smeri večjega sina). Ponavljamo do prvega elementa v tabeli.
Osebna orodja