Izpitno vprašanje RAČ2PRA 2900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 15:57, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
← Prejšnja različica
Različica od 16:00, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
Naslednja različica →
Vrstica 48: Vrstica 48:
trenutna_vsota = S + a[i]; //pogledamo kakšno vsoto dobimo, če prištejemo trenutni element a[i] trenutna_vsota = S + a[i]; //pogledamo kakšno vsoto dobimo, če prištejemo trenutni element a[i]
if(trenutna_vsota>0){ //če je vsota, ki smo jo dobili pozitivna... if(trenutna_vsota>0){ //če je vsota, ki smo jo dobili pozitivna...
- S = S + a[i]; //...element a[i] prištejemo k vsoti+ S = trenutna_vsota; //trenutno vsoto shranimo v spremenljivko S
} }
else{ //če dobimo negativno vsoto, se nam bolj splača začeti od začetka, torej od 0 naprej else{ //če dobimo negativno vsoto, se nam bolj splača začeti od začetka, torej od 0 naprej

Različica od 16:00, 6 april 2007

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

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:

Razloži vsaj dva algoritma za izračun maksimalne vsote podzaporedja v zaporedju celih števil!

Odgovor:

- Imejmo zaporedje celih števil: a1, a2,...,an

- Z S(i,j) označimo vsoto ak, kjer je k = i,...,j

- Radi bi poiskali maksimalno vsoto, ki jo bomo poimenovali vsota_opt

- n je število elementov v tabeli števil


1.ALGORITEM: (Upoštevamo vse vsote)

  1. S_opt = 0; //Na začetku optimalne vsote še nimamo
  2. for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
  3. for(int j=i; j<n; j++){ //pregledamo vsa možna podzaporedja
  4. S = a[i]; //določimo začetek podzaporedja - začetna vsota
  5. }
  6. for(int k=i+1; k<=j; k++){ //dodajamo elemente - izboljšujemo vsoto
  7. S = S + a[k]; //prištevamo elemnte zraven
  8. }
  9. if(S > S_opt) //če najdemo boljšo vsoto...
  10. S_opt = S; //...jo shranimo v spremenljivko S_opt in dobimo novo maksimalno vsoto
  11. }

2.ALGORITEM: (Upoštevamo prejšnje vsote (S_i,j = S_i,j-1 + a_j))

  1. S_opt = 0; //na začetku še nimamo maksimalne vsote
  2. for(int i=0; i<n: i++);{ //sprehodimo se čez tabelo
  3. S = a[i]; //prvi element podzaporedja
  4. if(S > S_opt){ //Če najdemo boljši začetni element...
  5. S_opt = S;//...ga shranimo v spremenljivko S_opt
  6. }
  7. for(j=i+1; j<n; j++){ //pogledamo preostanek tabele
  8. S = S + a[j]; //pogledamo prejšnji element in ga prištejemo vsoti
  9. if(S > S_opt){ //če najdemo boljšo vsoto...
  10. S_opt = S; //...jo shranimo v spremenljivko S_opt
  11. }}}

3.ALGORITEM: (Ali vzamemo zraven i-ti element(S_i = S_i-1 + a_1 ali S_i = 0))

  1. S_opt = 0; //na začetku optimalne vsote še nimamo
  2. S = 0; //vsota je 0
  3. for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
  4. trenutna_vsota = S + a[i]; //pogledamo kakšno vsoto dobimo, če prištejemo trenutni element a[i]
  5. if(trenutna_vsota>0){ //če je vsota, ki smo jo dobili pozitivna...
  6. S = trenutna_vsota; //trenutno vsoto shranimo v spremenljivko S
  7. }
  8. else{ //če dobimo negativno vsoto, se nam bolj splača začeti od začetka, torej od 0 naprej
  9. S = 0; //iščemo naslednje podzaporedje
  10. if(S > S_opt){ //če najdemo boljše podzaporedje...
  11. S_opt = S; //...ga shranimo v spremenljivko S_opt
  12. }

KONKRETEN PRIMER ZA ZADNJI ALGORITEM:

Dano je zaporedje števil: 8,-6,10,-14,13,-5,7,-9,18,-3,2. Sprehodimo se čez tabelo in se na vasakem koraku odločimo, ali bomo element vzeli ali ne:

 1.korak:  8  ... vzamem ... vsota = 8 ... max.vsota = 8 
 2.korak:  -6 ... vzamem ... vsota = 2 ... max.vsota = 8 

//Za negativni element smo se odločili,ker je vsota 8+(-6) pozitivna. Maksimalna vsota pa je 8, kar pomeni, da bi se nam, če bi zdaj končali, bolj izplačalo imeti le prvi element in ne drugega. Zapomnimo si jo za vsak slučaj, če bi bili recimo od zdaj naprej sami negativni elementi, bi bila to optimalna rešitev.

 3.korak: 10 ... vzamem ... vsota = 12 ... max.vsota = 12

//Če bi pod max.vsoto zapisali 18 (8 od prej + 10), bi bilo narobe, saj bi to pomenilo, da smo v zaporedje vzeli 1.in 3.element, 2.pa ne - to pa ne gre, saj v podzaporedju elementov ne izpuščamo!!!

 4.korak: -14 ... ne vzamem ...  vsota = 0 ... max.vsota = 12

//Ker se za element nismo odločili, smo zaključili s podzaporedjem in zdaj bomo poiskali novega. Maksimalna vsota je zaenkrat tista, ki smo jo dobili pri prejšnjem podzaporedju.

 5.korak:  13 ... vzamem ... vsota = 13 ... max.vsota = 13 
 6.korak:  -5 ... vzamem ... vsota =  8 ... max.vsota = 13
 7.korak:   7 ... vzamem ... vsota = 15 ... max.vsota = 15
 8.korak:  -9 ... vzamem ... vsota =  6 ... max.vsota = 15
 9.korak:  18 ... vzamem ... vsota = 24 ... max.vsota = 24
10.korak:  -3 ... vzamem ... vsota = 21 ... max.vsota = 24
11.korak:   2 ... vzamem ... vsota = 23 ... max.vsota = 24

Rešitev je podzaporedje: 13,-5,7,-9,18. Maksimalna vsota je 24.

Osebna orodja