Probleme informatice (part˘ial) rezolvate matematic...Probleme informatice (part˘ial) rezolvate...

122
Probleme informatice (part ¸ial) rezolvate matematic 2018 FMI - Lect ¸ii de preg˘ atire pentru admitere 1 / 55

Transcript of Probleme informatice (part˘ial) rezolvate matematic...Probleme informatice (part˘ial) rezolvate...

Probleme informatice (partial)

rezolvate matematic

2018 FMI - Lectii de pregatire pentru admitere1 / 55

Scop

Trucuri (matematice) pentru a rezolva unele probleme informatice.

Trucuri (informatice) pentru a rezolva unele probleme matematice.Provocare: Project Euler

2 / 55

Scop

Trucuri (matematice) pentru a rezolva unele probleme informatice.Trucuri (informatice) pentru a rezolva unele probleme matematice.

Provocare: Project Euler

2 / 55

Pe scurt

1 Probleme de numarare si Programare dinamica

2 Probleme cu numere; Divizibilitate; Algoritmul lui Euclid

3 / 55

Probleme de numarare: Plan

Descoperirea formulei recursive

(Optional) rezolvarea recursiei

Programarea solutiei.

4 / 55

Problema

Q1

Daca o echipa de baschet are 9 jucatori,ın cate moduri ısi poate alege cei 5 jucatori ın teren?

5 / 55

Truc matematic: Combinari de n luate cate k

Formula recursiva

C 0n = 1, C n

n = 1, C kn = C k

n−1 + C k−1n−1

Rezolvarea recursiei

C kn =

n!

(n − k)!k!

6 / 55

C kn — formula directa

C kn = C n−k

n =n!

(n − k)!k!

=(n − k + 1) · (n − k + 2) · · · · · (n − k + k)

1 · 2 · · · · · k

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

unsigned long long numarator = 1, numitor = 1;

for (int i = 1; i <= k; i++) {

numarator = numarator * (n - k + i);

numitor = numitor * i;

}

return numarator / numitor;

}

Cate operatii se fac?Observati vreo problema?

7 / 55

C kn — formula directa

C kn = C n−k

n =n!

(n − k)!k!=

(n − k + 1) · (n − k + 2) · · · · · (n − k + k)

1 · 2 · · · · · k

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

unsigned long long numarator = 1, numitor = 1;

for (int i = 1; i <= k; i++) {

numarator = numarator * (n - k + i);

numitor = numitor * i;

}

return numarator / numitor;

}

Cate operatii se fac?Observati vreo problema?

7 / 55

C kn — formula directa

C kn = C n−k

n =n!

(n − k)!k!=

(n − k + 1) · (n − k + 2) · · · · · (n − k + k)

1 · 2 · · · · · k

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

unsigned long long numarator = 1, numitor = 1;

for (int i = 1; i <= k; i++) {

numarator = numarator * (n - k + i);

numitor = numitor * i;

}

return numarator / numitor;

}

Cate operatii se fac?Observati vreo problema?

7 / 55

C kn — Definitia recursiva

C 0n = 1, C n

n = 1, C kn = C k

n−1 + C k−1n−1

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

return combination(n-1, k) + combination(n-1, k-1);

}

Observati vreo problema?Cate adunari se fac?

8 / 55

C kn — Definitia recursiva

C 0n = 1, C n

n = 1, C kn = C k

n−1 + C k−1n−1

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

return combination(n-1, k) + combination(n-1, k-1);

}

Observati vreo problema?

Cate adunari se fac?

8 / 55

C kn — Definitia recursiva

C 0n = 1, C n

n = 1, C kn = C k

n−1 + C k−1n−1

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

return combination(n-1, k) + combination(n-1, k-1);

}

Observati vreo problema?Cate adunari se fac?

8 / 55

Truc: retinerea valorilor deja calculate

C 0n = 1, C n

n = 1, C kn = C k

n−1 + C k−1n−1

unsigned long long memo[101][101];

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

unsigned long long cnk = memo[n][k];

if (cnk == 0) {

cnk = combination(n-1, k) + combination(n-1, k-1);

memo[n][k] = cnk;

}

return cnk;

}

Cate adunari se fac?

9 / 55

Truc: retinerea valorilor deja calculate

C 0n = 1, C n

n = 1, C kn = C k

n−1 + C k−1n−1

unsigned long long memo[101][101];

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

unsigned long long cnk = memo[n][k];

if (cnk == 0) {

cnk = combination(n-1, k) + combination(n-1, k-1);

memo[n][k] = cnk;

}

return cnk;

}

Cate adunari se fac?

9 / 55

Truc: tabelare

Triunghiul lui Pascal:

C 00 1

C 01 C 1

1 1 1C 02 C 1

2 C 22 1 2 1

C 03 C 1

3 C 23 C 3

3 1 3 3 1C 04 C 1

4 C 24 C 3

4 C 44 1 4 6 4 1

10 / 55

Truc: tabelare

unsigned long long linie_triunghi[101];

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

linie_triunghi[0] = 1;

for (int i = 1; i <= n; i++) {

if (i <= k) linie_triunghi[i] = 1;

for (unsigned j = min(k, i-1); j > 0; j--)

linie_triunghi[j] =

linie_triunghi[j-1] + linie_triunghi[j];

}

