Cum rezolvăm un subiect de bac la informatică?

  

Cum rezolvăm un subiect de bac la informatică?


În această postare vom rezolva un subiect de bacalaureat la informatică, mai exact primul model oferit de MEC anul acesta.


Vom începe cu primul subiect și vom lua în ordine exercițiile de tip grilă:




Trebuie să găsim expresia care are valoarea 1 (adevărată) DACĂ ȘI NUMAI DACĂ (⇔) n (întreg) este divizibil cu 2 și cu 5. 

Foarte mulți omit relația de ECHIVALENȚĂ între cele 2 și cred că este una și aceeași cu o relație de IMPLICAȚIE (⇒). Să ne reamintim diferența:

AB înseamnă că dacă A este adevărată, atunci și B este adevărată; în caz că A este falsă, nu se poate spune nimic despre B.

 AB înseamnă că A și B au aceleași valori de adevăr. Este o DUBLĂ IMPLICAȚIE: AB și BA

!Nu te rezuma doar la AB sau B

Exemplu: 

(n%4 == 0 && n % 5 == 0) ⇒ n este divizibil cu 2* și cu 5, deci expresia este adevărată (1)

*dacă n este divizibil cu 4 atunci este divizibil și cu divizorii lui 4, D4 = {1, 2, 4};

 DAR dacă o luăm în sens invers B A  expresia este  falsă (0): 

n este divizibil cu 2 și cu 5 ≠> (n%4 == 0 && n%5 == 0)  // dacă un număr este divizibil cu 2 nu înseamnă că este divizibil cu 4 (ex: 26)

Deci relația de echivalență nu este îndeplinită.

!


Scriem ipoteza matematic și vom avea: 

(n%2 == 0 && n%5 == 0), o vom nega și vom obține

!(n%2 != 0 || n%5 != 0), n%2 poate avea valoarea 0 sau 1. Așadar, dacă n%2 != 0, atunci n % 2 == 1. Înlocuind vom obține:

!(n%2 ==1 && n%5 != 0) (care este a))

Răspuns: a)




Nu avem decât să parcurgem programul cu atenție și să vedem ce valoare va avea f(102030)

f(102030) = 20 + f(10203) = 2100
f(10203) = 20 + f(1020) = 2080
f(1020) =  20 + f(102)  = 2060
f(102) = 20 + f(10) = 2040
f(10) = 2020 (10 <= 20)

Răspuns: c)



Continuând șirul vom obține: 13, 131, 133, 201, 203, 21, 211, 213, 221, 223, 23, 231, 233, 3, 301, 303, …

Răspuns: d)



Avem un vector în care valoarea (nodul) de pe poziția i reprezintă tatăl nodului i. Așadar nodul care se repetă de 2 ori în vector înseamnă că este un tată cu 2 fii: 2, 7, 8.


Cea mai sigură opțiune este să desenați pe ciornă arborele începând cu nodul care nu are niciun tată (0), nodul nostru fiind 7; după aceea căutăm nodurile care îl au tată pe 7: 8, 9. Și tot așa.

Observăm că nodul 7, 8, 2, au câte 2 fii.

Răspuns: b)



Teorie: Un graf neorientat complet are numărul de muchii egal cu C(n, 2)*= n*(n-1)/2

*combinări de n luate câte 2

 În cazul nostru: n = 20 ⇒ 190 de muchii, avem deja 100 ⇒ mai trebuie adăugate 90 de muchii 

Răspuns: c)



Subiectul al II-lea


  1. Facem un tabel de valori și parcurgem cu atenție programul

12345, 780, 921, 4012, 75, 100214
N:12345 -> 1234 -> 123 -> 12 -> 1 -> 0
P: 1 -> 10 -> 100 -> 1000 -> 10000 -> 100000
M: 0 -> 0 -> 20 -> 20 -> 2020 -> 2020
K:0 -> 1 -> 2 -> 3 -> 4 -> 5
X: 780 -> 921 -> 92 -> 4012 -> 401 -> 40 ->75 -> 7 -> 0 -> 0 -> 100214 -> 10021 -> 1002 -> 100 -> 10
I: 1 -> 1 -> 2 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 4 -> 1 -> 2 -> 3 -> 4 -> 5
C: 0 -> 2 -> 0 -> 2 -> 0

