Izpitno vprašanje RAČ2PRA 5400

Iz MaFiRaWiki

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

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

Državni uradnik ima na mizi goro papirjev. Za vsakega ve, koliko časa mu bo vzela obdelava (denimo, da je to število, ki predstavlja čas obdelave v sekundah). Ker je uradnik len in urad plača uradnike po številu obdelanih papirjev, bi rad najprej obdelal tiste papirje, katerih obdelava mu ne bo vzela veliko časa (in druge po možnosti poslal naslednjemu uradniku). Zato želi narediti dva kupa: v enem naj bodo papirji, katerih čas obdelave je večji od povprečnega, v drugem pa vsi preostali. Ker je vrstni red papirjev važen, morajo biti papirji znotraj kupa urejeni po istem vrstem redu kot v začetnem kupu. Pomagaj mu pri tem mukotrpnem sortiranju! Ime funkcije naj bo public static void sortirajPapirje(Sklad s1, Sklad s2). Sklad s1 je vhodni sklad in vanj se shranijo papirji z nižjim časom obdelave od povprečnega, v s2 pa papirji z večjim časom obdelave. Pazi na to, da so vsi podatki v skladu tipa niz in jih je za primerjanje potrebno pretvoriti v število!

Odgovor

Najprej moramo izračunati povprečni čas obdelave enega papirja, zato se sprehodimo čez dani sklad (seveda moramo elemente pretvoriti iz nizov v števila) in seštevamo čase obdelav, elemente pa prelagamo v pomožni sklad. Na koncu vsoto delimo s številom elementov in dobimo povprečni čas.
Nato se sprehodimo čez pomožni sklad. Glede na to, ali je število manjše ali večje od povprečnega časa, element preložimo v prvi oz. drugi sklad.

  1. public static void sortirajPapirje(Sklad<String> s1, Sklad<String> s2) throws Exception{
  2. Sklad<String> pomozni = new Sklad<String>();
  3. int vsota = 0;
  4. int stevec = 0;
  5. while(!s1.prazen()){
  6. // niz spremenimo v število
  7. int trenutni = Integer.parseInt(s1.vrh());
  8. // prištejemo čas obdelave trenutnega papirja
  9. vsota = vsota + trenutni;
  10. stevec++;
  11. // vstavimo vrhnji element v pomožni sklad
  12. pomozni.vstavi(s1.vrh());
  13. // odstranimo element iz sklada
  14. s1.odstrani();
  15. }
  16. // povprečni čas obdelave enega papirja
  17. double povprecni = vsota/stevec;
  18. while(!pomozni.prazen()){
  19. // niz spremenimo v število
  20. int trenutni = Integer.parseInt(pomozni.vrh());
  21. // preverimo ali je trenutni vecji ali manjši od povprečnega časa in ga temu primerno vstavimo v s1 oz. s2
  22. if(trenutni<=povprecni) s1.vstavi(pomozni.vrh());
  23. else s2.vstavi(pomozni.vrh());
  24. pomozni.odstrani();
  25. }
  26. }

Testni program:

  1. public static void main(String[] args) throws Exception{
  2. Sklad<String> a = new Sklad<String>();
  3. Sklad<String> b = new Sklad<String>();
  4. a.vstavi("10");
  5. a.vstavi("9");
  6. a.vstavi("8");
  7. a.vstavi("7");
  8. a.vstavi("6");
  9. a.vstavi("5");
  10. a.vstavi("4");
  11. a.vstavi("3");
  12. a.vstavi("2");
  13. a.vstavi("1");
  14. // povprečje teh desetih števil je 5.5
  15. sortirajPapirje(a,b);
  16. System.out.println("Papirji, katerih čas obdelave je manjši od povprečnega:");
  17. a.izpis();
  18. System.out.println("Papirji, katerih čas obdelave je večji od povprečnega:");
  19. b.izpis();
  20. }

Izpiše:

 > java Vpr_5400
Papirji, katerih čas obdelave je manjši od povprečnega: 
1 2 3 4 5 
Papirji, katerih čas obdelave je večji od povprečnega:
6 7 8 9 10
Osebna orodja