005 Permutari

[•wefgef]

Pai tu ai implementat numerele lui Stirling gresite . Cauta pe wikipedia si vei vedea ca exista atat numerele lui Stirling de speta I, cat si de speta a II-a (au semnificatii, recurente, respectiv valori diferite)

[•taloibogdan]

  Nu stiu cum ati reusit sa faceti de 200 si ceva de ms...mie, la testu 5 imi ia 53 ms si la 10 imi ia cel mai mult ->84 ms

[•APOCALYPTO]

la fel cum a mai spus inanitea mea si eddy, poate cineva sa puna si demonstratia ca solutia este numarul stirling de speta I, cred ca nu este  prea evident ca asa este chiar daca merge...

[•Mishu91]

Mai bine îți găsești singur dinamica, decât să cauți de ce sunt numerele lui Stirling sau ale nu știu cui. Așa ai șanse și să înveți ceva din ea.

[•energizerBunny]

Ok. sunt incepator dar totusi... cum scriu eu sirul de numere care rezulta din 200 2 de exemplu ?!
Ca nu vad niciun tip de variabila care sa salveze siruri asa de lungi.
Si mai sunt si pascal 

[•pauldb]

Trebuie sa reprezinti numerele ca siruri (vectori) de cifre si trebuie sa implementezi "de mana" operatiile de care ai nevoie (aduname, inmultire, etc.). Poti sa consulti sectiunea "Numere mari" din acest articol ca sa-ti faci o idee (desi explicatiile sunt in C, poate reusesti sa transpui codul in Pascal).

[•yonatan]

Salut!
Vreau si eu niste ajutor pentru ca nu inteleg cum sa ajung la relatia de la numere stirling.
Uitati cum gandesc eu si va rog frumos sa-mi dati indicatii unde gresesc(daca gresesc) si ce are trebui sa fac sa ajung la recurecta respectiva.
a[n][k] ->numarul de permutari  de n elemente din multimea {1,2,3...n} cu k maxime

