Clasa a 7-a lecția 26 - 07 apr 2016

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.

Temă Rezolvari

Rezolvări aici [1]

Lectie

Am rezolvat impreuna problema Flags

Versiunea 1: Backtracking - am încercat toate posibilitățile de colorare ale steagurilor și le-am numărat. Am folosit o implementare recursivă pentru backtracking. Funcția recursivă returnează numărul de configurații de sufixe de steaguri valide.

#include <cstdio>

const int MAX_N = 45;
const int WHITE = 0;
const int RED = 1;
const int BLUE = 2;

int N;
int v[MAX_N];

int backtracking(int i) {
  // i = pozitia curenta (pe care o competam)
  // N = numarul de fasii ale steagului
  // returneaza numarul de steaguri
  int answer = 0;
  if (i == 0) {
    v[i] = WHITE;
    answer += backtracking(1);
    v[i] = RED;
    answer += backtracking(1);
  } else if (i == N) {
    if (v[N - 1] != BLUE)
      answer++;
  } else { // if (i <= N) {
    if (v[i - 1] == WHITE) {
      v[i] = BLUE;
      answer += backtracking(i + 1);//nr de feluri in care putem
      // completa steagul curent (de la poz. i + 1 la N)
      v[i] = RED;
      answer += backtracking(i + 1);//nr de feluri in care putem
      // completa steagul curent (de la poz. i + 1 la N)
    } else if (v[i - 1] == RED) {
      v[i] = WHITE;
      answer += backtracking(i + 1);
      v[i] = BLUE;
      answer += backtracking(i + 1);
    } else if (v[i - 1] == BLUE && v[i - 2] == RED) {
      v[i] = WHITE;
      answer += backtracking(i + 1);
    } else { //if (v[i - 1] == BLUE && v[i - 2] == WHITE) {
      v[i] = RED;
      answer += backtracking(i + 1);
    }
  }
  return answer;
}

int main(void) {
  int answer;

  // citirea datelor
  scanf("%d", &N);

  // calcularea solutiei
  answer = backtracking(0);

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

Versiunea 2: Am simplificat foarte mult funcția recursivă.

#include <cstdio>

const int MAX_N = 45;
const int WHITE = 0;
const int RED = 1;
const int BLUE = 2;

int N;

int backtracking(int last, int i) {
  // i = pozitia curenta (pe care o competam)
  // N = numarul de fasii ale steagului
  // returneaza numarul de steaguri
  int answer = 0;
  if (i == N) {
    answer++;
  } else if (i < N) {
    if (last == WHITE) {
      answer += backtracking(RED, i + 2);
      answer += backtracking(RED, i + 1);
    } else { // if (last == RED) {
      answer += backtracking(WHITE, i + 1);
      answer += backtracking(WHITE, i + 2);
    }
  }
  return answer;
}

int main(void) {
  int answer;

  // citirea datelor
  scanf("%d", &N);

  // calcularea solutiei
  answer = backtracking(RED, 1) +
      backtracking(WHITE, 1);

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

Versiunea 3: Am simplificat și mai mult programul și se constată că acesta calculează șirul lui Fibonacci.

#include <cstdio>

int backtracking(int N) {
  if (N == 0)
    return 0;
  else if (N == 1)
    return 1;
  else // if (N > 0)
    return backtracking(N - 2) + backtracking(N - 1);
}

int main(void) {
  int N;
  int answer;
  // citirea datelor
  scanf("%d", &N);
  // calcularea solutiei
  answer = 2 * backtracking(N);
  // afisarea solutiei
  printf("%d\n", answer);
  return 0;
}

Versiunea 4: Am aplicat memoizare peste calculea șirului lui Fibonacci și am redus complexitatea timp de la exponențial la liniar.

#include <cstdio>

const int MAX_N = 45;

unsigned int Fibo[1 + MAX_N];

unsigned int fibo(int N) {
  if (Fibo[N] == 0) {
    if (N == 0)
      Fibo[N] = 0;
    else if (N == 1)
      Fibo[N] = 2;
    else // if (N > 0)
      Fibo[N] = fibo(N - 2) + fibo(N - 1);
  }
  return Fibo[N];
}

int main(void) {
  int N;
  unsigned int answer;
  // citirea datelor
  scanf("%d", &N);
  // calcularea solutiei
  answer = fibo(N);
  // afisarea solutiei
  printf("%u\n", answer);
  return 0;
}

Tema