Izpitno vprašanje RAČ2PRA 2900

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 16:38, 5 april 2007
Skalan (Pogovor | prispevki)

← Prejšnja različica
Različica od 16:43, 5 april 2007
Skalan (Pogovor | prispevki)

Naslednja različica →
Vrstica 1: Vrstica 1:
-[Vprašanje:]+=Vprašanje:=
Razloži vsaj dva algoritma za izračun maksimalne vsote podzaporedja v zaporedju celih števil! Razloži vsaj dva algoritma za izračun maksimalne vsote podzaporedja v zaporedju celih števil!
-[Odgovor:]+=Odgovor:=
- Imejmo zaporedje števil: a1, a2, a3,... - Imejmo zaporedje števil: a1, a2, a3,...

Različica od 16:43, 5 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:

  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 = vsota + a[i]; //seštejemo vrednosti
  5. }
  6. for(int k=i+1; k<=j; k++){ //s premikanjem kazalca k pregledujemo še druga podzaporedja - izboljšujemo vsoto
  7. vsota = vsota + a[k];
  8. }
  9. if(vsota > vsota_opt)
  10. vsota_opt = vsota;
  11. }

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