return linie_triunghi[k];

}

Cate adunari se fac?

11 / 55

Truc: tabelare

unsigned long long linie_triunghi[101];

unsigned long long combination(unsigned n, unsigned k) {

k = min(k, n-k);

if (k == 0 || n == k) return 1;

linie_triunghi[0] = 1;

for (int i = 1; i <= n; i++) {

if (i <= k) linie_triunghi[i] = 1;

for (unsigned j = min(k, i-1); j > 0; j--)

linie_triunghi[j] =

linie_triunghi[j-1] + linie_triunghi[j];

}

return linie_triunghi[k];

}

Cate adunari se fac?

11 / 55

Problema

Q2

In cate moduri putem acoperi n trepte cu n dreptunghiuri,unde dreptunghiurile pot avea orice forma?

12 / 55

Acoperirea treptelor cu dreptunghiuri

Exemplu

Suprafata ın forma de scara cu 4 trepte:

13 / 55

Acoperirea treptelor cu dreptunghiuri

Exemplu

Suprafata ın forma de scara cu 4 trepte:

13 / 55

Alegerea triunghiului din colt

Sa consideram cazul cu 6 trepte.

In acest mod nu se poate obtine o acoperire cu 6 dreptunghiuri!

14 / 55

Alegerea triunghiului din colt

Sa consideram cazul cu 6 trepte.

In acest mod nu se poate obtine o acoperire cu 6 dreptunghiuri!

14 / 55

Acoperirea treptelor cu dreptunghiuri

Fiecare dreptunghi trebuie sa acopere o treapta!

Deci, dreptunghiul din colt ımparte problema ın doua.

Formula recursiva

Notam cu Cn numarul de acoperiri pentru n trepte. Se observa relatia:

C6 = C5 + C1 · C4 + C2 · C3 + C3 · C2 + C4 · C1 + C5

C6 =6∑

k=1

Ck−1Cn−k , cu C0 = 1.

15 / 55

Acoperirea treptelor cu dreptunghiuri

Fiecare dreptunghi trebuie sa acopere o treapta!

Deci, dreptunghiul din colt ımparte problema ın doua.

Formula recursiva

Notam cu Cn numarul de acoperiri pentru n trepte. Se observa relatia:

C6 = C5 + C1 · C4 + C2 · C3 + C3 · C2 + C4 · C1 + C5

C6 =6∑

k=1

Ck−1Cn−k , cu C0 = 1.

15 / 55

Acoperirea treptelor cu dreptunghiuri

Fiecare dreptunghi trebuie sa acopere o treapta!

Deci, dreptunghiul din colt ımparte problema ın doua.

Formula recursiva

Notam cu Cn numarul de acoperiri pentru n trepte. Se observa relatia:

C6 = C5 + C1 · C4 + C2 · C3 + C3 · C2 + C4 · C1 + C5

C6 =6∑

k=1

Ck−1Cn−k , cu C0 = 1.

15 / 55

Acoperirea treptelor cu dreptunghiuri

Fiecare dreptunghi trebuie sa acopere o treapta!

Deci, dreptunghiul din colt ımparte problema ın doua.

Formula recursiva

Notam cu Cn numarul de acoperiri pentru n trepte. Se observa relatia:

C6 = C5 + C1 · C4 + C2 · C3 + C3 · C2 + C4 · C1 + C5

C6 =6∑

k=1

Ck−1Cn−k , cu C0 = 1.

15 / 55

Truc: Numerele lui Catalan

Formula recursiva

Cn =n∑

k=1

Ck−1Cn−k , cu C0 = 1.

C0 = 1,

Cn = C0Cn−1 + C1Cn−2 + · · ·+ Cn−2C1 + Cn−1C0

Rezolvarea recursiei

Cn =1

n + 1C n2n

Exemplu:

1 1 2 5 14 42 132 429 1430 4862 16796 58786208012 742900 2674440 9694845 35357670 129644790

16 / 55

Truc: Numerele lui Catalan

Formula recursiva

Cn =n∑

k=1

Ck−1Cn−k , cu C0 = 1.

C0 = 1,

Cn = C0Cn−1 + C1Cn−2 + · · ·+ Cn−2C1 + Cn−1C0

Rezolvarea recursiei

Cn =1

n + 1C n2n

Exemplu:

1 1 2 5 14 42 132 429 1430 4862 16796 58786208012 742900 2674440 9694845 35357670 129644790

16 / 55

Truc: Numerele lui Catalan

Formula recursiva

Cn =n∑

k=1

Ck−1Cn−k , cu C0 = 1.

C0 = 1,

Cn = C0Cn−1 + C1Cn−2 + · · ·+ Cn−2C1 + Cn−1C0

Rezolvarea recursiei

Cn =1

n + 1C n2n

Exemplu:

1 1 2 5 14 42 132 429 1430 4862 16796 58786208012 742900 2674440 9694845 35357670 129644790

16 / 55

Aplicatii

Q

In cate moduri putem paranteza produsul x0 · x1 · x2 · . . . · xn?

Exemplu (n=3)

x0 · (x1 · (x2 · x3))

