Izpitno vprašanje RAČ2PRA 8200

Iz MaFiRaWiki

Vprašanje

Imamo dva sklada, v katerih so elementi urejeni nepadajoče. Sestavi algoritem, ki s pomočjo osnovnih operacij nad vrsto in skladom sestavi novo vrsto, kjer so elementi (iz prvih dveh skladov) prav tako urejeni naraščajoče.

Odgovor

Ideja rešitve je ta, da sklada zlijemo v vrsto. S tem bomo dobili elemente urejene enako (največji na začetku). Ko pa jih preložimo v sklad, bodo urejeni tako, da bo najmanjši zgoraj. Če pa jih še enkrat preložimo v sklad, bodo urejeni prav.

No, resnici na ljubo je tako zlivanje, kot zgoraj opisano motoviljenje z vrsto in skladom malček nerodno. Ampak načeloma je prav. priporočam pa, da kdo drug dopiše še en, malo bolj premišljen postopek (tega kar pustimo, saj je načeloma ok, a ..)!

  1.  
  2. public class SkladVrsta{
  3. public static Vrsta<E> skladVrsta(Sklad<E> a, Sklad<E> b) throws Exception {
  4. Vrsta<E> nova = new Vrsta<E>();
  5. Sklad<E> pom = new Sklad<E>();
  6.  
  7. while(!a.prazen()) {
  8. //ce je b prazen, samo zlozimo elemente iz a v novo vrsto
  9. if(b.prazen()) {
  10. nova.vstavi(a.vrh());
  11. a.odstrani();
  12. }
  13. //ce pa b ni prazen, primerjamo velikosti
  14. else {
  15. if(a.vrh() > b.vrh()) {
  16. nova.vstavi(a.vrh());
  17. a.odstrani();
  18. }
  19. else {
  20. nova.vstavi(b.vrh());
  21. b.odstrani();
  22. }
  23. }
  24. }
  25. //ce je v skladu b vec elementov, jih moramo na koncu se zloziti v novo vrsto
  26. while(!b.prazen()) {
  27. nova.vstavi(b.vrh());
  28. b.odstrani();
  29. }
  30. while(!nova.prazna()){
  31. pom.vstavi(nova.zacetek());
  32. nova.odstrani();
  33. }
  34. while(!pom.prazen()){
  35. nova.vstavi(pom.vrh());
  36. pom.odstrani();
  37. }
  38. return nova;
  39. }
  40. }
Osebna orodja