Page 107 - MATINF Nr.2

˘
PROBLEME DE INFORMATICA PENTRU EXAMENE 107

Teste pentru admiterea la facultate

Testul 1
Viorel P˘aun 1

15
1. Fie m s , i n dou˘a numere naturale, 2 ≤ m, n < 2 .
n
a) Demonstrat , i c˘a suma resturilor ˆımp˘art , irii num˘arului m la numerele 1, 2, . . . , n este
n 2
mai mic˘a decˆat .
2
b) Elaborat , i un program C++ pentru calculul sumei resturilor ˆımp˘art , irii num˘arului m n
la 1, 2, . . . , n.
c) Elaborat , i o funct , ie C++ de complexitate O(log n) pentru calculul restului ˆımp˘art , irii
2
n
num˘arului m la k.
2
n
2. Fie polinomul P(x) = a 0 + a 1 x + a 2 x + . . . + a n x , n ∈ N, n ≤ 1000, cu coeficient , i
ˆın corpul Z p al claselor de resturi modulo p, unde p este un num˘ar prim. Elaborat , i un
program C++ pentru:
a) reducerea gradului polinomului P(x), utilizˆand relat , ia x p−1 ≡ 1 (mod p);
b) rezolvarea ecuat , iei polinomiale P(x) = 0.

Testul 2
Costel B˘alc˘au 2

1. Se dau un num˘ar natural n avˆand k cifre s , i un num˘ar m ∈ {1, 2, . . . , k − 1}. Elaborat , i un
program C++ care s˘a determine:

a) num˘arul maxim p ce se obt , ine din n prin eliminarea unei singure cifre;
b) num˘arul maxim q ce se obt , ine din n prin eliminarea a m cifre.
Exemplu. Pentru n = 97478461 s , i m = 4, r˘aspunsul la punctul a) este p = 9778461, iar
r˘aspunsul la punctul b) este q = 9861.
2. Fie n un num˘ar natural nenul.
a) Elaborat , i un program C++ pentru generarea tuturor partit , iilor mult , imii M =
{1, 2, 3, . . . , 2n} ˆın dou˘a submult , imi de cardinale egale (submult , imile sunt disjuncte,
reuniunea lor este M s , i nu conteaz˘a ordinea dintre ele).
b) Elaborat , i un program C++ pentru determinarea num˘arului de partit , ii de la punctul
a).

1
Lect. univ. dr., Universitatea din Pites , ti, viop23@yahoo.com
2
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com