Clasa a 8-a lecția 5 - 21 oct 2015

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

1167 - Bicolored Horses

Enunț: 1167 - Bicolored Horses

Se dau:
- N cai ordonați și K grajduri
- Pentru fiecare cal știm tipul de cal (alb sau negru)

Cerință: Să se găsească o repartizare a cailor în grajduri
(fără să li se modifice ordinea) astfel încât să se obțină
un coeficient de nefericire total minim.

Se cere: 
- Coeficientul minim de nefericire
  = suma coeficienților de nefericire din fiecare grajd
  = suma(pentru fiecare grajd, nrCaiAlbi * nrCaiNegri)

Implementare nerecursivă

Astăzi am trecut la implementarea nerecursivă a problemelor decompozabile în subprobleme suprapuse. De această dată am rezolvat o problemă de programare dinamică.

Implementarea nerecursivă trebuie redactată direct, fără pași intermediari. În plus, codul scris este mult mai puțin lizibil. Avantajul acestei metode de rezolvare este timpul redus de execuție iar dezavantajul este lipsa clarității codului.

Timpul de execuție este redus prin lipsa apelurilor recusive care necesită timp pentru transcrierea pe stivă a paraterilor.

Lizibilitatea este mult îngreunată deoarece nu este evident pentru cititorul codului dacă ordinea de calcul a elementelor din matrice este cea corectă. Nu este evident nici dacă inițializăm toate valorile matricei care nu sunt calculate de cazul general dar folosite de acesta.

Redactarea codului în această formă este, în plus, complicată și de faptul că trebuie să găsim o ordine în care să calculăm elementele matricei (sau matricelor) astfel încât de fiecare dată când aplicăm formula recurentă valorile de care depinde valoarea curentă să fie deja calculate.

Un alt avantaj al acestei metode este că că permite, în anumite situații, optimizarea stațiului folosit. De exemplu, în cazul de față, se pot stoca doar ultimele două coloane ale matricei Nefericire.

#include <stdio.h>
#include <limits.h>

const int MAX_N = 500;
const int INF = INT_MAX / 2;

int Nefericire[1 + MAX_N][1 + MAX_N];
// Primul indice reprezintă numărul de cai puși în grajduri.
// Al doilea indice reprezintă numărul de grajduri ocupate deja.

int CaiNegri[1 + MAX_N];

int min(int a, int b) {
  return a < b ? a : b;
}

int caiNegri(int begin, int end) {
  return CaiNegri[end] - CaiNegri[begin];
}

int caiAlbi(int begin, int end) { // exclusiv begin, inclusiv end
  return (end - begin) - caiNegri(begin, end);
}

int main() {
  int i;
  int N, K;
  int calulCurent;
  scanf("%d %d", &N, &K);
  CaiNegri[0] = 0; // initializare
  for (i = 1; i <= N; ++i) {
    scanf("%d", &calulCurent);
    CaiNegri[i] = CaiNegri[i - 1] + calulCurent;
  }

  int cai, grajduri;

  // initializare
  cai = 0;
  for (grajduri = 1; grajduri <= K; grajduri++) {
    Nefericire[cai][grajduri] = INF;
  }
  for (cai = 1; cai <= N; cai++) {
    grajduri = 0;
    Nefericire[cai][grajduri] = INF;
  }
  Nefericire[0][0] = 0;

  // cazul general
  for (cai = 1; cai <= N; cai++) {
    for (grajduri = 1; grajduri <= K; grajduri++) {
      int minim = INF;
      for(int ultimiiCai = 1; cai - ultimiiCai >= grajduri - 1; ultimiiCai++)
        // ultimiiCai reprezintă numărul de cai din grajdul cu numărul grajduri
        minim = min(minim, Nefericire[cai - ultimiiCai][grajduri - 1] +
            caiAlbi(cai - ultimiiCai, cai) *
            caiNegri(cai - ultimiiCai, cai));
      Nefericire[cai][grajduri] = minim;
    }
  }

  // calcularea solutiei
  int answer = Nefericire[N][K];

  printf("%d\n", answer);
  return 0;
}

Temă

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