x0 · ((x1 · x2) · x3)

(x0 · x1) · (x2 · x3)

((x0 · x1) · x2) · x3(x0 · (x1 · x2)) · x3

17 / 55

Aplicatii

Q

In cate moduri putem paranteza produsul x0 · x1 · x2 · . . . · xn?

Exemplu (n=3)

x0 · (x1 · (x2 · x3))

x0 · ((x1 · x2) · x3)

(x0 · x1) · (x2 · x3)

((x0 · x1) · x2) · x3(x0 · (x1 · x2)) · x3

17 / 55

Aplicatii

Q

In cate moduri putem paranteza produsul x0 · x1 · x2 · . . . · xn?

Rezolvare:Notam cu pn numarul parantezarilor lui x0 · x1 · x2 · . . . · xn.Observam

(x0 · . . . · xk) · (xk+1 · . . . · xn)↓ ↓

pk pn−k−1

Decipn =

∑n−1k=0 pk · pn−k−1 = p0 · pn−1 + p1 · pn−2 + . . .+ pn−2 · p1 + pn−1 · p0

Se observa ca pn = Cn, deci numarul parantezarilor unui produs de n + 1factori este numarul lui Catalan Cn.

18 / 55

Aplicatii

Q

In cate moduri putem paranteza produsul x0 · x1 · x2 · . . . · xn?

Rezolvare:Notam cu pn numarul parantezarilor lui x0 · x1 · x2 · . . . · xn.Observam

(x0 · . . . · xk) · (xk+1 · . . . · xn)↓ ↓

pk pn−k−1

Decipn =

∑n−1k=0 pk · pn−k−1 = p0 · pn−1 + p1 · pn−2 + . . .+ pn−2 · p1 + pn−1 · p0

Se observa ca pn = Cn, deci numarul parantezarilor unui produs de n + 1factori este numarul lui Catalan Cn.

18 / 55

Aplicatii

Q

In cate moduri putem paranteza produsul x0 · x1 · x2 · . . . · xn?

Rezolvare:Notam cu pn numarul parantezarilor lui x0 · x1 · x2 · . . . · xn.Observam

(x0 · . . . · xk) · (xk+1 · . . . · xn)↓ ↓

pk pn−k−1

Decipn =

∑n−1k=0 pk · pn−k−1 = p0 · pn−1 + p1 · pn−2 + . . .+ pn−2 · p1 + pn−1 · p0

Se observa ca pn = Cn, deci numarul parantezarilor unui produs de n + 1factori este numarul lui Catalan Cn.

18 / 55

Problema

Q3

In cate moduri se poate scrie un numar n ca suma a k numere?

n = n1 + n2 + . . .+ nk ,0 < n1 ≤ n2 ≤ . . . ≤ nk

19 / 55

Truc: Partitia unei multimi

O partitie a multimii A este o familie de submultimi {Ai}i∈I care verificaurmatoarele proprietati:

1 Ai 6= ∅ pentru orice i ∈ I ,

2 A =⋃

i∈I Ai ,

3 Ai ∩ Aj = ∅ pentru i 6= j ∈ I .

Multimile Ai se numesc clase ale partiei.

20 / 55

Truc: Partitia unei multimi

Exemplu

Care sunt partitiile multimii A = {1, 2, 3} ?

{1, 2, 3}{1, 2}, {3}{1, 3}, {2}{2, 3}, {1}{1}, {2}, {3}

21 / 55

Truc: Partitia unei multimi

Exemplu

Care sunt partitiile multimii A = {1, 2, 3} ?

{1, 2, 3}

{1, 2}, {3}{1, 3}, {2}{2, 3}, {1}{1}, {2}, {3}

21 / 55

Truc: Partitia unei multimi

Exemplu

Care sunt partitiile multimii A = {1, 2, 3} ?

{1, 2, 3}{1, 2}, {3}{1, 3}, {2}{2, 3}, {1}

{1}, {2}, {3}

21 / 55

Truc: Partitia unei multimi

Exemplu

Care sunt partitiile multimii A = {1, 2, 3} ?

{1, 2, 3}{1, 2}, {3}{1, 3}, {2}{2, 3}, {1}{1}, {2}, {3}

21 / 55

Truc: Numarul partitiilor unei multimi

Nr. elem.: 0 1 2 3 4 5 6 7 8 9 10

Nr. partitii: 1 1 2 5 15 52 203 877 4140 21147 115975

Numarul lui Bell Bn: numarul partitiilor unei multimi cu n elemente

Numarul lui Stirling de tipul II S(n, k): numarul partitiilor cu k clase aleunei multimi cu n elemente

Bn = S(n, 1) + S(n, 2) + . . .+ S(n, n − 1) + S(n, n)

22 / 55

Truc: Numarul partitiilor unei multimi

Nr. elem.: 0 1 2 3 4 5 6 7 8 9 10

Nr. partitii: 1 1 2 5 15 52 203 877 4140 21147 115975

Numarul lui Bell Bn: numarul partitiilor unei multimi cu n elemente

Numarul lui Stirling de tipul II S(n, k): numarul partitiilor cu k clase aleunei multimi cu n elemente

Bn = S(n, 1) + S(n, 2) + . . .+ S(n, n − 1) + S(n, n)