Se va afișa 2020

  1. Observăm că după citirea lui n  trebuie să scriem alte 2 numere, 2 reprezentând câte cifre are n. Mai observăm că după ce împărțim numărul de k ori dacă x != 0 va prelua ultima cifra a lui, în caz contrar va prelua ultima cifra a numărului n. În variabila m se formează un număr care preia cifrele de la x sau n și le poziționează de fiecare dată la stânga numărului deja format. Variabila k știm că la fiecare număr citit crește cu o unitate, astfel primul număr nu va fi modificat (k = 0) și al doilea număr va fi împărțit la 10 o data (k = 1).

Deci primul număr va avea obligatoriu ultima cifra 9 sau va fi egal cu 0, iar al doilea va avea penultima cifră 4 sau va fi format dintr-o singură cifră. Sunt mai multe variante de răspuns.

Răspunsul meu: 49 0 3; 49 989 546


c.


#include
using namespace std;
int main()
{
int n, p, m, k, i, x, c; // din a) observati variabele care trebuie declarate
cin >> n;
p = 1; m =0; k = 0;
while(n!= 0)
{
cin >> x;
for(i = 1; i <= k; ++i)
x /= 10;
if(x!= 0) c = x%10;
else  c = n%10;
m = c * p + m;
n /= 10;
p *= 10;
++k;
}
cout << m;
return 0;
}


d.     Observăm că avem 2 structuri repetitive: una cu număr necunoscut de pași (cât timp execută), și una cu număr cunoscut de pași     (pentru i <- 1, k execută). Vom opta pentru înlăturarea structurii repetitive cu număr cunoscut de pași, observând că aceasta împarte x     la 10^k. Așadar, putem modifica modul în care evoluează k: îl vom inițializa cu 1, iar în interiorul structurii cât timp vom împărți x la k,     după aceea îl înmulțim k cu 10.


citește n (număr natural)
p <- 1; m <- 0; k <- 1
┌cât timp n =/= 0 execută
citește x (număr natural)
x <- [x/k]
│ ┌ dacă x =/= 0 atunci x <- x%10
    └■ altfel c <- n%10
m <- c*p+m
n <- [n/10]
p <- p*10; k <- k*10;
└■
scrie m



Teorie:

struct [NUME_STRUCTURĂ]
{
    [TIP1 NUME_CÂMP[, NUME_CÂMP[, ...]];]
    [TIP2 NUME_CÂMP[, NUME_CÂMP[, ...]];]
    ...
} [LISTA DE VARIABILE];


Conform teoriei și cerinței vom avea:

struct triunghi{
       struct coord{
        float x, y;
       }A, B, C;
   } t;



Afișare:8viCtORIe

Parcurgere:

K: 32 (nu este neapărat să știm numărul)

A: VIcToriE -> vIcToriE -> vicToriE -> viCToriE -> viCtoriE -> viCtOriE -> viCtORiE -> viCtORIE -> viCtORIe

I: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 


Explicație: Programul afișează câte litere are cuvântul “victorie” și înlocuiește litere de tipar cu litere mici și invers, și apoi îl afișează.


Trecem la Subiectul al III-lea

Pasul 1 determinăm cu ce tip de variabile vom lucra

 n e  [1, 10^9] și dacă se va modifica îl vom împărți, iar d și p vor fi mai mici decât n, deci toate variabilele se încadrează în tipul int

Pasul 2 scriem antetul programului

Programul furnizează divizorul prim d, și puterea p, așadar va fi un program de tip void, numele său este putere și are trei parametri de tip int, dintre care 2 (d, p) vor avea referință

Pasul 3 analizăm problema și căutăm o rezolvare eficientă

