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

From Algopedia
Jump to navigationJump to search
Line 13: Line 13:
 
= Lectie =  
 
= Lectie =  
 
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:
 +
<syntaxhighlight>
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 +
Versiunea 2:
 +
<syntaxhighlight>
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 +
Versiunea 3:
 +
<syntaxhighlight>
 +
#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;
 +
}
 +
</syntaxhighlight>
 +
 +
Versiunea 4:
 +
<syntaxhighlight>
 +
#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;
 +
}
 +
</syntaxhighlight>
  
 
= Tema =
 
= Tema =

Revision as of 12:25, 14 April 2016

Temă Rezolvari

Rezolvări aici [1]

Lectie

Am rezolvat impreuna problema Flags

Versiunea 1:

#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:

#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:

#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:

#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