Izpitno vprašanje DIRI2005 5100

Iz MaFiRaWiki

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

Vsebina

Vprašanje

Metka je vodja izmene v robotsko vodenem skladišču. Njeno delo je, da nadzira programerje, ki upravljajo robote-viličarje, ki skladajo zaboje v skladovnice. Janko jo je dolgo prosil, naj mu preskrbi delo programerja v tem skladišču. Končno je Metka le popustila in mu pri direktorju izposlovala zaposlitev. A že takoj prvi dan ga je Janko polomil. Robota je narobe sprogramiral. Tako so zabojniki v skladovnicah, ki jih nadzira Janko, zloženi (levo je naveden ZGORNJI zaboj skladovnice, v TEJ skladovnici so 4 zaboji) 1, 2, 3, 4; namesto 2, 1, 4, 3; ali pa (za 7 zabojev) 1, 2, 3, 4, 5, 6, 7 namesto 2, 1, 4, 3, 6, 5, 7 (po dva in dva zaboja sta torej v napačnem vrstnem redu). Metka mora hitro ukrepati in napisati ustrezen program, ki bo vodil robota, da preložil zaboje v vseh skladovnicah. Robot zna izvajati osnovne operacije nad skladom. Pomagaj Metki in napiši ALGORITEM za vodenje robota, ki v danem skladu preloži elemente tako, da zamenja po dva in dva elementa.

Odgovor

Zabojnikov očitno ni moč direktno preložiti v novo skladovnico tako, da bi bili zloženi po pravilnem vrstnem redu. Ideja je v tem, da robot najprej zabojnike preloži izmenično v dve skladovnici in jih nato ponovno preloži nazaj po pravilnem vrstnem redu. To naredi tako, da ponovno izmenično jemlje zabojnike iz obeh skladovnic vendar mora začeti pri skladovnici, na katero NI naložil zadnjega zabojnika.
Slika1 prikazuje, kakšna bi morala biti skladovnica.

Pravilen sklad
Slika1: Pravilno naložena skladovnica.

Slika2 prikazuje skladovnico, kot jo je zložil Janko.

Napacen sklad
Slika2: Napačno naložena skladovnica.

Prvi korak - razvrščanje

V prvem koraku skladovnico razloži v dve skladovnici tako, da izmenično prelaga v eno in drugo npr. a in b. Pri tem si mora zapomniti, v katero skladovnico je naložil zadnji zabojnik.

Razvrscanje v dva sklada
Slika3: Razvrščanje v dve skladovnici.

Drugi korak - združevanje

V tem koraku vedno jemlje izmenično iz obeh skladovnic, paziti pa mora, da začne pri tisti skladovnici, na katero ni zlagal nazadnje.

Zdruzevanje v pravi sklad
Slika4: Združevanje v pravilno skladovnico.

Testni program PopraviSkladA.java

  1. // program, ki nepravilno naloženo skladovnico popravi
  2. import java.util.Stack;
  3. import javax.swing.*;
  4.  
  5. public class PopraviSkladA {
  6. public static void main(String[] args) {
  7.  
  8. Stack <String> sklad = new Stack <String>();
  9. Stack <String> a = new Stack <String>();
  10. Stack <String> b = new Stack <String>();
  11.  
  12. int koliko = Integer.parseInt(JOptionPane.showInputDialog("Koliko elementov boste vnesli? "));
  13. while ( koliko > 0 ) {
  14. sklad.push(JOptionPane.showInputDialog("Vnesite vrednost elementa v sklad"));
  15. koliko--;
  16. }
  17. System.out.println("Elementi v skladu na zacetku: " + sklad);
  18.  
  19. String element = "";
  20. Boolean zadnji = false; // da vemo kam smo dali na zadnje
  21. while ( !sklad.empty() ) {
  22. element = sklad.pop();
  23. a.push(element);
  24. zadnji = true;
  25. if ( !sklad.empty() ) {
  26. element = sklad.pop();
  27. b.push(element);
  28. zadnji = false;
  29. }
  30. }
  31.  
  32. System.out.println("Elementi trenutno v skladu: " + sklad);
  33. System.out.println("Elementi v skladu a: " + a);
  34. System.out.println("Elementi v skladu b: " + b);
  35.  
  36. if (zadnji) { // ce smo na zadnje dali v a moramo zaceti v b
  37. while ( !a.empty() || !b.empty() ) {
  38. if ( !b.empty() ) {
  39. element = b.pop();
  40. sklad.push(element);
  41. }
  42. if ( !a.empty() ) {
  43. element = a.pop();
  44. sklad.push(element);
  45. }
  46. }
  47. }
  48. else {
  49. while ( !a.empty() || !b.empty() ) {
  50. if ( !a.empty() ) {
  51. element = a.pop();
  52. sklad.push(element);
  53. }
  54. if ( !b.empty() ) {
  55. element = b.pop();
  56. sklad.push(element);
  57. }
  58. }
  59. }
  60.  
  61. System.out.println("Elementi v skladu na koncu: " + sklad);
  62. }
  63. }

Druga varianta

Druga možnost je taka, da uporabimo le en dotatni sklad, na katerega najprej preložimo vse elemente, potem pa jemljemo po dva elementa in ju v obratnem vrstnem redu polagamo na prvi sklad. Pri skladu s sobim številom elementov, bi šlo tudi tako, da bi že v nov sklad jemali elemente po dva in jih prelagali v obratnem vrstnem redu, za sklad z lihim številom elementov pa to žal ne gre oz. bi v tem primeru morali prvi element preložiti direktno na nov sklad. Pri tem bi potrebovali tudi informacijo o velikosti sklada.

Zato v zanki načeloma jemljemo po dva elementa, vendar vedno pred jemanjem drugega preverimo, če sploh obstaja.

Psevdokoda

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

Testni program - PopraviSkladB.java

  1. import java.util.Stack;
  2. import javax.swing.*;
  3.  
  4. public class PreloziSklad {
  5. public static void main(String[] args) {
  6.  
  7. Stack <String> sklad = new Stack <String>();
  8.  
  9. int koliko = Integer.parseInt(JOptionPane.showInputDialog("Koliko elementov boste vnesli? "));
  10. while ( 0 < koliko ) {
  11. sklad.push(JOptionPane.showInputDialog("Vnesite vrednost elementa v sklad"));
  12. koliko--;
  13. }
  14. System.out.println("Elementi v skladi na zacetku: " + sklad);
  15.  
  16. Stack <String> novSklad = new Stack <String>(); // ustvarimo nov sklad
  17. //preložimo vse elemente v novSklad
  18. while (!sklad.empty()) {
  19. novSklad.push(sklad.pop());
  20. }
  21.  
  22. System.out.println("Elementi trenutno v skladu: " + sklad);
  23. System.out.println("Elementi v novem skladu: " + novSklad);
  24.  
  25. String element = ""; // za hranjenje elementov
  26. // ponovno preložimo v prvi sklad
  27. while (!novSklad.empty()) {
  28. element = novSklad.pop();
  29. // ker je lahko tudi liho število elementov, preverjamo
  30. if (!novSklad.empty()) {
  31. sklad.push(novSklad.pop());
  32. }
  33. sklad.push(element);
  34. }
  35.  
  36. System.out.println("Elementi v skladu na koncu: " + sklad);
  37. }
  38. }
Osebna orodja