Izpitno vprašanje RAČ2PRA 14600

Iz MaFiRaWiki

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

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

Naštej nekatere probleme, ki jih lahko rešiš s pomočjo metode deli in vladaj in opiši algoritem za enega od teh.


Odgovor

Nekaj problemov, ki jih lahko rešimo s pomočjo metode deli in vladaj:

  • hitro urejanje
  • urejanje z zlivanjem
  • bisekcija
  • iskanje k-tega najmanjšega elementa v tabeli
  • Strassenovo množenje matrik
  • hitra Fourierova transformacija
  • iskanje najbližjih si točk v ravnini


Pa si kot primer uporabe metode deli in vladaj poglejmo iskanje k-tega najmanjšega elementa v tabeli.

Podano imamo tabelo n števil in želimo poiskati k-ti element po velikosti.

Reševanje:

Delimo kot pri hitrem urejanju:
Slika:DeliInVladaj.jpg


  • če k <= m: nas (n-m)-ti del ne zanima; iščemo k-tega v levem delu
  • če k > m: nas m-ti del ne zanima; iščemo (k-m)-tega v desnem delu


Primer:

Imamo tebelo števil: 70, 75, 80, 85, 60, 55, 50, 45, 223, 22, 56, 185, 82, 5, 15, 14 in iščemo 7. element.
  • Deli: 22, 14, 15, 5, 60, 55, 50, 45, 56, 70, 223, 185, 82, 85, 80, 75
V prvem delu je 10 elementov, zato iščemo še naprej 7. element v tem delu. Pivotni element bo sedaj 22.
  • 5, 14, 15, 22, 60, 55, 50, 45, 56, 70
V prvem delu so 4 elementi, zato iščemo naprej 7-4 = tretjega v drugem delu. Pivotni element bo 60.
  • 56, 55, 50, 45, 60, 70
V prvem delu je 5 elementov, zato iščemo še naprej 3. element v tem delu. Pivotni element bo 56.
  • 45, 55, 50, 56, 60
V prvem delu so 4 elementi zato iščemo še naprej 3. element v tem delu. Pivotni element bo 45.
  • 45, 55, 50, 56
V prvem delu je 1 elemet, zato iščemo naprej 3-1 = drugega v drugem delu. Pivotni elment bo 55.
  • 50, 55, 56
V prvem delu sta dva elementa, zato iščemo še naprej drugega v tem delu. Pivotni element bo 50.
  • 50, 55
V prvem delu je le en element, zato iščemo naprej 2-1 = prvega v drugem delu.
Rešitev: Iskani element je 55.


Glej tudi

Osebna orodja