22 / 55

Truc: Numarul partitiilor unei multimi

Nr. elem.: 0 1 2 3 4 5 6 7 8 9 10

Nr. partitii: 1 1 2 5 15 52 203 877 4140 21147 115975

Numarul lui Bell Bn: numarul partitiilor unei multimi cu n elemente

Numarul lui Stirling de tipul II S(n, k): numarul partitiilor cu k clase aleunei multimi cu n elemente

Bn = S(n, 1) + S(n, 2) + . . .+ S(n, n − 1) + S(n, n)

22 / 55

Truc: Numarul partitiilor unei multimi

Nr. elem.: 0 1 2 3 4 5 6 7 8 9 10

Nr. partitii: 1 1 2 5 15 52 203 877 4140 21147 115975

Numarul lui Bell Bn: numarul partitiilor unei multimi cu n elemente

Numarul lui Stirling de tipul II S(n, k): numarul partitiilor cu k clase aleunei multimi cu n elemente

Bn = S(n, 1) + S(n, 2) + . . .+ S(n, n − 1) + S(n, n)

22 / 55

Truc: Numarul partitiilor unei multimi

Exemplu

Care sunt partitiile multimii A = {1, 2, 3} ?

{1, 2, 3}{1, 2}, {3}{1, 3}, {2}{2, 3}, {1}{1}, {2}, {3}

S(3, 1) = 1

S(3, 2) = 3

S(3, 3) = 1

B3 = S(3, 1) + S(3, 2) + S(3, 3) = 5

Observati ca S(n, 1) = 1, S(n, n) = 1

23 / 55

Truc: Numarul partitiilor unei multimi

Exemplu

Care sunt partitiile multimii A = {1, 2, 3} ?

{1, 2, 3}{1, 2}, {3}{1, 3}, {2}{2, 3}, {1}{1}, {2}, {3}

S(3, 1) = 1

S(3, 2) = 3

S(3, 3) = 1

B3 = S(3, 1) + S(3, 2) + S(3, 3) = 5

Observati ca S(n, 1) = 1, S(n, n) = 1

23 / 55

Truc: Numarul partitiilor unei multimi

Daca stim sa calculam S(n, k) pentru orice k ≤ n

∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗

atunci stim sa calculam si S(n + 1, k):

1 ∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗ •

2 ∗ ∗ ∗ ∗ ∗ ∗ · · · ∗•∗ · · · ∗ ∗ ∗

Formula recursiva

S(n + 1, k) = S(n, k − 1) + kS(n, k)

Conditiile initiale: S(1, 1) = 1 si S(n, 0) = S(0, k) = 0

24 / 55

Truc: Numarul partitiilor unei multimi

Daca stim sa calculam S(n, k) pentru orice k ≤ n

∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗

atunci stim sa calculam si S(n + 1, k):

1 ∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗ •

2 ∗ ∗ ∗ ∗ ∗ ∗ · · · ∗•∗ · · · ∗ ∗ ∗

Formula recursiva

S(n + 1, k) = S(n, k − 1) + kS(n, k)

Conditiile initiale: S(1, 1) = 1 si S(n, 0) = S(0, k) = 0

24 / 55

Truc: Numarul partitiilor unei multimi

Daca stim sa calculam S(n, k) pentru orice k ≤ n

∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗

atunci stim sa calculam si S(n + 1, k):

1 ∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗ •

2 ∗ ∗ ∗ ∗ ∗ ∗ · · · ∗•∗ · · · ∗ ∗ ∗

Formula recursiva

S(n + 1, k) = S(n, k − 1) + kS(n, k)

Conditiile initiale: S(1, 1) = 1 si S(n, 0) = S(0, k) = 0

24 / 55

Truc: Numarul partitiilor unei multimi

Daca stim sa calculam S(n, k) pentru orice k ≤ n

∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗

atunci stim sa calculam si S(n + 1, k):

1 ∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗ •

2 ∗ ∗ ∗ ∗ ∗ ∗ · · · ∗•∗ · · · ∗ ∗ ∗

Formula recursiva

S(n + 1, k) = S(n, k − 1) + kS(n, k)

Conditiile initiale: S(1, 1) = 1 si S(n, 0) = S(0, k) = 0

24 / 55

Truc: Numarul partitiilor unei multimi

Daca stim sa calculam S(n, k) pentru orice k ≤ n

∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗

atunci stim sa calculam si S(n + 1, k):

1 ∗ ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗ •

2 ∗ ∗ ∗ ∗ ∗ ∗ · · · ∗•∗ · · · ∗ ∗ ∗

Formula recursiva

S(n + 1, k) = S(n, k − 1) + kS(n, k)

Conditiile initiale: S(1, 1) = 1 si S(n, 0) = S(0, k) = 0

24 / 55

Truc: Numarul partitiilor unei multimi ın k clase

Input: n ≥ 1, numarul de elemente al multimii M

Output: Un vector S ın care S [k] este numarul partitiilor lui M cu kclase

Data: Un vector S de dimensiune n

beginS[1] := 1

for i := 2 to n doS[i] := 1

for k := i-1 down to 2 doS[k] := k * S[k] + S[k-1]

end

end

