Izpitno vprašanje RAČ2PRA 11200

Iz MaFiRaWiki

Vprašanje

|Vpr. 11200| Naj tabela

40 18 15 9 x 11 15 y 1 6 3 11 5

predstavlja max kopico celih števil (x in y seveda nista tiskarski napaki, ampak ustrezni celi števili). Katere (celoštevilske) vrednosti lahko zavzameta x in y?

Odgovor

Kopica je levo poravnano dvojiško drevo. Kopico, ki jo predstavlja zgornja tabela, lahko narišemo tudi kot drevo in dobimo naslednjo strukturo drevesa (iz katere preberemo rešitev):

Za maximalno kopico velja, da je oče večji ali enak svojima sinovoma. S pomočjo zgornje definicije max kopice lahko zlahka odčitamo vrednosti katere lahko zavzameta x in y.

Če imamo elemente kopice shranjene v tabeli tako kot v našem primeru, lahko uporabimo formule, za indeks sinov in očeta.

Formule so:

  levi sin = 2*i, desni sin = 2*i + 1, oce = i/2.

rešitev je torej: 6 <= x <= 18 in y <= 9

Glej tudi

Osebna orodja