prof. zoltan szabo - educampion.edu.ro/arhiva/www/arhiva_2009/papers/paper22.pdf · combinatoric...

Combinatoric�

prof. Zoltan Szabo

Parti�ionarea unui num�r

Pregatirea lotului national de informatica – juniori

Iasi, 2008

Parti�ionarea unui num�r

• Tipuri de probleme–Probleme de generare –Num�rul parti�ion�rilor–Num�rul de ordine al unei configura�ii în

mul�imea ordonat� a solu�iilor

Parti�ionare f�r� restric�ii Probleme de generare 1

• Problema 1. (Parti�ionare f�r� restric�ii)

��-se un num�r natural n, s� se descompun� în toate modurile posibile ca sum� de numere naturale nenule nu neap�rat distincte.


• Exemplun=4

1+1+1+11+1+21+2+11+3

2+1+12+23+14

Subprogram parti�ionare1(st:stiv�,k,s,n:natural){ dac� n=s atunci

tip�rete (st,k)altfel

pentru i1, n-s execut�{ st(k+1) i;

parti�ionare1(st,k+1,s+i,n)}

}


Apel: parti�ionare1(st,0,0,n)


• Exerci�iu

Genera�i toate descompunerile f�r� restric�ii în ordine lexicografic� a num�rului n=5


Solu�ie1+1+1+1+11+1+1+21+1+2+11+1+31+2+1+11+2+21+3+11+4

2+1+1+12+1+22+2+12+33+1+13+24+15

Parti�ionare cresc�toareProbleme de generare 2

• Problema 2. (Parti�ionare cresc�toare)

��-se un num�r natural n, s� se descompun� în toate modurile posibile ca sum� de numere naturale nenule nu neap�rat distincte aranjate cresc�tor.


• Exemplun=4

1+1+1+11+1+21+32+24



pentru ist(k),��-s execut�{ st(k+1) i;


}


Apel: st(0) �1;parti�ionare2(st,0,0,n)


• Exerci�iu

Genera�i toate descompunerile cresc�toare în ordine lexicografic� a num�rului n=5


Solu�ie1+1+1+1+11+1+1+21+1+31+2+21+4 2+3 5

Parti�ionare strict cresc�toareProbleme de generare 3

• Problema 3. (Parti�ionare strict cresc�toare)

��-se un num�r natural n, s� se descompun� în toate modurile posibile ca sum� de numere naturale distincte aranjate cresc�tor.


• Exemplun=4

1+34



pentru ist(k)+1, n-s execut�{ st(k+1) i;


}


Apel: st(0) 0;parti�ionare2(st,0,0,n)


• Exerci�iu

Genera�i toate descompunerile strict cresc�toare în ordine lexicografic� a num�rului n=5


Solu�ie

1+4 2+3 5

Parti�ionare special�Probleme de generare 4

• Problema 4. (Parti�ionare cu elementele unui �ir)

��-se un num�r natural n, s� se descompun� în toate modurile posibile ca sum� de p numere naturale: a1, a2,…, ap, .


• Exemplun=5p=2 a=(1,2)

1+1+1+1+11+1+1+21+1+2+11+2+1+11+2+22+1+1+12+1+22+2+1

Subprogram parti�ionare4(st:stiv�,k,s,n:natural){ dac� s=n atunci


dac� s


• Exerci�iu

Genera�i toate descompunerile în ordine lexicografic� a num�rului n=5 în valori de

1,2 i 3


Solu�ie1+1+1+1+11+1+1+21+1+2+11+1+31+2+1+11+2+21+32+1+1+12+1+22+2+12+3 3+1+13+2

Parti�ionare f�r� restric�ii ��iilor 1

• Problema 1. (Parti�ionare f�r� restric�ii)

��-se un num�r natural n, s� se determine num�rul descompunerilor ca sum� de numere naturale nu neap�rat distincte.

P(n) = ?


• Exemplu P(n) = ? n=4

1+1+1+11+1+21+2+11+3

2+1+12+23+14

• P(4)=P(3)+P(2)+P(1)+P(0)• P(n)=P(n-1)+P(n-2)+…P(0), P(0)=1


• P(n)=P(n-1)+P(n-2)+…P(0), P(0)=1

64321684211P76543210N

• Observ�m, c�

P(n)=2n-1

Parti�ionare cresc�toare ��iilor 2

• Problema 2. (Parti�ionare cresc�toare)

��-se un num�r natural n, s� se determine num�rul descompunerilor ca sum� de numere naturale nu neap�rat distincte, cu elementele în ordine cresc�toare.

P(n) = ?


Exemplu P(n) = ? n=4

1+1+1+11+1+21+3

• P(4,1)=P(3,1)+P(2,2)+1

Num�rul descompunerilor lui n cu prima valoare 1P(n,1)= P(n-1,1)+ P(n-2,2)+…+P(n-[n/2],[n/2]+1)

2+24

Var 1. Formul� recursiv�


Num�rul descompunerilor lui n cu prima valoare 1P(n,1)= P(n-1,1)+ P(n-2,2)+…+P(n-[n/2],[n/2])+1

Descompunerea lui n x cu prima valoare k

[ ]��

�

��

�

�

<∈

>+��

�

��

��

−+++−−+−

=kn

kkn

knnn

nPkknPkknP

knP

,02,,1

2,1)2

