Data: simulare 2019
Profil: Matematica-Informatica
Limbaj: C++
Tutoriale Recomandate:
- Tipul struct in C++ | Teorie si probleme rezolvate
- Despre recursivitate in informatica
- Algoritmul pentru descompunerea unui numar in cifre C++
Subiectul I.
1. Indicați expresia C/C++ cu valoarea 1.
Trebuie să ținem cont de faptul că atunci când facem o operație de genul x/y, atunci se face împărțirea întreagă (spre exemplu dacă împărțim 3 la 19 rezultatul va fi 0, nu 0.157…). Mergând pe acest principiu, observăm ca răspunsul corect este d. 19/21*3==3/19*21. Atât 19/21, cât și 3/19 dau 0 deoarece sunt fracții subunitare.
2. Utilizând metoda backtracking, se generează toate drapelele formate din câte 3 culori distincte din mulţimea {alb, galben, negru, roșu, verde}. Două drapele sunt distincte dacă diferă prin cel puțin o culoare sau prin ordinea culorilor. Primele patru soluţii obţinute sunt, în această ordine:
(alb, galben, negru), (alb, galben, roșu), (alb, galben, verde) şi (alb, negru, galben).
Indicaţi soluția generată imediat înainte de (galben, verde, alb).
a. (negru, roșu, verde) b. (negru, alb, galben)
c. (galben, verde, roșu) d. (galben, roșu, verde)
Codificăm răspunsurile noastre:
1 – alb
2 – galben
3 – negru
4 – roșu
5 – verde
Variantele de răspuns devin: (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 2), (1, 3, 4), (1, 3, 5), (1, 4, 2), (1, 4, 3), (1, 4, 5), (2, 1, 3), (2, 1, 4), (2, 1, 5), (2, 3, 1), (2, 3, 4), (2, 4, 5), (2, 5, 1). Soluția generată înainte de (galben, verde, alb) – adică (2, 5, 1) este (2, 4, 5) – adică d. (galben, roșu, verde).
3. Subprogramul f alăturat este incomplet definit. Indicați expresia cu care pot fi înlocuite punctele de suspensie, astfel încât valoarea lui f(2019,1) să fie egală cu numărul divizorilor pozitivi ai lui 2019.
int f(int n, int d)
{
if(..........)
return 0;
if(d*d == n)
return 1;
if(n%d == 0)
return 2+f(n,d+1);
return f(n,d+1);
}
Analizăm funcția recursiva și observăm că al doilea if se execută doar dacă d^2 este stric mai mare decât n. Răspuns final: a. d*d>n.
4. Un graf neorientat cu 8 noduri, numerotate de la 1 la 8, are muchiile [1,2], [1,6], [4,6],
[3,6], [6,5], [5,3], [3,4], [7,8], [8,2]. Trei noduri care nu aparţin niciunui ciclu în acest
graf pot fi:
a. 1, 3, 4 b. 2, 7, 8
c. 3, 5, 6 d. 5, 6, 8
Dacă analizăm desenul,observăm că doar nodurile 1,2,7 și 8 nu fac parte dintr-un ciclu. Deci răspunsul final este b. 2, 7, 8.
Subiectul II.
1. Algoritmul alăturat este reprezentat în pseudocod. S-a notat cu a%b restul împărţirii numărului natural a la numărul natural nenul b şi cu [c] partea întreagă a numărului real c.
citeste a,b,k (numere naturale, 1≤a≤b, k>1) pm <- 0; y <- 0; i <- b cât timp i≥a execută --- x <- i; p <- 0 --- cât timp x%k=0 execută ------ x <- [x/k]; p <- p+1 --- dacă p≠0 și (p<pm sau pm=0)atunci ------ pm <- p; y <- i --- i <- i-1 scrie y
a) Scrieţi valoarea afişată dacă se citesc, în această ordine, numerele 5, 19 și 4.
Dacă analizăm algoritmul, observăm că acesta parcurge toate numerele de la b la a și caută cel mai mare număr care se poate împărți de cele mai puține ori la k. Deci, răspunsul este 12 (4^1 *3).
b) Dacă pentru variabila b se citeşte numărul 2019, iar pentru variabila k se citeşte numărul 5, scrieţi cea mai mică şi cea mai mare valoare care pot fi citite pentru variabila a astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, valoarea afişată să fie 0.
Putem observa că ne este de la început pusă condiția ca a să fie mai mic sau egal cu b. Deci, o mică scurtătură ar fi ca pentru valoarea maximă pentru care condiția să fie respectată, asta s-ar putea întâmpla dacă a și b ar fi egale (adică 2019 este valoarea maximă). Observăm că k=5, deci dacă mulțimea [a,b] ar conține elemente care nu se împart exact la k, atunci se va afișa 0 (în cazul nostru, b=2016).
c) Scrieţi programul C/C++ corespunzător algoritmului dat.
#include <iostream>
using namespace std;
int main()
{
int a,b,k,pm,y,x,i;
cin >> a >> b >> k;
pm = 0; y = 0; i = b;
while(i >= a)
{
x = i;
p = 0;
while(x % k == 0)
{
x = x / k;
p = p + 1;
}
if(p != 0 && ( p < pm || pm == 0))
{
pm = p;
y = i;
}
i = i - 1;
}
cout << y;
return 0;
}
d) Scrieţi în pseudocod un algoritm, echivalent cu cel dat, înlocuind prima structură
cât timp…execută cu o structură repetitivă de tip pentru…execută.
citeste a,b,k (numere naturale, 1≤a≤b, k>1) pm <- 0; y <- 0 pentru i <- b, a, -1 executa --- x <- i; p <- 0 --- cât timp x%k=0 execută ------ x <- [x/k]; p <- p+1 --- dacă p≠0 și (p<pm sau pm=0)atunci ------ pm <- p; y <- i --- i <- i-1 scrie y
2. Expresiile de mai jos au ca valori numere naturale, reprezentând următoarele informații memorate pentru un eveniment din anul 2019: data desfășurării sale (ziua și luna) și un identificator. Scrieți definiția unei structuri cu eticheta eveniment, care să permită memorarea informațiilor menționate pentru un eveniment, și declarați corespunzător variabila e, de acest tip.
e.data.zi e.data.luna e.id
struct eveniment {
int id;
struct tipData {
int zi;
int luna;
} data;
} e;
3. Variabilele i şi j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 5 linii şi
5 coloane, numerotate de la 0 la 4, având iniţial toate elementele nule. Fără a utiliza alte variabile decât cele menționate, scrieţi secvenţa de instrucţiuni de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenţei obţinute, variabila a să memoreze tabloul alăturat.
Din nefericire nu ne putem folosi de o variabilă auxiliară pentru a ne ușura munca, deci singura variantă este să găsim o mică “formulă” în funcție de i și de j pentru a rezolva problema.
for(i = 0; i < 5; i++)
for(j = 0; j < 5; j++)
a[i][j] = i * 2 + j;
Subiectul III.
1. Subprogramul inserare are un singur parametru, n, prin care primeşte un număr natural
(n∈[10,105)). Subprogramul furnizează prin același parametru numărul obținut din n prin inserarea, între oricare două cifre alăturate ale sale, a valorii absolute a diferenței acestora. Scrieți definiția completă a subprogramului.
Exemplu: dacă n = 7255, atunci, după apel, n = 7523505.
int inserare(int n)
{
int x, v[15], k = 1, p = 1;
x = n;
while(x)
{
v[k++] = x % 10;
x = x / 10;
}
for(int i = k - 1; i >= 2; i--)
{
x = x*10 + v[i];
x = x*10 + abs(v[i]-v[i-1]);
}
x = x*10 + v[1];
n = x;
return n;
}
2. Într-un text de cel mult 50 de caractere cuvintele sunt separate prin câte un spațiu și sunt formate din litere mari ale alfabetului englez, urmate eventual de caracterul . (punct), dacă sunt scrise prescurtat. Textul reprezintă numele unei instituții de învățământ și doar cuvintele din mulțimea {COLEGIUL, LICEUL, NATIONAL, TEORETIC} pot fi prescurtate, eliminându-se ultimele lor litere. Scrieţi un program C/C++ care citeşte de la tastatură un text de tipul precizat și construiește în memorie, apoi afișează pe ecran, numele instituției scris fără prescurtări. Exemplu: dacă se citește textul COLEG. NATIONAL DE INFORMATICA sau textul COLEG. NAT. DE INFORMATICA se obține COLEGIUL NATIONAL DE INFORMATICA
#include <iostream>
using namespace std;
int main()
{
char s[51];
cin.get(s, 51);
int k = 0;
char sir[4][50] = {"COLEGIUL", "NATIONAL", "TEORETIC", "LICEUL"};
char ans[50][50];
char *cuvant = strtok(s, " ");
while(cuvant != NULL)
{
if(cuvant[strlen(cuvant) - 1] == '.')
{
cuvant[strlen(cuvant) - 1] = '\0';
for(int i = 0; i < 4; i++)
{
if(strstr(sir[i],cuvant))
{
strcpy(ans[k++],sir[i]);
}
}
}
else
strcpy(ans[k++],cuvant);
cuvant = strtok(NULL, " ");
}
for(int i = 0; i < k; i++)
cout << ans[i] << " ";
return 0;
}
3. Un șir format din 2·n numere naturale se numește paritar dacă fiecare dintre primii săi n termeni fie are aceeași paritate cu oricare dintre ultimii săi n termeni, fie este strict mai mic decât oricare număr de paritate diferită aflat printre aceștia. Fișierul bac.txt conține numere naturale din intervalul [0,106]: pe prima linie un număr nenul, n, iar pe a doua linie un șir de 2·n numere, separate prin câte un spațiu. Se cere să se afișeze pe ecran mesajul DA, în cazul în care șirul aflat în fișier este paritar, sau mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al memoriei utilizate.
Exemplu: dacă fișierul are unul dintre conținuturile de mai jos, se afișează pe ecran mesajul DA.
5 5
20 3 11 4 15 25 49 18 53 16 20 3 11 4 15 25 49 81 53 61
Una dintre soluții ar fi să memorăm elementele într-un vector și apoi să vedem dacă cele două șiruri respectă condițiile cerute (o soluție bună, dar ineficientă). Recomandabil ar fi să nu folosim vectori în astfel de situații. Putem observa că avem nevoie doar de 4 numere din ambele șiruri: cel mai mare număr impar din primul șir(impar_sir_1), cel mai mare număr par din primul șir(par_sir_1), cel mai mic număr par din al doilea șir(par_sir_2) și cel mai mic număr impar din al doilea șir(impar_sir_2). Astfel, dacă par_sir_1 < impar_sir_2 și impar_sir_1 < par_sir_2, atunci se va afișa DA.
#include <iostream>
using namespace std;
int main()
{
int n, par_sir_1 = -1, impar_sir_1 = -1, par_sir_2 = 999999, impar_sir_2 = 999999, x;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x;
if(x % 2 == 0)
par_sir_1 = max(par_sir_1,x);
if(x % 2 == 1)
impar_sir_1 = max(impar_sir_1,x);
}
for(int i = 1; i <= n; i++)
{
cin >> x;
if(x % 2 == 0)
par_sir_2 = min(par_sir_2,x);
if(x % 2 == 1)
impar_sir_2 = min(impar_sir_2,x);
}
if(par_sir_1 < impar_sir_2 && impar_sir_1 < par_sir_2)
cout << "DA";
else
cout << "NU";
return 0;
}