endreturn S

25 / 55

Aplicatii

Q

Sa se determine numarul functiilor surjectivef : {1, . . . , n} → {1, . . . , k}.

Rezolvare:Notam acest numar cu σ(n, k). Observam ca

partitionam multimea {1, . . . , n} ın k clase ın S(n, k) moduri

ducem cate un element din fiecare partitie ın multimea {1, . . . , k} ınk! moduri (permutari de k elemente este k!)

Deci raspunsul este σ(n, k) = k!S(n, k)

26 / 55

Aplicatii

Q

Sa se determine numarul functiilor surjectivef : {1, . . . , n} → {1, . . . , k}.

Rezolvare:Notam acest numar cu σ(n, k). Observam ca

partitionam multimea {1, . . . , n} ın k clase ın S(n, k) moduri

ducem cate un element din fiecare partitie ın multimea {1, . . . , k} ınk! moduri (permutari de k elemente este k!)

Deci raspunsul este σ(n, k) = k!S(n, k)

26 / 55

Aplicatii

Q

Sa se determine numarul relatiilor de echivalenta care se pot defini pemultimea {1, . . . , n}.

Rezolvare:Oricarei relatii de echivalenta R pe {1, . . . , n} ıi asociem o partitie amultimii {1, . . . , n} astfel:

(i , j) ∈ R ⇔ i si j sunt ın aceeasi clasa

Observam ca ın acest mod se stabileste o bijectie ıntre multimea relatiilorde echivalenta si partitiile multimii {1, . . . , n}.Atunci raspunsul este dat de numarul partitiilor multimii {1, . . . , n}.

27 / 55

Aplicatii

Q

Sa se determine numarul relatiilor de echivalenta care se pot defini pemultimea {1, . . . , n}.

Rezolvare:Oricarei relatii de echivalenta R pe {1, . . . , n} ıi asociem o partitie amultimii {1, . . . , n} astfel:

(i , j) ∈ R ⇔ i si j sunt ın aceeasi clasa

Observam ca ın acest mod se stabileste o bijectie ıntre multimea relatiilorde echivalenta si partitiile multimii {1, . . . , n}.Atunci raspunsul este dat de numarul partitiilor multimii {1, . . . , n}.

27 / 55

Aplicatii

Q

Sa se determine numarul matricilor A patratice de dimensiune n carecontin doar 0 si 1, si care verifica urmatoarele proprietati:

1 A[i , i ] = 1 or. 1 ≤ i ≤ n,

2 A[i , j ] = A[j , i ] or. 1 ≤ i , j ≤ n,

3 A[i , j ] = 1 si A[j , k]=1 implica A[i , k] = 1 or. 1 ≤ i , j , k ≤ n

Rezolvare:Asociem lui A o partitie a multimii {1, . . . , n} astfel:

A[i , j ] = 1 ⇔ i si j sunt ın aceeasi clasa

Observam ca ın acest mod se stabileste o bijectie ıntre multimeamatricilor de acest tip si partitiile multimii {1, . . . , n}.Atunci raspunsul este dat de numarul partitiilor multimii {1, . . . , n}.

28 / 55

Aplicatii

Q

Sa se determine numarul matricilor A patratice de dimensiune n carecontin doar 0 si 1, si care verifica urmatoarele proprietati:

1 A[i , i ] = 1 or. 1 ≤ i ≤ n,

2 A[i , j ] = A[j , i ] or. 1 ≤ i , j ≤ n,

3 A[i , j ] = 1 si A[j , k]=1 implica A[i , k] = 1 or. 1 ≤ i , j , k ≤ n

Rezolvare:Asociem lui A o partitie a multimii {1, . . . , n} astfel:

A[i , j ] = 1 ⇔ i si j sunt ın aceeasi clasa

Observam ca ın acest mod se stabileste o bijectie ıntre multimeamatricilor de acest tip si partitiile multimii {1, . . . , n}.Atunci raspunsul este dat de numarul partitiilor multimii {1, . . . , n}.

28 / 55

Q3

In cate moduri se poate scrie un numar n ca suma a k numere?

n = n1 + n2 + . . .+ nk , 0 < n1 ≤ n2 ≤ . . . ≤ nk

Descoperirea recursiei:

Daca p(n, k) este acest numar, observam ca avem doua grupuri departitii:

1 partitii cu 1 ın ele, i.e. 1 + ceva

2 partitii fara 1

Formula recursiva

p(0, 0) = 0, p(n, 0) = p(0, k) = 0,

p(n, k) = p(n − 1, k − 1) + p(n − k, k)

29 / 55

Q3

In cate moduri se poate scrie un numar n ca suma a k numere?

n = n1 + n2 + . . .+ nk , 0 < n1 ≤ n2 ≤ . . . ≤ nk

Descoperirea recursiei:

Daca p(n, k) este acest numar, observam ca avem doua grupuri departitii:

1 partitii cu 1 ın ele, i.e. 1 + ceva

2 partitii fara 1

Formula recursiva

p(0, 0) = 0, p(n, 0) = p(0, k) = 0,

p(n, k) = p(n − 1, k − 1) + p(n − k, k)

29 / 55

Q3

In cate moduri se poate scrie un numar n ca suma a k numere?

n = n1 + n2 + . . .+ nk , 0 < n1 ≤ n2 ≤ . . . ≤ nk

Descoperirea recursiei:

Daca p(n, k) este acest numar, observam ca avem doua grupuri departitii:

1 partitii cu 1 ın ele, i.e. 1 + ceva

2 partitii fara 1

Formula recursiva

p(0, 0) = 0, p(n, 0) = p(0, k) = 0,

p(n, k) = p(n − 1, k − 1) + p(n − k , k)

29 / 55

Problema

Q4

In cate moduri putem acoperi o placa de 2×N cu piese de domino 1× 2?

30 / 55

Piese de domino

Exemplu

Pentru o placa de 2× 7, o solutie este:

31 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1?

F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2?

F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Piese de domino: descoperirea recursiei

Fie Fn numarul acoperirilor unei table 2× n.

Cat este F1? F1 = 1

Cat este F2? F2 = 2

Stiind sa calculam Fk pt. or. k < n, cat este Fn?

Fn = Fn−1 + Fn−2

32 / 55

Truc: Numerele lui Fibonacci

F0 = 1, F1 = 1, Fn = Fn−1 + Fn−2 pentru n ≥ 2

Input: n ≥ 1Output: Al n-lea numar din secventa Fibonaccibegin

f1 := 1

f2 := 1

for i := 2 to n doaux := f1

f1 := f2

f2 := aux + f2end

endreturn f2

33 / 55

Truc: Numerele lui Fibonacci

F0 = 1, F1 = 1, Fn = Fn−1 + Fn−2 pentru n ≥ 2

Input: n ≥ 1Output: Al n-lea numar din secventa Fibonaccibegin

f1 := 1

f2 := 1

for i := 2 to n doaux := f1

f1 := f2

f2 := aux + f2end

endreturn f2

33 / 55

Aplicatii

Reproducerea iepurilor

Populatia ıncepe cu o singura pereche de iepuri.

Fiecare pereche de iepuri produce o noua pereche ın doua luni.

Presupunem ca iepurii nu mor niciodata.

Cate perechi de iepuri vor fi peste n luni?

Rezolvare:Daca fn este numarul de perechi de iepuri peste n luni, atunci avemrelatiile f0 = 1, f1 = 1, fn+1 = fn + fn−1 pentru n ≥ 2.

34 / 55

Aplicatii

Reproducerea iepurilor

Populatia ıncepe cu o singura pereche de iepuri.

Fiecare pereche de iepuri produce o noua pereche ın doua luni.

Presupunem ca iepurii nu mor niciodata.

Cate perechi de iepuri vor fi peste n luni?

Rezolvare:Daca fn este numarul de perechi de iepuri peste n luni, atunci avemrelatiile f0 = 1, f1 = 1, fn+1 = fn + fn−1 pentru n ≥ 2.

34 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 21: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 21: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 21: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 21: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 2

1: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 21: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul secventelor binare de lungime n care nu contin 0-uriconsecutive?

Rezolvare:

Fie sn numarul secventelor de lungime n care nu contin 0-uriconsecutive.

Se observa ca s0 = 1 (cuvantul vid) si s1 = 2.

O secventa de lungime n care nu contine 0-uri consecutive se poatetermina ın:

0: ?? . . .?10, unde |?? . . .?| = n − 21: ?? . . .?1, unde |?? . . .?| = n − 1

Deci sn = sn−1 + sn−2.

35 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.

36 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.

36 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.

36 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.

36 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.

n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.

36 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.

36 / 55

Aplicatii

Q

Care este numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive?

Rezolvare:

Fie an numarul submultimilor lui {1, . . . , n} care nu contin douanumere consecutive.

Se observa ca a0 = 1 (multimea vida) si a1 = 2.

Pentru n ≥ 2, daca A este o submultime a lui {1, . . . , n} care nucontine doua numere consecutive, atunci avem doua cazuri:

n este ın A: Atunci n − 1 nu poate sa fie ın A si A \ {n} este osubmultime a lui {1, . . . , n − 2} care nu contin doua numereconsecutive.n nu este ın A: Atunci A este o submultime a lui {1, . . . , n − 1} carenu contin doua numere consecutive.

Deci an = an−2 + an−1.36 / 55

Problema

Q6

In cate zerouri se termina 100! ?

100! = 1 · 2 · 3 · 4 . . . · 97 · 98 · 99 · 100

37 / 55

In cate zerouri se termina n! ?

Algoritmul naiv

Input: n ∈ NOutput: Numarul de zerouri din n!

beginfact := 1

for i := 2 to n dofact := fact * i

endz := 0

while fact mod 10 = 0 dofact := fact div 10

z := z + 1end

endreturn z

Observati vreo problema?

38 / 55

In cate zerouri se termina n! ?

Algoritmul naiv

Input: n ∈ NOutput: Numarul de zerouri din n!

beginfact := 1

for i := 2 to n dofact := fact * i

endz := 0

while fact mod 10 = 0 dofact := fact div 10

z := z + 1end

endreturn z

Observati vreo problema?38 / 55

In cate zerouri se termina n! ?

Zerourile de la sfarsitul lui n! apar din produse de 2 si 5

Descompunem n! ın factori primi: n! = 2k2 ∗ 3k3 ∗ 5k5 ∗ · · ·

Numarul zerourile de la sfarsitul lui n! este min(k2, k5).

Sunt mai putini factori 5 decat 2, deci nr. de zerouri cautat este k5.

k5 = nr. numerelor mai mici ca n divizibile cu 5 +nr. numerelor mai mici ca n divizibile cu 25 +nr. numerelor mai mici ca n divizibile cu 125 + ...

k5 =∑i≥1

⌊ n5i

⌋, unde

⌊ n

5i+1

⌋=

⌊⌊n5i

⌋5

39 / 55

In cate zerouri se termina n! ?

Zerourile de la sfarsitul lui n! apar din produse de 2 si 5

Descompunem n! ın factori primi: n! = 2k2 ∗ 3k3 ∗ 5k5 ∗ · · ·

Numarul zerourile de la sfarsitul lui n! este min(k2, k5).

Sunt mai putini factori 5 decat 2, deci nr. de zerouri cautat este k5.

k5 = nr. numerelor mai mici ca n divizibile cu 5 +nr. numerelor mai mici ca n divizibile cu 25 +nr. numerelor mai mici ca n divizibile cu 125 + ...

k5 =∑i≥1

⌊ n5i

⌋, unde

⌊ n

5i+1

⌋=

⌊⌊n5i

⌋5

39 / 55

In cate zerouri se termina n! ?

Zerourile de la sfarsitul lui n! apar din produse de 2 si 5

Descompunem n! ın factori primi: n! = 2k2 ∗ 3k3 ∗ 5k5 ∗ · · ·

Numarul zerourile de la sfarsitul lui n! este min(k2, k5).

Sunt mai putini factori 5 decat 2, deci nr. de zerouri cautat este k5.

k5 = nr. numerelor mai mici ca n divizibile cu 5 +nr. numerelor mai mici ca n divizibile cu 25 +nr. numerelor mai mici ca n divizibile cu 125 + ...

k5 =∑i≥1

⌊ n5i

⌋, unde

⌊ n

5i+1

⌋=

⌊⌊n5i

⌋5

39 / 55

In cate zerouri se termina n! ?

Zerourile de la sfarsitul lui n! apar din produse de 2 si 5

Descompunem n! ın factori primi: n! = 2k2 ∗ 3k3 ∗ 5k5 ∗ · · ·

Numarul zerourile de la sfarsitul lui n! este min(k2, k5).

Sunt mai putini factori 5 decat 2, deci nr. de zerouri cautat este k5.

k5 = nr. numerelor mai mici ca n divizibile cu 5 +nr. numerelor mai mici ca n divizibile cu 25 +nr. numerelor mai mici ca n divizibile cu 125 + ...

k5 =∑i≥1

⌊ n5i

⌋, unde

⌊ n

5i+1

⌋=

⌊⌊n5i

⌋5

39 / 55

In cate zerouri se termina n! ?

Zerourile de la sfarsitul lui n! apar din produse de 2 si 5

Descompunem n! ın factori primi: n! = 2k2 ∗ 3k3 ∗ 5k5 ∗ · · ·

Numarul zerourile de la sfarsitul lui n! este min(k2, k5).

Sunt mai putini factori 5 decat 2, deci nr. de zerouri cautat este k5.

k5 = nr. numerelor mai mici ca n divizibile cu 5 +nr. numerelor mai mici ca n divizibile cu 25 +nr. numerelor mai mici ca n divizibile cu 125 + ...

k5 =∑i≥1

⌊ n5i

⌋, unde

⌊ n

5i+1

⌋=

⌊⌊n5i

⌋5

39 / 55

In cate zerouri se termina n! ?

k5 =∑i≥1

⌊ n5i

⌋, unde

⌊ n

5i+1

⌋=

⌊⌊n5i

⌋5

Input: n ∈ NOutput: Numarul de zerouri din n!

beginz := 0

while n 6= 0 don := n div 5

z := z + nend

endreturn z

40 / 55

Problema

Q7

Pentru doua numere n ≥ 1 si p ≥ 1, n ≥ p, gasiti x si y cu proprietatea

xn + yp = cmmdc(n, p)

41 / 55

Truc: Algoritmul lui Euclid

Algoritmul lui Euclid (scaderi repetate)

Input: n, p ∈ N, n ≥ p

Output: cmmdc(n, p)

beginwhile n 6= p do

if n ≥ p thenn := n - p

elsep := p - n

end

end

endreturn n

42 / 55

Truc: Algoritmul lui Euclid

Algoritmul lui Euclid (ultimul rest nenul)

Input: n, p ∈ N, n ≥ p

Output: cmmdc(n, p)

beginwhile p 6= 0 do

aux := p

p := n mod p

n := auxend

endreturn n

43 / 55

Truc: Algoritmul lui Euclid

Algoritmul ıncepe cu n si p si consta ın calcularea

unei secvente q1, . . . , qk de caturi si a

unei secvente r0, . . . , rk+1 de resturi

astfel ıncat:r0 = nr1 = p. . .ri+1 = ri−1 − qi ri si 0 ≤ ri+1 < ri. . .