,2

(...)1,1(),(

),(

01254

01133

00122

00011

4321

Descompunerea lui n cu prima valoare k

[ ]��

�

��

�

�

<∈

>+��

�

��

��

−+++−−+−

=kn

kkn

knnn

nPkknPkknP

knP

,02,,1

2,1)2

,2

(...)1,1(),(

),(

P(2,1)=P(1,1)+1

P(3,1)=P(2,1)+1

P(3,2)=1

P(4,1)=P(3,1)+P(2,2)+1


Calculul recursiv:

Functie P1(n,k:natural){��>=2*k atunci

{ S1;pentru i k, [n/2]��

S S+P(n-i,i);returneaz� S;}

��

��>=k atuncireturneaz��;

��

��0;}

Programare dinamic�

functie P2(n,k:natural){��


• Exerci�iu

(Genera�i toate descompunerile cresc�toare în ordine lexicografic� a num�rului n=5)

Scrie�i formula recursiv� pentru num�rul descompunerilor cresc�toare a num�rului n=5


Solu�ie1+1+1+1+11+1+1+21+1+31+2+21+4 2+3 5

P(5,1)=P(4,1)+P(3,2)+1=7P(4,1)=P(3,1)+P(2,2)+1=5

P(3,1)=P(2,1)+1=3P(2,1)=P(1,1)+1=2

P(1,1)=1P(2,2)=1

P(3,2)=1


Construiti tabelul dinamic pentru n=9

1111124830901111237228

00111124157

00011124116

0000111275

0000011254

0000001133

0000000122

0000000011

987654321

Parti�ionare cresc�toare ��iilor 2 – Var. 2

O��“mai bun�”

1+1+1+1+11+1+1+2

1+2+21+1+3

2+31+4

5

P(n,k) – parti�ionarea lui n în numere nu mai mari decât k.

P(n,k)=P(n,k-1)+P(n-k,k) n>k>1P(n,k)=1+P(n,n-1) 1


Construiti tabelul dinamic pentru n=9

P(6,2)=P(6,1)+P(4,2)=1+3=4

3029282623181251922222120181510518

1515151413118417

111111111097416

7777765315

5555554314

3333333213

2222222212

1111111111

987654321


Cu tablou bidimensionalFunctie P(n,k:natural){pentru i 1, n execut�

{a(1,i) 1;a(i,1) 1;}

pentru i 2, n execut�pentru j 2, k execut�

��>j atuncia(i,j) a(i,j-1)+a(i-j,j);

altfela(i,j) 1+a(i,i-1);

returneaz� a(n,k)}

Cu tablou unidimensional

Functie P (n,k:natural){ a(0)1;

pentru i 1, n execut�a(i) 0;

pentru i 1, k execut�pentru j i, n execut�

a(j) a(j)+a(j-i)returneaz� a(n)

}


Num�rul parti�iilor lui n=5Pasul 1. ini�ializarea:

Pasul 2. num�rul parti�iilorFolosind doar cifra 1


000001a543210i

111111a543210i

332211a543210i


Num�rul parti�iilor lui n=5 (continuare)Pasul 4. num�rul parti�iilorFolosind doar cifra 3



543211a543210i

653211a543210i

753211a543210i

Parti�ionare strict cresc�toare ��iilor 3

• Problema 3 (Parti�ionarea strict cresc�toare)

Dându-se un num�r natural n, s� se determine num�rul descompunerilor ca sum� de numere naturale distincte, cu elementele în ordine cresc�toare.

P(n) = ?


Cazurin=5

2+31+4

5

P(n,k) – parti�ionarea lui n în numere distincte nu mai mari decât k.

P(n,k)=P(n,k-1)+P(n-k,k-1) n>k>1P(n,k)=1+P(n,n-1) 1


Cu tablou unidimensional

Functie P(n:natural){ a(0)1;pentru i 1, n execut�

a(i) 0;pentru i 1, n execut�

pentru j �n, i, pas -1 execut�a(j) a(j)+a(j-i)

��(n)}

Cu tablou bidimensional

Functie P(n,k:natural){ pentru i 1, n execut�{ a(1,i) 0;a(i,1) 0;}

pentru i 2, n execut�pentru j 2, k execut�

��>j atuncia(i,j) a(i,j-1)+a(i-j,j-1);

altfela(i,j) 1+a(i,i-1);

returneaz� a(n,k)}

Parti�ionare cresc�toare Formule recursive

4. Partition�rile lui n, în k numere nu mai mari decât m.

P(n,m,k)=P(n,m-1,k)+P(n-m,m,k-1) , n>m>1, k>1P(n,m,1)=P(n,m-1,1)+1 , 11,P(n,m,1)=1 , n�mP(n,m,1)=0 , n>m

n=8, m=4, k=51 1 1 1 41 1 1 2 31 1 2 2 2

Parti�ionare strict cresc�toare Formule recursive

5. Partition�rile lui n, în k numere distinctenu mai mari decât m.

P(n,m,k)=P(n,m-1,k)+P(n-m,m-1,k-1) ,n>m>1, k>1P(n,m,1)=P(n,m-1,1)+1 , 11,P(n,m,1)=1 , n�mP(n,m,1)=0 , n>m

n=10 m=5 k=3

1 4 5

2 3 5

Parti�ionare f�r� restric�iiOrdonan�are1

ProblemaSe consider� �irul parti�ion�rilor f�r� restric�ii al num�rului n, în ordine lexicografic�. S� se tip�reasc� parti�ionarea cu num�rul de ordine k.

Parti�ionare f�r� restric�ii Ordonan�are1

• Exemplun=4 k=5

1. 1+1+1+12. 1+1+23. 1+2+14. 1+35. 2+1+16. 2+27. 3+18. 4

Parti�ionarea a 5-a este��

Cum proced�m?

�tim c� num�rul parti�ion�rilor= 2n-1=8

Observ�m c�: 4 solu�ii încep cu 12 solu�ii încep cu 21 solu�ie începe cu 31 solu�ie începe cu 4

Parti�ionare f�r� restric�ii Ordonan�are1

• Exemplun=4 k=5

1. 1+1+1+12. 1+1+23. 1+2+14. 1+35. 2+1+16. 2+27. 3+18. 4

P=2n-1=8 n=4 k=5

tp/2, nrp/2 (nr=4)c 1;k�nr 5�4 ? Fals� nu începe cu 1

tt/2, nrnr+t (nr=6)c c+1;k�nr 5�6 ?�� scrie c (2)

n n-c; (n=2)k k-2*t; (k=1)c 1

…

Subprogram ordonantare(n,k:natural);{ t2n-2; prednr 0; nr t; c 1;Repeta

daca k=2t atunci {scrie(n,’ ’);n 0;}

altfeldaca k=1 atunci

{ pentru i 1,n executascrie (1,’ ’)

n 0}altfel

{cattimp nr0 atunci

daca k=2t atunci scrie(n,.’ ‘)altfel

daca k=1 atuncipentru i 1,n executa

scrie (1,’ ’)altfel

daca nr

Parti�ionare strict descresc�toareOrdonan�are 2

ProblemaSe consider� irul parti�ion�rilor��descresc�toare al unei sume de bani S n,în ordine lexicografic�. S� se tip�reasc� parti�ionarea cu num�rul de ordine n.

(ONI2005 Gala�i, cl. A X-a)

Parti�ionarea strict descresc�toare Ordonan�are2

• ExempluS=7 N=21. 4 2 12. 4 33. 5 24. 6 15. 7

Parti�ionarea a 2-a este��

Cum proced�m?Construim tabelul dinamic cu formulac(v,S)=P(v-1,S)+P(v-1,S-v)c(0,0)=1C(0,s)=0 s>0

Num�rul �� !��i este dat de C(N,N).


c(v,S)=P(v-1,S)+P(v-1,S-v)S>=v

C(v,S)=C(v-1,S) S0• Ce observ�m din ultima

coloan�?• A(4,7)=2 avem dou�

solu�ii care îl con�in pe 4 ca cel mai mare element!

54322111744322111633322111522222111401112111300001111200000011100000001076543210c


stabilim��cu

c[i,S] >= N c[4,7]=2c[i–1,S] < N c[3,7]=0

4+…….Relu�m cuSS-i (7-4=3)

N N-c[i-1,S]Pân� când N=0.

4+3 54322111744322111633322111522222111401112111300001111200000011100000001076543210c

Parti�ionarea strict descresc�toare Ordonan�are 2

Completarea tabelului dinamic:

pentru i0, S execut�pentru j 0, S execut�

a[i,j] 0;a[0,0] 1;pentru i0, S execut�{pentru j 0, i-1��

a[i,j] a[i-1,j];pentru j i, S��

a[i,j] a[i-1,j]+a[i-1,j-i];}

Reconstituirea solutiei:

repet�i1;câttimp a[i,S]

prof. zoltan szabo - educampion.edu.ro/arhiva/www/arhiva_2009/papers/paper22.pdf · combinatoric...

Documents