Izpitno vprašanje RAČ2PRA 2900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 10:56, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
← Prejšnja različica
Različica od 11:31, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
Naslednja različica →
Vrstica 7: Vrstica 7:
- Imejmo zaporedje celih števil: a1, a2,...,an - Imejmo zaporedje celih števil: a1, a2,...,an
-- Z vsota(i,j) označimo vsoto ak, kjer je k = i,...,j+- Z S(i,j) označimo vsoto ak, kjer je k = i,...,j
- Radi bi poiskali maksimalno vsoto, ki jo bomo poimenovali vsota_opt - Radi bi poiskali maksimalno vsoto, ki jo bomo poimenovali vsota_opt
Vrstica 15: Vrstica 15:
Primer: Primer:
-Dano je zaporedje števil: 8,-6,10,-14,13,-5,7,-9,18,-3,2+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. Vsota podzaporedja 13,-5,7,-9,18 je 24. To je hkrati tudi rešitev, oziroma maksimalna vsota.
-1.ALGORITEM: (upoštevamo vse vsote)+ 
-<java>vsota_opt = 0; //Na začetku optimalne vsote še nimamo+1.ALGORITEM: (Upoštevamo vse vsote)
 +<java>S_opt = 0; //Na začetku optimalne vsote še nimamo
for(int i=0; i<n; i++){ //sprehodimo se čez tabelo for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
- for(int j=i; j<n; j++){ //izberemo podzaporedje+ for(int j=i; j<n; j++){ //pregledamo vsa možna podzaporedja
- vsota = a[i]; + S = a[i]; //določimo začetek podzaporedja - začetna vsota
} }
//vsota od i do j: //vsota od i do j:
- for(int k=i+1; k<=j; k++){ //s premikanjem kazalca k pregledujemo še druga podzaporedja - izboljšujemo vsoto+ for(int k=i+1; k<=j; k++){ //dodajamo elemente - izboljšujemo vsoto
- vsota = vsota + a[k];+ S = S + a[k]; //prištevamo elemnte zraven
} }
-if(vsota > vsota_opt) //če najdemo boljšo vsoto+if(S > S_opt) //če najdemo boljšo vsoto...
-vsota_opt = vsota;+S_opt = S; //...jo shranimo v spremenljivko S_opt
} }
</java> </java>
-2.ALGORITEM: +2.ALGORITEM: (Ali vzamemo zraven i-tega)
<java>vsota_opt = 0; //na začetku optimalne vsote še nimamo <java>vsota_opt = 0; //na začetku optimalne vsote še nimamo
for(int i=0; i<n; i++){ //sprehodimo se čez tabelo for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
Vrstica 44: Vrstica 46:
vsota_opt = vsota; vsota_opt = vsota;
} }
 +</java>
 +
 +3.ALGORITEM: (Upoštevamo prejšnje vsote)
 +<java>vsota_opt = 0; //na začetku še nimamo maksimalne vsote
 +for(int i=0; i<n: i++);{
 +}
</java> </java>

Različica od 11:31, 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. //vsota od i do j:
  7. for(int k=i+1; k<=j; k++){ //dodajamo elemente - izboljšujemo vsoto
  8. S = S + a[k]; //prištevamo elemnte zraven
  9. }
  10. if(S > S_opt) //če najdemo boljšo vsoto...
  11. S_opt = S; //...jo shranimo v spremenljivko S_opt
  12. }

2.ALGORITEM: (Ali vzamemo zraven i-tega)

  1. vsota_opt = 0; //na začetku optimalne vsote še nimamo
  2. for(int i=0; i<n; i++){ //sprehodimo se čez tabelo
  3. if(a[i]>0){ //če je element v tabeli pozitiven...
  4. vsota = vsota + a[i]; //...ga prištejemo k vsoti...
  5. }
  6. else ... ? //pomoc:-)
  7. }
  8. if(vsota > vsota_opt){
  9. vsota_opt = vsota;
  10. }

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

  1. vsota_opt = 0; //na začetku še nimamo maksimalne vsote
  2. for(int i=0; i<n: i++);{
  3. }
Osebna orodja