Pogovor:Izpitno vprašanje DIRI2005 5100

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 09:36, 9 maj 2008
MatijaLokar (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
MatijaLokar (Pogovor | prispevki)

Vrstica 26: Vrstica 26:
--[[Uporabnik:MatijaLokar|Matija Lokar]] 11:36, 9 maj 2008 (CEST) --[[Uporabnik:MatijaLokar|Matija Lokar]] 11:36, 9 maj 2008 (CEST)
 +
 +----
 +V redu, a po nepotrebnem preveč zapleteno. Menim, da je lažje takole:
 +
 +* iz sklada jemljemo po dva elementa in ju v obratnem vrstnem redu preložimo v pomožni sklad
 +* prelozimo pomožni sklad v prvotnega!
 +
 +recimo:
 +
 +<java>
 + novS = pripravi(); // pripravimo nov sklad
 + while (!s.prazen()) {
 + elt = s.vrh();
 + s.odstrani();
 + if (!s.prazen()) { // če je še kak element - to moramo narediti zaradi skaldov z lihim številom elementov
 + novS.vstavi(s.vrh());
 + s.odstrani();
 + }
 + novS.vstavi(elt); // s tem sta po dva in dva elmenta obrnjena, razen morda zadnjega, če ta nima para
 + }
 + // preložimo nazaj
 + while (!novS.prazen()) {
 + s.vstavi(novS.vrh());
 + novS.odstrani();
 + }
 +</java>
 +--[[Uporabnik:MatijaLokar|Matija Lokar]] 14:34, 22 maj 2008 (CEST)

Trenutna različica

Manjka algoritem!

Ideja je prava, sedaj pa jo je potrebno še zložiti v algoritem, kjer uporabljate osnovne operacije nad skladom. Seveda pa je mogoče zadevo rešiti tudi samo z enim pomožnim skladom.

--Matija Lokar 10:25, 29 april 2008 (CEST)

Hm, algoritem ne bo čisto Ok. Nekaj je napak v implementaciji, napačno idejo pa sem prejšnjič spregledal! V ideji je narobe to, da ne jemljemo pri združevanju manjšega (končno - kdaj je zabojnik manjši od drugega?), ampak moramo le izmenično jemati! Torej, če je prvotni sklad a, x, g, h bi mpotrm mortal biti x, a, h, g.

Implementacija: zagotovo se ob "zlivanju" sklada ne spraznita sočasno!

Poleg tega je potrebno uporabljati osnovne operacije nad skladom. Torej sklad > 0 zagotovo ne bo ok! Še enkrat - na voljo imate OSNOVNE operacije.

Namig: en sklad v drugega preložimo takole

  1.  
  2. novS = pripravi(); // pripravimo nov sklad
  3. while (!s.prazen()) {
  4. elt = s.vrh();
  5. s.odstrani();
  6. novS.vstavi(elt);
  7. }

--Matija Lokar 11:36, 9 maj 2008 (CEST)


V redu, a po nepotrebnem preveč zapleteno. Menim, da je lažje takole:

  • iz sklada jemljemo po dva elementa in ju v obratnem vrstnem redu preložimo v pomožni sklad
  • prelozimo pomožni sklad v prvotnega!

recimo:

  1.  
  2. novS = pripravi(); // pripravimo nov sklad
  3. while (!s.prazen()) {
  4. elt = s.vrh();
  5. s.odstrani();
  6. if (!s.prazen()) { // če je še kak element - to moramo narediti zaradi skaldov z lihim številom elementov
  7. novS.vstavi(s.vrh());
  8. s.odstrani();
  9. }
  10. novS.vstavi(elt); // s tem sta po dva in dva elmenta obrnjena, razen morda zadnjega, če ta nima para
  11. }
  12. // preložimo nazaj
  13. while (!novS.prazen()) {
  14. s.vstavi(novS.vrh());
  15. novS.odstrani();
  16. }

--Matija Lokar 14:34, 22 maj 2008 (CEST)

Osebna orodja