Izpitno vprašanje RAČ2PRA 5500

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vprašanje

Razloži in reši problem postajenačelnika.

Odgovor

Miha je postajni načelnik na železniški postaji sredi hribovite pokrajine, kjer je zelo malo prostora. V resnici ga je ravno toliko, da postaja vsebuje slepi tir, ter vhodni in izhodni tir. Vrstni red vagonov se na postaji vsakič spremeni. Torej, če so vagoni na postajo prišli v vrstnam redu npr. ABC, jih želimo odposlati v drugačnem vrstnem redu, npr. BCA. Miha vedno vnaprej dobi željeno izhodno kombinacijo. Zanima jih, če je taka preureditev vagonov možna. Če ni možna, bo takoj javil v centralo, da bodo vlak poslali po drugi poti. Pomagaj mu in sestavi program, ki sprejme prihajajočo razporeditev vagonov in željeno izhodno razporeditev in pove, če je ta možna.

  • Predpostavke:
    - Na slepem tiru je dovolj prostora za vse vagone.
    - Vagoni se z izhodnega tira ne vračajo na slepi tir.
    - Vagoni se s slepega tira ne vračajo na vhodni tir.


Primer vlaka

ABC ... želimo dobiti BCA
vagon A, B in C zapelje na slepi tir
vagon A, B in C se iz slepega tira premakne na izhodnega


  • Ideja:
    - vagoni na vhodnem tiru: sklad (prvi vagon je na vrhu)
    - vagoni na slepem tiru: sklad
    - željena kompozicija: sklad, kjer je oznaka prvega vagona nove kompozicije na vrhu
  • Simulacija dogajanj:
    - Če je na slepem tiru enak vagon, kot ga potrebujemo na izhodnem tiru, ga s slepega tira pošljemo na izhodni tir in na spisku z želeno kompozicijo odstranimo ta vagon.
    - Če na slepem tiru ni ustreznega vagona, z vhodnega tira pripeljemo nov vagon na slepi tir.
    - Rekurzija

  1. public static boolean urediVagone(Sklad1 vhodniS, Sklad1 izhodniS, Sklad1 pomozniS){
  2. //vhodniS: vagoni, ki še čakajo
  3. //pomozni: sklad vagonov na slepem tiru
  4. //izhodniS: spisek oznak vagonov, ki jih moramo še poslati na izhodni tir. Pozor: To niso vagoni, ki
  5. //smo jih že odposlali, ampak zapis tsitega dela kompozicije, ki jo moramo še sestaviti
  6. //
  7. // rekurzivno ureja vagone
  8. if (izhodniS.prazen()) return true; // vagoni so urejeni
  9.  
  10. while (!pomozniS.prazen() && (pomozniS.vrh() == izhodniS.vrh())) {
  11. // dokler je prav, prestavljaj vagone s slepega na izhodni tir
  12. //prestavljaj na izhodni pomeni, da v izhodniS zbrišemo oznako, ker smo pač ta vagon že
  13. //odposlali na izhod!
  14. System.out.println("Prestavi vagon " + pomozniS.vrh() + " s slepega na izhodni tir!");
  15. izhodniS.odstrani();
  16. pomozniS.odstrani();
  17. }
  18.  
  19. if (vhodniS.prazen()){ // na vhodnem tiru ni vec vagonov
  20. if (pomozniS.prazen()) return true; // vagoni so urejeni
  21.  
  22. if (pomozniS.vrh() != izhodniS.vrh()){ // vagonov se ne da urediti
  23. System.out.println(" Vagonov ni mogoče urediti!");
  24. return false;
  25. }
  26. }
  27.  
  28. else { // nov korak: premakni vagon na slepi tir in rekurzivno klici metodo
  29. System.out.println("Prestavi vagon " + vhodniS.vrh() + " z vhodnega na slepi tir!");
  30. pomozniS.vstavi(vhodniS.vrh());
  31. vhodniS.odstrani();
  32. }
  33.  
  34. return urediVagone(vhodniS, izhodniS, pomozniS); // rekurzivni klic
Osebna orodja