Izpitno vprašanje RAČ2PRA 2900

Iz MaFiRaWiki

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 S_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, i označuje začetek zaporedja
  3. for(int j=i; j<n; j++){ //pregledamo vsa možna podzaporedja z začetkom i, j označuje konec podzaporedja
  4. S = a[i]; //določimo začetek podzaporedja - začetna vsota
  5. for(int k=i+1; k<=j; k++){ //dodajamo elemente - izboljšujemo vsoto
  6. S = S + a[k]; //prištevamo elemnte zraven
  7. }
  8. if(S > S_opt) //če najdemo boljšo vsoto...
  9. S_opt = S; //...jo shranimo v spremenljivko S_opt in dobimo novo maksimalno vsoto
  10. } // zaporedje z začetkom i in koncem j, torej S[i,j]
  11. } // vsa zaporedja z začetkom i
  12. return S_opt;

2.ALGORITEM: (Upoštevamo prejšnje vsote (S(i,j) = S(i,j-1) + aj))

  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 je boljše že podzaporedje, ki vsebuje le a[i]
  5. S_opt = S;//...ga shranimo v spremenljivko S_opt
  6. for(j=i+1; j<n; j++){ //še podzaporedja z začetkom pri i, ki imajo konec pri j
  7. S = S + a[j]; // S(i,j) = S(i,j-1) + a[j]
  8. if(S > S_opt){ //če najdemo boljšo vsoto...
  9. S_opt = S; //...jo shranimo v spremenljivko S_opt
  10. }
  11. }
  12. return S_opt;


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. // nadaljevanje je tipični primer, kako se NE piše komentarjev!!
  3. // Ti komentarji nič ne povejo ZAKAJ smo določeno stvar naredili, so le v slovenščini zapisani pomeni javanskih kod
  4. S = 0; //vsota je 0
  5. for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
  6. int trenutna_vsota = S + a[i]; //pogledamo kakšno vsoto dobimo, če prištejemo trenutni element a[i]
  7. if(trenutna_vsota>0){ //če je vsota, ki smo jo dobili pozitivna...
  8. S = trenutna_vsota; //trenutno vsoto shranimo v spremenljivko S
  9. }
  10. else{ //če dobimo negativno vsoto, se nam bolj splača začeti od začetka, torej od 0 naprej
  11. S = 0; //iščemo naslednje podzaporedje
  12. if(S > S_opt){ //če najdemo boljše podzaporedje...
  13. S_opt = S; //...ga shranimo v spremenljivko S_opt
  14. }

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