Izpitno vprašanje RAČ2PRA 11500

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka Marjetaselak.

Pripravil/a ga je pri predmetu računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vsebina

Vprašanje

V algoritem za gradnjo kopic se nam je prikradla napaka. Poišči napačni element v spodnji kopici in povej, katere vrednosti lahko zavzame! Ali je ta element enolično določen?

    • 81, 20, 3, 16, 26
    • 90, 79, 54, 22, 35, 27, 43, 8, 23, 13
    • 98, 89, 98, 68, 82, 51, 52, 65, 49, 83, 62, 25, 29, 41, 50, 35, 28, 22, 2, 13

Odgovor

Kopica

Kopica je levo poravnano dvojiško drevo. Za maksimalno kopico velja, da je oče večji ali enak svojima sinovoma. Levo in desno poddrevo sta prav tako maksimalni kopici. Poznamo tudi minimalno kopico, tj. oče je manjši ali enak svojima sinovoma.

Rešitev naloge

Primer 1

  • Tabela števil:
    • 81, 20, 3, 16, 26

S pomočjo te tabele narišemo dvojiško drevo.

Ugotovimo, da to drevo ni kopica. Zato s pomočjo definicije maksimalne kopice, zlahka odčitamo vrednost, katera je napačna in povemo pravilno vrednost oz. vse možne pravilne vrednosti, ki jih lahko zavzame, da bo potem naše drevo predstavljalo maksimalno kopico.

Rešitev

Razlikujemo dva primera:

  • V našem primeru je lahko napačen element 26. Namesto tega števila bi moralo biti katerokoli poljubno število manjše ali enako 20 (ker je 20 oče), da bi tabela predstavljala maksimalno kopico.
  • Napačen element je lahko tudi 20, v tem primeru je 26 pravilen element. Namesto elementa 20 bi moralo biti poljubno število med 26 in 81 (tj. 26 <= število <= 81) in tako bi tabela postala kopica.

Primer 2

  • Tabela števil:
    • 90, 79, 54, 22, 35, 27, 43, 8, 23, 13

To drevo tudi ni kopica. Zato s pomočjo definicije maksimalne kopice, zopet odčitamo vrednost, katera je napačna in povemo pravilno vrednost oz. vse možne pravilne vrednosti, ki jih lahko zavzame, da bo potem naše drevo predstavljalo maksimalno kopico.

Rešitev

Zopet razlikujemo dva primera:

  • V tem primeru je lahko napačen element 23. Namesto tega števila bi moralo biti katerokoli poljubno število manjše ali enako 22 (ker je 22 oče) in tako bi tabela postala kopica.
  • Napačen element je lahko tudi 22, potem je 23 pravilen element. Namesto elementa 22 bi moralo biti poljubno število med 23 in 79 (tj. 23 <= število <= 79). Tabela bi zopet predstavljala kopico.

Primer 3

  • Tabela števil:
    • 98, 89, 98, 68, 82, 51, 52, 65, 49, 83, 62, 25, 29, 41, 50, 35, 28, 22, 2, 13

To drevo ravno tako še ni kopica. Zato s pomočjo definicije maksimalne kopice, zopet odčitamo vrednost, katera je napačna in povemo pravilno vrednost oz. vse možne pravilne vrednosti, ki jih lahko zavzame, da bo potem naše drevo predstavljalo maksimalno kopico.

Rešitev

Razlikujemo dva primera:

  • V tem primeru pa je lahko napačen element 83. Namesto tega števila bi moralo biti katerokoli poljubno število med 13 in 82 (tj. 13 <= število <= 82). Tako tabela postane kopica.
  • Napačen element je lahko tudi 82, potem je 83 pravilen element. Namesto elementa 82 bi moralo biti poljubno število med 83 in 89 (tj. 83 <= število <= 89) in tako tabela predstavlja max kopico.
Osebna orodja