este suma din:
       -a[n-1][k-1]*(n-pozitia ultimului maxim) pentru ca putem adauga pe n dupa ultimul maxim si vom avea k maxime <=> daca avem {maxim , e1, e2, e3} avem 4 pozitii(pozitia lui e3 este n-1 iar a lui maxim n-4) in care putem pune pe n (in locul celor 3 virgule sau dupa e3)
       -a[n-1][k]*(pozitia ultimului maxim-pozitia penultimului maxim) pentru n va "bloca" orice maxim care se afla dupa el iar numarul de maxime va ramane k <=>daca avem{maxim1, e1, e2, e3, maxim2} atunci putem pune pe n in locul celor 4 virgule (poz[maxim1]=poz[maxim2-4])
       
       - a[n-1][k+1]*(pozitia[penultim]-pozitie[antepenultim] ) pentru n trebuie sa blocheze 2 maxime deci trebuie pus intre antepenultimul si penultimul maxim
        ...
        -a[ i ][j]*(poz[al k-lea maxim]- poz[al k-1-lea maxim]
         ...
       -a[n-1][n-1]*(poz[al k-lea maxim]-poz[al k-1-lea maixim] =1 putem pune intr-un singur loc al n-lea element

Va rog mult sa ma ajutati.

[•pauldb]

Rezolvarea ta nu e buna pentru ca nu stii pozitiile maximelor.

O problema asemanatoare cu aceasta este problema doipe, care are solutia explicata intr-un articol. Poti sa cauti acolo indicii despre abordarea acestui tip de probleme.

[•popoiu.george]

Imi puteti explica si mie recurenta de la numarul lui Stirling de speta I ? Chiar nu am reusit sa o pricep.

[•ionutz32]

Ideea e ca permutarile de lungime N se obtin prin introducerea lui N, pe rand, pe toate pozitiile, in fiecare permutare de lungime N-1. Sa zicem ca il asezam pe N pe pozitia i (i=1,n). Cum N e numarul maxim, el nu are niciun numar mai mare in stanga, deci determina o maxima. In dreapta lui N nu va fi niciun numar mai mare decat N, ceea ce inseamna ca N e cel mai din dreapta numar cu aceasta proprietate. Cum noi vrem ca permutarea sa aiba K maxime, trebuie ca in stanga lui N (pe pozitiile 1..i-1) sa avem niste numere ce alcatuiesc K-1 maxime. Noi cunoastem S(i-1,k-1), adica numarul de permutari ale multimii {1, 2, … , i-1} cu K-1 maxime. Pentru fiecare astfel de permutare, numerele respective pot fi inlocuite cu oricare i-1 valori care sa respecte relatiile de ordine, iar sirul va avea tot atatea maxime. De exemplu, sirul 2, 1, 3 are 2 maxime. Valorile 1, 2, 3 ar putea fi inlocuite cu alte valori, sa zicem 4, 7, 22, iar sirul 7, 4, 22 va avea tot 2 maxime. Noi trebuie sa completam primele i-1 pozitii cu numere din multimea {1, 2, …, N-1}. Oricare i-1 numere din aceasta multime pot respecta relatiile de ordine care vor duce la existenta a K-1 maxime, deci modul de a completa primele i-1 pozitii e C(n-1,i-1)*S(i-1,k-1). Pentru fiecare i numere fixate la inceput, toate celelalte numere de la 1 la N care au ramas vor completa ultimele N-i pozitii, numarul de posibilitati fiind P(N-i). Deci daca N e pus pe pozitia i, exista C(n-1,i-1)*S(i-1,k-1)*P(N-i) posibilitati, adica (n-1)!/((i-1)!*(n-i)!)*S(i-1,k-1)*(n-i)!=(n-1)!/(i-1)!*S(i-1,k-1)=i(i+1)(i+2)…(n-1)*S(i-1,k-1). Raspunsul problemei se obtine dandu-i lui i toate valorile de la 1 la N, adica vom avea S(n,k)=1*2*…*(n-1)*S(0,k-1)+2*3*…*(n-1)*S(1,k-1)+…+(n-1)*S(n-2,k-1)+S(n-1,k-1)
Pentru forma recurenta, se da (n-1) factor comun:
S(n,k)=(n-1)[1*2*…*(n-2)*S(0,k-1)+2*3*…*(n-2)*S(1,k-1)+…+S(n-2,k-1)]+S(n-1,k-1)=(n-1)*S(n-1,k)+S(n-1,k-1).

[•Bit_Master]

Daca problema asta se face cu numere mari, de ce nu sunt numere mari la indicii?

[•SpiderMan]

In primul rand nu cred ca exista un tag cu numere mari, in al doiela rand ar trebuie facut unul .... 

[•Bit_Master]

In primul rand nu cred ca exista un tag cu numere mari, in al doiela rand ar trebuie facut unul ....  

http://infoarena.ro/cauta-probleme?tag_id%5B%5D=104

_____________

Ce e gdb.exe? Pt ca imi crapa in timpul debug-ului, apoi crapa si MinGW?
gdb.exe nu crapa daca rulez normal programul sau daca dau debug dar fara sa pun la watch nimic.

___mai tarziu___
Am mai facut niste teste si se pare ca gdb crapa daca declari tablourile prea mari, chiar daca ruland normal sau cu debug dar fara sa pui la watch tabloul merge.

[•SpiderMan]

Merci, chiar nu am stiut de el .

[•Bit_Master]

Merci, chiar nu am stiut de el .

infoarena.ro/portal

Am creat eu un mic portal de taguri (neoficial).

[•blasterz]

GDB e ... debug-erul ... http://en.wikipedia.org/wiki/GNU_Debugger

[•Bit_Master]

GDB e ... debug-erul ... http://en.wikipedia.org/wiki/GNU_Debugger

Multumesc.

[•xtreme]

Ce parametrii ar trebui sa pun la o functie care sa imi inmulteasca doua numere mari (vectori) ?

[•Magnus]

Cod:

void mul(int a[],int b[])

(daca vectorul e de int)

[•deiosx]

in  mingw imi da bine pt toate testele, dar evaluatorul imi spune "killed by signal 11" si nu inteleg dc...

[•gabitzish1]

S-ar putea sa accesezi o zona de memorie nedeclarata. Asta e cauza cea mai frecventa.

[•VisuianMihai]

la primul exemplu sunt permutari:
123
132
213
231
312
321
Care sunt cele 3 permutari cu 2 maxime?

[•pauldb]

132
213
231

[•VisuianMihai]

AAA deci si primul termen satisface conditia... Ok mersi

[•repp4radu]

Eu am facut cu long long si am luat 10 puncte.

Ma gandeam sa refac dupa pe numere mari DAR pe exemplul al doilea imi da 34 in loc de 35.

Am folosit formula de recursivitate:

S(n,k) = (n-1)*S(n-1,k) + S(n-1, k-1)

Matricea arata cam asa:

1
1 1
1 3 1
1 10 6 1
1 41 34 10 1

E corect?

PS deasupra diagonalei principale din matrice sunt zerouri.