Aceasta este o problemă tipică. Descompunerea unui număr în factori primi face parte din seria algoritmilor elementari. Tot ce trebuie să facem este să introducem în subprogramul nostru acest algoritm de bază și să reținem într-o variabilă d divizorul prim care apare la cea mai mare putere p.

void putere(int n, int &d, int &p)
{
  int f, e; // f- factorul prim, e- exponentul lui f
  p = 0; // initializam d  si p la cea mai mica valoare pe care poate s-o ia
  for(f = 2; n != 1; ++f)
  {
    e = 0;
    while(n % f == 0)
    {
       n /= f;
       ++e;
    }
    if(e > p)
    {
      p = e;
      d = f;
    }
    else if(e == p && f > d) // daca se gasesc 2 factori primi la aceeasi putere vom retine factorul cel mai mare
    d = f;
  }
}



Observăm că exemplul nu respectă cerința în totalitate pentru că matricea are 5 linii, nu 4 (= n). Noi vom respecta cerința.

Pasul 1 Stabilim variabilele/tablourile cu care vom lucra și tipul lor

Vom avea un tablou not. m[25][4200] și contorii i și j

Pasul 2 Analizăm problema și căutăm o soluție

Acest tip de problemă se rezolvă identificând o regulă și/sau  condiție. Al i-lea rând va începe cu i și din k în k coloane va crește cu o unitate. Cel mai simplu este sa luăm elemente din tablou și să vedem ce valoare au primit:

M[1][1]  = 1

M[1][4] = 2

M[1][9] = 3

M[4][6] = 5

Observăm că dacă j % k == 0 m[i][j] = i + j/k - 1 altfel m[i][j] = i + j/k (j - indice coloana)

O vom aplica în programul nostru:

#include 
using namespace std;
int main(){
  int n, k, i, j, m[100][100];
  cin >> n >> k;
  for(i = 1; i <= n; ++i)
    for(j = 1; j <= n*k; ++j)
    if(j % k == 0)  m[i][j] = i + j/k - 1;
    else  m[i][j] = i + j/k;
  for(i = 1; i <= n; ++i)
  {
    for(j = 1; j <= n *k; ++j)
      cout << m[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}


  1. Avem relația de recurență:

fn= 3*fn-1-fn-2 => fn+2= 3*fn+1-fn => fn= 3*fn+1-fn+2

Ultima relație o vom folosi în programul nostru:

#include 
#include
using namespace std;
ofstream fout("bac.txt");
int main(){
  int x, y, z; // x = f(n+1), y = f(n+2), z = f(n)
  cin >> x >> y;
  fout << y <<' ' << x << ' '; // afisam primii 2 termeni
  z = 3*x - y; // f(n) = 3*f(n+1)-f(n+2) relatie dedusa din relatia de recurenta 
  while(z != 1)
  {
    fout << z << ' ';
    //retinem doar ultimii 2 termeni: x, z
    y = x; // y = f(n+1)
    x = z; //x = f(n)
    z = 3*x - y; // f(n-1)= 3*f(n) - f(n+1)
  }
  fout << 1 << ' ' << 1; // afisam ultimii 2 termeni
  return 0;
}


  1. Am citit de la tastatură cele 2 numere și am aplicat relația fn= 3*fn+1-fn+2    dedusă din ipoteză: fn= 3*fn-1-fn-2 => fn+2= 3*fn+1-fn => fn= 3*fn+1-fn+2, actualizând de fiecare dată ultimii doi termeni x și y.

Algoritmul este eficient din punct de vedere al memoriei deoarece nu utilizează decât 3 variabile(nu se folosesc tablouri pentru stocarea elementelor) .

Algoritmul este liniar, adică dintr-o singură parcurgere se obţin rezultatele dorite: (O(n)) unde n este numărul elementelor din șirul format prin relația de recurență dată.









x
Acest website utilizează cookie-uri pentru a creea o experiență cât mai plăcută. Învață mai multe Acceptă