Difference between revisions of "Clasa a 7-a lecția 26 - 07 apr 2016"

From Algopedia
Jump to navigationJump to search
 
Line 14: Line 14:
 
Am rezolvat impreuna problema [http://acm.timus.ru/problem.aspx?num=1225 Flags]
 
Am rezolvat impreuna problema [http://acm.timus.ru/problem.aspx?num=1225 Flags]
  
Versiunea 1:
+
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.
 
<syntaxhighlight>
 
<syntaxhighlight>
 
#include <cstdio>
 
#include <cstdio>
Line 78: Line 78:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Versiunea 2:
+
Versiunea 2: Am simplificat foarte mult funcția recursivă.
 
<syntaxhighlight>
 
<syntaxhighlight>
 
#include <cstdio>
 
#include <cstdio>
Line 124: Line 124:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Versiunea 3:
+
Versiunea 3: Am simplificat și mai mult programul și se constată că acesta calculează șirul lui Fibonacci.
 
<syntaxhighlight>
 
<syntaxhighlight>
 
#include <cstdio>
 
#include <cstdio>
Line 150: Line 150:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Versiunea 4:
+
Versiunea 4: Am aplicat memoizare peste calculea șirului lui Fibonacci și am redus complexitatea timp de la exponențial la liniar.
 
<syntaxhighlight>
 
<syntaxhighlight>
 
#include <cstdio>
 
#include <cstdio>

Latest revision as of 12:31, 14 April 2016

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