Izpitno vprašanje RAČ2PRA 3000

Iz MaFiRaWiki

Vprašanje

Sestavi javno statično metodo, ki za dano tabelo celih števil vrne podzaporedje z maksimalno vsoto. Pri tem uporabi algoritem časovne zahtevnosti O(n3) in prostorske zahtevnosti O(n2). Najprej generiraj vsote vseh možnih podzaporedij in jih shrani v tabelo. V dodatno tabelo shrani začetke in konce podzaporedij. Nato v tabeli poišči maksimalni element in iz istoležnih indeksov rekonstruiraj ustrezno podzaporedje.

Odgovor

Matematična formulacija problema
Dano je zaporedje celih števil a1, a2, …, an. Naj bo Si,j = vsota ak, k = i, …, j

  • Poišči opt = podzaporedje z maksimalno vsoto
  • 8, -6, 10, -14, 13, -5, 7, -9, 18, -3, 2
  • rešitev 13, -5, 7, -9, 18

Najprej generiramo vsote vseh možnih podzaporedij in jih shrani v tabelo. V dodatno tabelo shranimo začetke in konce podzaporedij, nato v tabeli poiščemo maksimalni element in iz istoležnih indeksov rekonstruiramo ustrezno podzaporedje. Na koncu vrnemo tabelo s ustreznim podzaporedjem.

  1. public static int[] borznikO3(int[] a) {
  2. // algoritem casovne zahtevnosti O(n^3) in
  3. // prostorske zahtevnosti O(n^2)
  4. // vrača optimalno podzaporedje
  5.  
  6. int n = a.length;
  7.  
  8. // tabela vsot vseh možnih podzaporedij
  9. int[] dVsote = new int[n*(n+1)/2];
  10. // tabela začetnih in končnih indeksov podzaporedij
  11. int[][] zacKon = new int[2][n*(n+1)/2];
  12. int katera = 0; // trenutno podzaporedje
  13. for (int i = 0; i < n; i++) {
  14. // i - kje zacnem
  15. for (int j = i; j < n; j++) {
  16. // j - kje neham
  17. int s = a[i];
  18. // vsota od i do j
  19. for (int k = i+1; k <= j; k++)
  20. s = s + a[k];
  21. // zapomnimo si podatke o trenutnem podzaporedju
  22. dVsote[katera]=s;
  23. zacKon[0][katera]=i;
  24. zacKon[1][katera]=j;
  25. katera++;
  26. }
  27. }
  28. // pregledamo vse vsote podzaporedij in si zapomnimo maksimalno
  29. int opt = dVsote[0]; // optimalno (maksimalno) podzaporedje
  30. katera = 0; // indeks optimalnega podzaporedja
  31. for(int i = 1; i < n*(n+1)/2; i++){
  32. int s = dVsote[i];
  33. if (s > opt) { // boljsa vsota! Zapomnimo si podatke
  34. opt = s;
  35. katera = i;
  36. }
  37. }
  38. // sestavimo tabelo z optimalnim podzaporedjem
  39. int odk = zacKon[0][katera]; // začetek podzaporedja
  40. int dok = zacKon[1][katera]; // konec zaporedja
  41. int [] r = new int[dok - odk + 1]; // tabela z elementi podzaporedja
  42. for(int i = odk; i <= dok; i++)
  43. r[i-odk]=a[i];
  44.  
  45. return r; // vrnemo tabelo z elementi podzaporedja
  46. }

Prostorska analiza

  • Podatki: ai
  • Rezultat: r
  • Velikost problema
    • Število podatkov (n)
  • Dodatno:
    • i, j, k, odk, dok, katera (števci)
    • s, opt (vsoti)
    • dVsote (1×n2)
    • zacKon (2×n2)
    • r (maksimalno n)
  • Odvisno od velikosti problema
  • O(n2)

Časovna analiza

  • Velikost problema
    • število podatkov (n)
  • Tipične operacije za problem:
    • seštevanja
    •  ? Primerjanje ?
  • Število primerjanj:
    • i = 1: n primerjanj
    • I = 2: n – 1 primerjanj
    • ....
    • Skupaj: n + (n – 1) + (n – 2) + ... + 2 + 1
    • n * (n + 1) / 2
    • O (n2)
  • Število seštevanj:
    • i = 1
      • Konec
        • j = 1: 0 seštevanj
        • j = 2: 1 seštevanje
        • ...
        • j = n: n - 1 seštevanj
      • Skupaj: 0 + 1 + ... + n – 1 = n * (n – 1) / 2
    • i = 2
      • Konec
        • j = 2: 0 seštevanj
        • j = 3: 1 seštevanje
        • ...
        • j = n: n - 2 seštevanj
      • Skupaj: 0 + 1 + ... + n – 2 = (n – 1) * (n – 2) / 2
    • i = m
      • Konec
        • j = m: 0 seštevanj
        • j = m + 1: 1 seštevanje
        • ...
        • j = n: n – m seštevanj
      • Skupaj: 0 + 1 + ... + n – m = (n – m) * (n – m + 1) / 2
    • i = n - 1
      • Skupaj: 1
    • i = n
      • Skupaj: 0
  • Skupaj: (n * (n – 1) + (n – 1) * (n – 2) + ... + 1 * 2)/ 2 = n3 + ...
  • O(n3)
Osebna orodja