Clasa a 8-a lecția 4 - 14 oct 2015

From Algopedia
Revision as of 11:50, 29 October 2015 by Dan (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

2018 - The Debut Album

Enunț: 2018 - The Debut Album

Implementare recursivă

#include <cstdio>

#define MOD 1000000007

int limite[2];

// Calculează numărul de albume cu un număr dat de piese,
// respectând restricțiile din enunț care încep cu un anumit
// tip de piesă dat
int nrAlbume(int piese, int prim) {
  if (piese == 0) {
    // La limită, pot crea un singur album cu 0 piese.
    // Această valoare se stabilește astfel încât, atunci
    // când este interogată de cazul general (de mai jos)
    // să conducă la obținerea rezultatului corect.
    return 1;
  } else {
    int i;
    int raspuns = 0;
    // i reprezintă numărul de piese de același tip cu care
    // încep albumele pe care le număr
    for (i = 1; i <= limite[prim] && i <= piese; i++) {
      raspuns += nrAlbume(piese - i, 1 - prim);
      raspuns %= MOD;
    }
    return raspuns;
  }
}

// Calculează numărul de albume cu un număr dat de piese,
// respectând restricțiile din enunț
int nrAlbume(int piese) {
  return nrAlbume(piese, 0) + nrAlbume(piese, 1);
}

int main() {
  int N;
  scanf("%d %d %d", &N, &limite[0], &limite[1]);
  printf("%d\n", nrAlbume(N));
  return 0;
}

Această implementare, deși corectă, are un timp de execuție exponențial, deoarece problema este împărțită în subprobleme care la rândul lor sunt împărțite în subprobleme și așa mai departe.

Implementare cu memoizare

#include <cstdio>

#define MOD 1000000007
#define MAX_PIESE 50000

int limite[2];

int NrAlbume[1 + MAX_PIESE][2];

// Calculează numărul de albume cu un număr dat de piese,
// respectând restricțiile din enunț care încep cu un anumit
// tip de piesă dat
int nrAlbume(int piese, int prim) {
  if (NrAlbume[piese][prim] == 0) {
    if (piese == 0) {
      // La limită, pot crea un singur album cu 0 piese.
      // Această valoare se stabilește astfel încât, atunci
      // când este interogată de cazul general (de mai jos)
      // să conducă la obținerea rezultatului corect.
      NrAlbume[piese][prim] = 1;
   } else {
      int i;
      int raspuns = 0;
      // i reprezintă numărul de piese de același tip cu care
      // încep albumele pe care le număr
      for (i = 1; i <= limite[prim] && i <= piese; i++) {
        raspuns += nrAlbume(piese - i, 1 - prim);
        raspuns %= MOD;
      }
      NrAlbume[piese][prim] = raspuns;
    }
  }
  return NrAlbume[piese][prim];
}

// Calculează numărul de albume cu un număr dat de piese,
// respectând restricțiile din enunț
int nrAlbume(int piese) {
  return nrAlbume(piese, 0) + nrAlbume(piese, 1);
}

int main() {
  int N;
  scanf("%d %d %d", &N, &limite[0], &limite[1]);
  printf("%d\n", nrAlbume(N));
  return 0;
}

Observăm că numărul de subprobleme distincte pe care trebuie să le rezolvăm este polinomial, iar algoritmul inițial calcula soluția pentru multe dintre aceste subprobleme de mai multe ori.

Aplicăm tehnica memoizării: Pornind de la aceste observații, ne dăm seama că putem stoca rezultatele tuturor subproblemelor și, de fiecare dată când este necesară reutilizarea rezultatului unei subprobleme calculată anterior vom folosi valoarea stocată după calculul inițial.

Astfel, timpul de execuție este redus de la exponențial la polinomial.

Optimizarea soluției

În prima etapă rescriem codul pentru tratarea cazului general al recurenței sub forma unei funcții pe care o vom optimiza ulterior.

#include <cstdio>

#define MOD 1000000007
#define MAX_PIESE 50000

int limite[2];

int NrAlbume[1 + MAX_PIESE][2];

int max(int a, int b) {
  return a > b ? a : b;
}

int nrAlbume(int piese, int prim);

// Calculează numărul de albume cu un număr de piese dat
// printr-un interval, respectând restricțiile din enunț
// care încep cu un anumit tip de piesă dat.
int sumaNrAlbume(int piese1, int piese2, int prim) {
  int i;
  int raspuns = 0;
  for (i = piese1; i <= piese2; i++) {
    raspuns += nrAlbume(i, prim);
    raspuns %= MOD;
  }
  return raspuns;
}

// Calculează numărul de albume cu un număr dat de piese,
// respectând restricțiile din enunț care încep cu un anumit
// tip de piesă dat.
int nrAlbume(int piese, int prim) {
  if (NrAlbume[piese][prim] == 0) {
    if (piese == 0) {
      // La limită, pot crea un singur album cu 0 piese.
      // Această valoare se stabilește astfel încât, atunci
      // când este interogată de cazul general (de mai jos)
      // să conducă la obținerea rezultatului corect.
      NrAlbume[piese][prim] = 1;
   } else {
      NrAlbume[piese][prim] = sumaNrAlbume(
    		  max(0, piese - limite[prim]), piese - 1, 1 - prim);
    }
  }
  return NrAlbume[piese][prim];
}

Rescriem din nou funcția într-o formă cu mai puțini parametri.

// Calculează numărul de albume cu un număr de piese dat
// printr-un interval de forma [0, piese], respectând restricțiile
// din enunț care încep cu un anumit tip de piesă dat.
int sumaNrAlbume(int piese, int prim) {
  int i;
  int raspuns = 0;
  for (i = 0; i <= piese; i++) {
    raspuns += nrAlbume(i, prim);
    raspuns %= MOD;
  }
  return raspuns;
}

// Calculează numărul de albume cu un număr de piese dat
// printr-un interval, respectând restricțiile din enunț
// care încep cu un anumit tip de piesă dat.
int sumaNrAlbume(int piese1, int piese2, int prim) {
  return sumaNrAlbume(piese2, prim) - sumaNrAlbume(piese1 - 1, prim);
}

Rescriem noua funcție în formă recursivă.

// Calculează numărul de albume cu un număr de piese dat
// printr-un interval de forma [0, piese], respectând restricțiile
// din enunț care încep cu un anumit tip de piesă dat.
int sumaNrAlbume(int piese, int prim) {
  if (piese < 0) {
    return 0;
  } else if (piese == 0) {
    return nrAlbume(0, prim);
  } else {
    return nrAlbume(piese, prim) + sumaNrAlbume(piese - 1, prim);
  }
}

În final, putem aplica memoizarea pe noua funcție:

int SumaNrAlbume[1 + MAX_PIESE][2];

// Calculează numărul de albume cu un număr de piese dat
// printr-un interval de forma [0, piese], respectând restricțiile
// din enunț care încep cu un anumit tip de piesă dat.
int sumaNrAlbume(int piese, int prim) {
  if (piese < 0) {
    return 0;
  } else {
    if (SumaNrAlbume[piese][prim] == 0) {
      if (piese == 0) {
        SumaNrAlbume[piese][prim] = nrAlbume(0, prim);
      } else {
        SumaNrAlbume[piese][prim] = nrAlbume(piese, prim) + sumaNrAlbume(piese - 1, prim);
      }
    }
    return SumaNrAlbume[piese][prim];
  }
}

Cu ajutorul acestei optimizări am redus cu un factor timpul de execuție polinomial.

Temă

Pentru data viitoare veți avea de rezolvat următoarele probleme: