Izpitno vprašanje DIRI2005 5900

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vsebina

Vprašanje

|Vpr. 5900| S pomočjo osnovnih operacij nad skladom iz danega sklada števil odstrani vsa soda števila.

Odgovor

Ideja

Iz danega sklada števil S po vrsti pregledujemo števila, ki so na vrhu. Če je število sodo (deljivo z 2), ga iz sklada odstranimo, če je liho, ga najprej preložimo v pomožen sklad in šele nato odstranimo iz prvotnega sklada. Ko je sklad s prazen, iz pomožnega sklada preložimo števila nazaj v prvotni sklad S.

Algoritem

//Naj bo dan sklad števil S, ki vsebuje n števil.

if S.prazen() NAPAKA

//Če je sklad S prazen, se algoritem ne izvede.

else {

//V nasprotnem primeru se izvede algoritem, s katerim lihe elemente preložimo v pomožen sklad.

 Sklad pom = pripravi();
 //Ustvarimo prazen pomožen sklad.
 for (int i = 1; i <= n; i++) {
 //Algoritem se izvaja dokler je v skladu S še kak element.
  x = S.vrh();
  //Trenutni element dobi vrednost zgornjega elementa v skladu.
  if (x%2 == 0) {
  //Pogojni stavek, s katerim iz sklada odstranimo sodo število.
   S.odstrani(x);
  }
  else {
  //Če trenutni element ni sodo število,
   pom.vstavi(x);
   //ga vstavimo v pomožen sklad
   S.odstrani(x);
   //in šele nato odstranimo iz sklada S.
  }
 }

//Zanka, s katero liha števila iz pomožnega sklada preložimo nazaj v prvotni sklad S.

 while (!pom.prazen()) {
 //Dokler je v pomožnem skladu še kak element,
  x = pomozen.vrh;
  //njegovo vrednost priredimo trenutnemu elementu,
  S.vstavi(x);
  //ga vstavimo v prvotni sklad S
  pom.odstrani(x);
  //in odstranimo iz pomožnega sklada.
 }
}
Osebna orodja