Izpitno vprašanje RAČ2PRA 11100

Iz MaFiRaWiki

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

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

Elementi so shranjeni v kopici. Sestavi algoritem s katerim jih preložiš v tabelo tako, da so v tabeli urejeni.

Odgovor

Postopek:

  • imamo tabelo, ki predstavlja kopico, z n elementi
  • vemo da je prvi element tabele (kopica[1]) max elemet tabele
  • zamenjamo prvi in zadnji element tabele, kopica[1] in kopica[n]
  • sedaj element kopica[1] potopimo na ustrezno mesto v kopici oziroma v tabeli, ki ima sedaj n - 1 elementov (sedaj je kopica: kopica[1],..., kopica[n - 1])
  • zamenjamo podatka kopica[1] in kopica[n - 1]
  • zopet potopimo vrhnji elemen na ustrezno mesto v kopici
  • sedaj ima kopica [n - 2] elementa (kopica je: kopica[1],..., kopica[n - 2])
    • kopica[n] je največji element v kopici, kopica[n - 1] pa je drugi največji element v kopici
  • ponovno zamenjamo podatka kopica[1] in kopica[n - 2]
  • potopimo vrhnji elemen na ustrezno mesto v kopici
  • sedaj ima kopica n - 3 elementi (kopica je: kopica[1],..., kopica[n - 3])
  • ...
  • tako ponavljamo doker ne pridemo od kopica[2] elementa