Algoritmul se termina cand un rest rk+1 este 0 si cmmdc-ul este rk .

Caturile q1, . . . , qk nu sunt folosite!

44 / 55

Truc: Algoritmul lui Euclid

Input: n, p ∈ N, n ≥ p

Output: cmmdc(n, p)

beginr := n

r’ := p

while r’ 6= 0 doct := r div r’

aux := r

r := r’

r’ := aux - ct * r’end

endreturn r

45 / 55

Truc: Algoritmul lui Euclid extins

Algoritmul lui Euclid extins permite calcularea a doi ıntregi x si y astfelıncat

xn + yp = cmmdc(n, p) (Identitatea lui Bezout)

46 / 55

Truc: Algoritmul lui Euclid extins

Algoritmul ıncepe cu n si p, si consta ın adaugarea a doua secventesuplimentare

x0, . . . , xk si

y0, . . . , yk d

astfel ıncatri = xi ∗ n + yi ∗ p

r0 = n r1 = p . . .x0 = 1 x1 = 0 . . .y0 = 0 y1 = 1 . . .

Formula recursiva

ri+1 = ri−1 − qi ri astfel ınca t 0 ≤ ri+1 < rixi+1 = xi−1 − qixiyi+1 = yi−1 − qiyi

47 / 55

Truc: Algoritmul lui Euclid extins

Algoritmul se termina cand un rest rk+1 este 0.In acest caz obtinem:

rk este cmmdc(n,p)

Coeficientii Bezout sunt xk si yk , adica:

xkn + ykp = cmmdc(n, p) = rk

48 / 55

Algoritmul lui Euclid extins

Input: n, pOutput: r=cmmdc(n, p) si x , y , astfel ıncat x ∗ a + y ∗ b = rbegin

x := 1 x’ := 0

y := 0 y’ := 1

r := n r’ := p

while r ′ 6= 0 doct := r div r’

aux := r r := r’ r’ := aux - ct * r’

aux := x x := x’ x’ := aux - ct * x’

aux := y y := y’ y’ := aux - ct * y’

end

endreturn r,x,y

49 / 55

Aplicatii

Q

Sa se verifice daca n este inversabil modulo p.In caz afirmativ, sa se determine n−1(mod p).

Rezolvare:

Algoritmul lui Euclid permite calcularea a doi ıntregi x si y astfelıncat xn + yp = cmmdc(n, p).

Daca cmmdc(n, p) = 1, atunci n−1(mod p) = x .

50 / 55

Aplicatii

Q

Sa se verifice daca n este inversabil modulo p.In caz afirmativ, sa se determine n−1(mod p).

Rezolvare:

Algoritmul lui Euclid permite calcularea a doi ıntregi x si y astfelıncat xn + yp = cmmdc(n, p).

Daca cmmdc(n, p) = 1, atunci n−1(mod p) = x .

50 / 55

Problema

Q8

Care este cel mai mic numar natural n care ımpartit la 2 da restul 1,ımpartit la 3 da restul 2, ımpartit la 5 da restul 3, iar ımpartit la 7 da

restul 4?

51 / 55

Problema

Q8

Care este cel mai mic numar natural n care ımpartit la 2 da restul 1,ımpartit la 3 da restul 2, ımpartit la 5 da restul 3, iar ımpartit la 7 da

restul 4?

Q

Fie p1, . . . , pk numere naturale prime ıntre ele si0 ≤ si < pi , oricare 1 ≤ i ≤ k .

Determinati s ≥ 0 astfel ıncat s = si (mod pi ) oricare 1 ≤ i ≤ k.

52 / 55

Truc: Teorema chineza a resturilor

Teorema

s =k∑

i=1

(si · Pi · xi ),

unde Pi = p1···pkpi

si xi = P−1i (mod pi ) oricare 1 ≤ i ≤ k.

Observati ca xi poate fi calculat folosind Algoritmul lui Euclid extins.

53 / 55

Truc: Teorema chineza a resturilor

Teorema

s =k∑

i=1

(si · Pi · xi ),

unde Pi = p1···pkpi

si xi = P−1i (mod pi ) oricare 1 ≤ i ≤ k.

Observati ca xi poate fi calculat folosind Algoritmul lui Euclid extins.

53 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Truc: Teorema chineza a resturilor

s =∑k

i=1(siPixi ), unde Pi = p1···pkpi

si xi = P−1i (mod pi ) or. i .

Exemplu

p1 = 2, p2 = 3, p3 = 5, p4 = 7s1 = 1, s2 = 2, s3 = 3, s4 = 4

P = 2 ∗ 3 ∗ 5 ∗ 7 = 210

P1 = 105, 1 = 105−1 (mod 2), x1 = 1

P2 = 70, 1 = 70−1 (mod 3), x2 = 1

P3 = 42, 3 = 42−1 (mod 5), x3 = 3

P4 = 30, 4 = 30−1 (mod 7), x4 = 4

Deci s = 1 ∗ 105 ∗ 1 + 2 ∗ 70 ∗ 1 + 3 ∗ 42 ∗ 3 + 4 ∗ 30 ∗ 4 = 1109

54 / 55

Bafta la examen!

55 / 55