Izpitno vprašanje RAČ2PRA 2900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 10:46, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
← Prejšnja različica
Različica od 10:49, 6 april 2007
Skalan (Pogovor | prispevki)
Odgovor:
Naslednja različica →
Vrstica 18: Vrstica 18:
Vsota podzaporedja 13,-5,7,-9,18 je 24 Vsota podzaporedja 13,-5,7,-9,18 je 24
-1.ALGORITEM: +1.ALGORITEM: (upoštevamo vse vsote)
<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

Različica od 10:49, 6 april 2007

Vprašanje:

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

Odgovor:

- Imejmo zaporedje števil: a1, a2, a3,...

- Z vsota(i,j) označimo vsoto ai,...,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

1.ALGORITEM: (upoštevamo vse vsote)

  1. vsota_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++){ //izberemo podzaporedje
  4. vsota = a[i];
  5. }
  6. //vsota od i do j:
  7. for(int k=i+1; k<=j; k++){ //s premikanjem kazalca k pregledujemo še druga podzaporedja - izboljšujemo vsoto
  8. vsota = vsota + a[k];
  9. }
  10. if(vsota > vsota_opt) //če najdemo boljšo vsoto
  11. vsota_opt = vsota;
  12. }

2.ALGORITEM:

  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. }
Osebna orodja