Izpitno vprašanje RAČ2PRA 2900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 11:31, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
← Prejšnja različica
Različica od 12:54, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
Naslednja različica →
Vrstica 26: Vrstica 26:
S = a[i]; //določimo začetek podzaporedja - začetna vsota S = a[i]; //določimo začetek podzaporedja - začetna vsota
} }
-//vsota od i do j: 
for(int k=i+1; k<=j; k++){ //dodajamo elemente - izboljšujemo vsoto for(int k=i+1; k<=j; k++){ //dodajamo elemente - izboljšujemo vsoto
S = S + a[k]; //prištevamo elemnte zraven S = S + a[k]; //prištevamo elemnte zraven
Vrstica 35: Vrstica 34:
</java> </java>
-2.ALGORITEM: (Ali vzamemo zraven i-tega)+2.ALGORITEM: (Ali vzamemo zraven i-ti element)
-<java>vsota_opt = 0; //na začetku optimalne vsote še nimamo+<java>S_opt = 0; //na začetku optimalne vsote še nimamo
 +S = 0;
for(int i=0; i<n; i++){ //sprehodimo se čez tabelo for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
- if(a[i]>0){ //če je element v tabeli pozitiven...+ trenutna_vsota = S + a[i];
- vsota = vsota + a[i]; //...ga prištejemo k vsoti...+ if(trenutna_vsota>0){ //če je vsota, ki smo jo dobili pozitivna...
 + S = S + a[i]; //...element a[i] prištejemo k vsoti
} }
- else ... ? //pomoc:-) + else{ //če dobimo negativno vsoto, se nam bolj splača začeti od začetka, torej od 0 naprej
-}+S = 0;
-if(vsota > vsota_opt){+if(S > S_opt){
-vsota_opt = vsota;+S_opt = S;
} }
</java> </java>
3.ALGORITEM: (Upoštevamo prejšnje vsote) 3.ALGORITEM: (Upoštevamo prejšnje vsote)
-<java>vsota_opt = 0; //na začetku še nimamo maksimalne vsote+<java>S_opt = 0; //na začetku še nimamo maksimalne vsote
-for(int i=0; i<n: i++);{+for(int i=0; i<n: i++);{ //sprehodimo se čez tabelo
-} + S = a[i]; //prvi element podzaporedja
-</java>+ if(S > S_opt){ //poskušamo najti boljši začetni element
 + S_opt = S;
 + }
 + for(j=i+1; j<n; j++){ //pogledamo preostanek tabele
 + S = S + a[j]; //seštejemo elemente
 + if(S > S_opt){ //če najemo boljšo vsoto...
 + S_opt = S; //...jo shranimo v spremenljivko S_opt
 +}}}</java>

Različica od 12:54, 6 april 2007

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

Primer:

Dano je zaporedje števil: 8,-6,10,-14,13,-5,7,-9,18,-3,2.

Vsota podzaporedja 13,-5,7,-9,18 je 24. To je hkrati tudi rešitev, oziroma maksimalna vsota.


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
  11. }

2.ALGORITEM: (Ali vzamemo zraven i-ti element)

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

3.ALGORITEM: (Upoštevamo prejšnje vsote)

  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){ //poskušamo najti boljši začetni element
  5. S_opt = S;
  6. }
  7. for(j=i+1; j<n; j++){ //pogledamo preostanek tabele
  8. S = S + a[j]; //seštejemo elemente
  9. if(S > S_opt){ //če najemo boljšo vsoto...
  10. S_opt = S; //...jo shranimo v spremenljivko S_opt
  11. }}}
Osebna orodja