Izpitno vprašanje RAČ2PRA 16000

Iz MaFiRaWiki

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

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.


Vprašanje

|Vpr. 16000|

Internetni glasbeni ponudnik bi rad svojim kupcem omogočil poslušanje glasbe v kar petih formatih. Od glasbenikov lahko kupi skladbo v poljubnem formatu, za pretvorbo v ostale štiri pa mora poskrbeti sam. Ker pa je pretvorba med formati potratna in je čas denar, želi izvesti pretvorbo čim hitreje. V katerem formatu naj od glasbenikov odkupi skladbe in v kakšnem zaporedju naj izvede pretvorbe med formati, če so cene za pretvorbo:

  • 1->2: 2 minuti
  • 1->3: 6 minut
  • 1->4: 4 minute
  • 1->5: 3 minute
  • 2->3: 4 minute
  • 2->4: 1 minuta
  • 2->5: 5 minut
  • 3->5: 8 minut
  • 3->4: 3 minute
  • 4->5: 8 minut

Privzemi, da je cena za pretvorbo iz formata a v format b enaka kot za pretvorbo iz formata b v format a (kar v praksi sicer še zdaleč ni res...).

Odgovor

Najprej narišemo diagram oziroma minimalno vpeto drevo, da bi si lahko lažje predstavljali pretvorbe formatov. Spodnji graf prikazuje naše drevo s pretvorbami.

Rešitev:

Postopek reševanja:

Kot smo že zgoraj omenili, najprej narišemo drevo pretvorb, zaradi lažjega reševanja naloge. Točke v drevesu predstavljajo formate, povezave med točkami pa ceno pretvorbe oziroma čas pretvorbe. Iščemo minimalno vpeto drevo torej v drevesu iščemo najcenejše povezave med vozlišči oziroma med točkami. Za reševanje takih dreves obstajata dva algoritma: Kurskalov algoritem in Primov algoritem. Ne glede kateri algoritem uporabimo, vedno pridemo do iste cene.

Izberimo Kurskalov algoritem. Tu gledamo najcenejše povezave, pri tem pa moramo paziti da ne naredimo cikla. Pogledamo katera je najcenejša povezava. Opazimo da je pretvora iz formata 2 v format 4 najcenejša, stane 1 enoto. Opazimo še, da je pretvorba formata 2 v format 1 naslednja najcenejša povezava, stane 2 enoti. S tem imamo povezane točke 1, 2 in 4. Naslednje so povezave, ki stanje 3 enote. Ena povezava pretvori format 4 v format 3 in druga, pretvori format 1 v format 5. Celotna pretvorba glasbe stane 9 enot.

Vrstni red pretvorb:

                    * 2 ---> 4 : stane 1 enota
                    * 2 ---> 1 : stane 2 enoti
                    * 1 ---> 5 in 4 ---> 3 : stane 3 enote.
Osebna orodja