Algoritem

  1. // sprehodimo se po tabeli
  2. for(int i = 1; i <= n - 1; i++){
  3. // zamenjamo prvi in zadnji element
  4. element = kopica[1]; // v element shranimo prvi element kopice, za katerega vemo da je max
  5. tab[1] = kopica[n - i + 1]; // novi prvi element v tabeli
  6. tab[n - i + 1] = element; // novi zadnji element v tabeli
  7.  
  8. // potapljamo novi prvi element v smeri največjega sina
  9. for(int j = 1; j <= n - i + 1; j++){
  10. leviSin = tab[2 * j];
  11. desniSin = tab[2 * j +1 ];
  12. oce = tab[j];
  13.  
  14. // ponavljamo dokler je kandidat za sina znotraj tabele
  15. while(2 * j + 1 <= n - i + 1){
  16. // pregledamo oceta in sinove
  17.  
  18. // oce je manjsi od obeh sinov
  19. if(oce < leviSin && oce < desniSin){
  20.  
  21. // levi sin je manjsi od desnega sina
  22. if(leviSin < desniSin){
  23. // zamenjamo oceta in desnega sina
  24. pom = oce;
  25. oce = desniSin;
  26. desniSin = pom;
  27. }
  28. // levi sin je vecji od desnega
  29. else if(leviSin >= desniSin){
  30. // zamenjamo oceta in levega sina
  31. pom = oce;
  32. oce = leviSin;
  33. leviSin = pom;
  34. }
  35. }
  36.  
  37. // oce je manjsi od levega sina, a je vecji od desnega sina
  38. if(oce < leviSin && oce > desniSin){
  39. // zamenjamo oceta in levega sina
  40. pom = oce;
  41. oce = leviSin;
  42. leviSin = pom;
  43. }
  44.  
  45. // oce manjsi od desnega sina, a vecji od levega sina
  46. if else(oce > leviSin && oce < desniSin){
  47. // zamenjamo oceta in desnega sina
  48. pom = oce;
  49. oce = desniSin;
  50. desniSin = pom;
  51. }
  52.  
  53. // oce je vecji od sinov
  54. else {
  55. // nic ne naredimo
  56. // pustimo kakor je
  57. }
  58. j++;
  59. } // while
  60. // for od potapljanja
  61. // for od sprehajanja po tabeli

Primer:

Imamo tabelo, ki predstavlja maksimalno kopico, kar pomeni da je prvi element v tabeli max element:

100 80 60 80 20 40 55 30 30 10 12 36


Elementi so v tabeli, ki predstavlja kopici, indeksirani od indeksa 1 pa do indeksa 12.


1.korak:

  • Kot smo že zgoraj omenili, je prvi element v kopici oz. v tabeli max element v kopici.
  • Zamenjamo prvi (kopica[i]) in zadnji(kopica[n]) element
    • v našem primeru zamenjamo 100 in 36:
36 80 60 80 20 40 55 30 30 10 12 100


  • Prvih n - 1 (v našem primeru je to prvih 11 elementov) elementov bo predstavljalo kopico, n-ti (12ti) element pa je že urejeni del.
  • Sedaj potopimo prvi element v smeri največjega sina in dobimo kopico:
80 80 60 36 20 40 55 30 30 10 12 100



2.korak:

  • Ponovno zamenjamo prvi in zadnji element kopice, ki ima sedaj n -1 (11) elementov.
    • prvi element je kopica[1] (80) in zadnji je kopica[n - 1] (12)
  • Zadnji element kopice je na n-1 (11) mestu:
  • v spodnji tabeli, sta elementa že zamenjena
12 80 60 36 20 40 55 30 30 10 80 100


  • Prvi element potapljamo v smeri največjega sina
  • ko element potopimo in nimamo več sinovov za potapljanje, prvih n - 2 (10) elementov tabele predstavlja kopico.
  • Zadnja dva elementa pa sta že urejeni del tabele:
80 36 60 30 20 40 55 12 30 10 80 100



3.korak:

  • Ponovno zamenjamo prvi in zadnji element kopice, torej kopica[1](80) in kopica[n-2](kopica[10])
  • zadnjega odstranimo, tako da imamo sedaj n - 3 elementov v nanovo dobljeni tabeli:
10 36 60 30 20 40 55 12 30 80 80 100


  • S tem so zadnji trije elementi tabele že urejeni del tabele.
  • Da bo prvih n - 3 (9) elementov kopica, prvi element potopimo v smeri največjega sina:
60 36 55 30 20 40 10 12 30 80 80 100



4.korak:

  • Zamenjamo prvi in zadnji element, kar pomeni da zamenjamo kopica[1](60) in kopica[n - 3](kopica[9](30)).
  • Zadnji štirje elementi so že urejeni del tabele:
30 36 55 30 20 40 10 12 60 80 80 100


  • Da bo prvih n - 4 = 8 elementov kopica, prvi element potopimo v smeri največjega sina:
55 36 40 30 20 30 10 12 60 80 80 100



5.korak:

  • Zamenjamo prvi in zadnji element, kar pomeni da zamenjamo kopica[1](55) in kopica[n -4](kopica[8])(12).
  • Zadnjih pet elementov je že urejeni del tabele:
12 36 40 30 20 30 10 55 60 80 80 100


  • Da bo prvih n - 5 = 7 elementov kopica, prvi element potopimo v smeri največjega sina:
40 36 30 30 20 12 10 55 60 80 80 100



6.korak:

  • Zamenjamo prvi in zadnji element, kar pomeni da zamenjamo kopica[1](40) in kopica[n -5](10).
  • V delu tabele, ki predstavlja kopico, je sedaj n - 6 = 6 elemenotv.
  • Zadnji šest elementov so že urejeni del tabele:
10 36 30 30 20 12 40 55 60 80 80 100


  • Da bo prvih n - 6 elementov kopica, prvi element potopimo v smeri največjega sina:
36 30 30 10 20 12 40 55 60 80 80 100



7.korak:

  • Zamenjamo prvi in zadnji element, kar pomeni da zamenjamo kopica[1](36) in kopica[n - 6](12).
  • V delu tabele, ki predstavlja kopico, je sedaj n - 7 = 5 elemenotv.
  • Zadnjih sedem elementov je že urejeni del tabele:
12 30 30 10 20 36 40 55 60 80 80 100


  • Da bo prvih n - 7 = 5 elementov kopica, prvi element potopimo v smeri največjega sina:
30 20 30 10 12 36 40 55 60 80 80 100



8.korak:

  • Zamenjamo prvi (kopica[1](30)) in zadnji (kopica[n - 7](12)) element kopice.
  • Elementi na indeksih od 5 - 12 je že urejeni del tabele:
12 20 30 10 30 36 40 55 60 80 80 100


  • * Da bo prvih n - 8 (prvi 4 elementi) elementov kopica, prvi element potopimo v smeri največjega sina:
    sina:
30 20 12 10 30 36 40 55 60 80 80 100



9.korak:

  • Zamenjamo prvi in zadnji element kopice, kar pomeni da zamenjamo kopica[1](30) in kopica[4](10).
  • Zadnjih 8 elementov tabele, so že urejeni del tabele.
10 20 12 30 30 36 40 55 60 80 80 100


  • S tem je zadnjih 9 elementov urejenih.
  • Da bodo prvih trije elementi tabele kopica, prvi element potopimo v smeri največjega sina:
20 10 12 30 30 36 40 55 60 80 80 100



10.korak:

  • Zamenjamo prvi(kopica[1] (20)) in tretji (kopica[3] = kopica[n - 9] (12)) element kopice
  • Zadnjih devet elementov tabele, je urejeni del tabele
12 10 20 30 30 36 40 55 60 80 80 100


  • S tem je zadnji 10 elementov urejenih.
  • Da bosta prva dva elementa tabele predstavljala kopico, prvi element potopimo v smeri največjega sina:
12 10 20 30 30 36 40 55 60 80 80 100



11.korak:

  • Zamenjamo prvi(kopica[1] (12)) in drugi(kopica[2] = kopica[n - 10] (10)) element kopice
  • S tem smo tabelo uredili do konca.


10 12 20 30 30 36 40 55 60 80 80 100


Osebna orodja