Izpitno vprašanje RAČ2PRA 8100

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka JožicaPavlovič.

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

Imamo dve vrsti, v katerih so elementi urejeni naraščajoče. Sestavi algoritem, ki s pomočjo osnovnih operacij nad vrsto sestavi novo vrsto, kjer so elementi (iz prvih dveh vrst) urejeni prav tako naraščajoče.

Odgovor

Iz vrst v1 in v2, v kateri so elementi urejeni naraščajoče, moramo sestaviti vrsto, v kateri bodo prav tako elementi urejeni naraščajoče. Najprej nastavimo pogoj (zanko while), da obe vrsti nista prazni. Tako bomo prelagali elemente iz ene in druge vrste, dokler ne bosta prazni. Nato ločimo tri pogoje:

1. če je začetni element v vrsti v1 večji od začetnega elementa vrste v2, damo element iz v1 v novo vrsto

2. če sta začetna elementa iz v1 in v2 enaka, ju damo izmenično v novo vrsto

3. če je začetni element v vrsti v2 večji od začetnega elementa vrste v1, damo element iz v2 v novo vrsto

Ko preverimo vse te pogoje, moramo še preveriti, če je v kateri vrsti ostal še kakšen element. Če je, ga damo v novo vrsto.

  1.  
  2. public class Vrsta1{
  3. public static Vrsta<Integer> uredi(Vrsta<Integer> v1, Vrsta<Integer> v2){
  4. Vrsta<Integer> urejena = new Vrsta<Integer>();
  5. while((!v2.prazna()) || (!v1.prazna())){
  6. //elemente moramo prestaviti iz obeh vrst zato jih prelagamo dokler obe
  7. //vrsti nista prazni
  8. if(!v1.prazna()&& !v2.prazna()){
  9. // locimo tri pogoje če je zacetek v1 najmanjsi vstavimo zacetek v1 in ta
  10. // zacetek odstranimo iz vrste v1
  11. if(v1.zacetek () < v2.zacetek ()){
  12. urejena.vstavi(v1.zacetek ());
  13. v1.odstrani();
  14. }
  15. //če sta začetka enaka vstavimo oba začetka,saj vemo da je vrsta urejena nepadajoče
  16. if(v1.zacetek () == v2.zacetek ()){
  17. urejena.vstavi(v1.zacetek ());
  18. urejena.vstavi(v2.zacetek ());
  19. v1.odstrani();
  20. v2.odstrani();
  21. }
  22. // če je začetek v2 večji od v1 vstavimo začetek v2
  23. if(v1.zacetek () > v2.zacetek ()){
  24. urejena.vstavi(v2.zacetek ());
  25. v2.odstrani();
  26. }
  27. }
  28. // če je ena vrsta prazna in druga še ni prazna vstavljamo elemente
  29. // iz neprazne vrste v urejeno vrsto
  30. if(v1.prazna()&& !v2.prazna()){
  31. urejena.vstavi(v2.zacetek());
  32. v2.odstrani();
  33. }
  34. if(v2.prazna()&& !v1.prazna()){
  35. urejena.vstavi(v1.zacetek());
  36. v1.odstrani();
  37. }
  38. }
  39. return urejena ;
  40. }
  41. //preizkusimo metodo
  42. public static void main(String[] args) {
  43. Vrsta<Integer> v1 = new Vrsta<Integer>();
  44. v1.vstavi(1);
  45. v1.vstavi(2);
  46. v1.vstavi(14);
  47. v1.vstavi(18);
  48. v1.vstavi(25);
  49. Vrsta<Integer> v2 = new Vrsta<Integer>();
  50. v2.vstavi(0);
  51. v2.vstavi(10);
  52. v2.vstavi(13);
  53. v2.vstavi(20);
  54. v2.vstavi(21);
  55. System.out.println(uredi(v1,v2));
  56. //vrne vrsto: - 0 - 1 - 2 - 10 - 13 - 14 - 18 - 20 - 21 - 25
  57. }
  58. }
Osebna orodja