Pagini: 1 [2] 3 4   În jos
  Imprimă  
Ajutor Subiect: 015 Permutari II  (Citit de 28932 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #25 : Aprilie 14, 2006, 09:59:05 »

Dupa ce problema asta a fost rezolvata de vreo 135 oameni nu crezi ca e cam absurd sa fie exemplele gresite? Mai citeste problema de multe ori pana intelegi ce vrea...
Memorat
dragos_d
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #26 : Martie 11, 2007, 23:33:24 »

Va rog frumos sa-mi oferiti si mie o indicatie pentru aceasta problema
Memorat
nash
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 109



Vezi Profilul
« Răspunde #27 : Aprilie 19, 2007, 13:05:15 »

 ok .. algoritmul de rezolvare e clasic .. cu toate astea mai mult de 85 de punde nu iau ..
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #28 : Iulie 03, 2007, 17:51:27 »

Citat
8
1 5 2 3 4 8 6 7                  12

imi explica cineva exemplul de mai sus?
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #29 : Iulie 03, 2007, 18:54:34 »

p1: 1 5 2 3 4 8 6 7 
p2: 1 4 5 2 3 7 8 6
p3: 1 3 4 5 2 6 7 8
p4: 1 2 3 4 5 8 6 7
p5: 1 5 2 3 4 7 8 6
p6: 1 4 5 2 3 6 7 8
p7: 1 3 4 5 2 8 6 7
p8: 1 2 3 4 5 7 8 6
p9: 1 5 2 3 4 3 6 7 8
p10: 1 4 5 2 3 8 6 7
p11: 1 3 4 5 2 7 8 6
p12: 1 2 3 4 5 6 7 8

Deci raspunsul e 12.
Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #30 : Iulie 04, 2007, 20:11:21 »

Imi dati va rog un indiciu pt teste 1 5 si 10? Iau TLE.. si nu prea stiu cum sa scap de el..

Aflu pentru fiecare numar in cati pasi ajunge pe pozitia finala, avand un while care il intoarce pe p1[p1[p1[...]]]... si apoi fac cmmmc al acestor numere. Si daca scot cmmmc-ul, tot da TLE pe testele alea. Am incercat sa tratez particular cazul 2 3 4 ... n 1 dar tot nu vrea...

Cum as putea face mai eficient?  Think
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #31 : Iulie 04, 2007, 20:26:47 »

Marcheaza toate numerele prin care treci de-a lungul unui ciclu si pentru alea nu va mai trebui sa calculezi iar.
Complexitatea scade asa de la O(n2) la O(n)
Memorat
Dastas
Vorbaret
****

Karma: 11
Deconectat Deconectat

Mesaje: 170



Vezi Profilul
« Răspunde #32 : Iulie 05, 2007, 14:29:17 »

Multumesc, mi-a iesit!  Thumb up
Memorat
mordred
Client obisnuit
**

Karma: -39
Deconectat Deconectat

Mesaje: 51



Vezi Profilul
« Răspunde #33 : Septembrie 03, 2008, 12:51:48 »

ok .. algoritmul de rezolvare e clasic .. cu toate astea mai mult de 85 de punde nu iau ..

chiar daca a trecut mult timp, 85 de puncte sunt pentru solutia brute-force ( O(n2) )
am testat eu aici
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #34 : Februarie 24, 2009, 20:39:34 »

Ma poate ajuta cineva, pentru problema aceasta eu fac o metoda mai mult babeste:
1)citesc datele de intrare
2) cat timp permutarea curenta nu este egala cu permutarea identica atunci:
           p[ i ]=v[p[ i ]];
           k++;
3) Afisez  k.
p[]= retin permutarea curent  si v[] este permutarea introdusa din fisier.
Cum as putea sa mai optimizez?
Si desi n-are legatura cu subiectul  exista  Numarul lui Stirling de speta 1?
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #35 : Februarie 24, 2009, 21:00:45 »

Daca iti scrii toate puterile unei permutari (cred ca gasesti si pe forum toate formele scrise) vei observa ca pe o pozitie anumite elemente se tot repeta. Pentru exemplul trei pe pozitia 2 vor aparea 5, apoi 4, apoi 3 si 2, dupa care se reia de la capat. Tu tre sa determini gradul permutarii care are toate elementele pe pozitiile dorite, iar acest grad este cmmmc-ul repetitiilor tuturor elementelor. In al 3lea exemplu 1 ramane pe prima pozitie in orice permutare, 2,3,4,5 se repeta din 4 in 4, iar 6, 7 si 8 din 3 in 3, deci rezultatul cerut va fi cmmmc(1, 3, 4) = 12. Daca te chinui otzara, poti determina din cat in cat se repeta fiecare element in O(N). Smile
Sper ca am fost de folos, si totodata nu prea explicit Smile 
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #36 : Februarie 24, 2009, 21:43:45 »

Si desi n-are legatura cu subiectul  exista  Numarul lui Stirling de speta 1?

Da, Numarul lui Stirling de speta I reprezinta numarul de permutari ale elementelor {1,2,...,n} ce contin exact m cicluri. ( Secventa ( c1,c2, ... , ck ) se numeste ciclu in permutarea p, daca p(c1)=c2, p(c2)=c3, ... ,p(ck) = c1. )
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #37 : Februarie 25, 2009, 06:52:34 »

@Andrei Misarca multumesc pentru explicatie, am citit comentarile de aici dar nu intleelgeam , din ce obtii cmmmc Smile
@Marcu Florian: exista si o relatie de recurenta Think
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #38 : Februarie 25, 2009, 17:59:35 »

s(n,m) - nr lui stirling de speta I.

* s(n,m) = 0, pt n<m
* s(n,m) = s(n-1,m-1) + n*s(n-1,m).

Explicatia: Elementul n poate forma singur cel de-al m-lea ciclu, sau poate fi inserat in cele m cicluri deja existente (in n moduri). Sper sa nu fi gresit.  Smile
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #39 : Martie 02, 2009, 18:45:07 »

conditia   n<m  este necesara dar nu suficienta, daca ai n=4,m=2 o sa dea o bucla la infinit. Am gasit
aici , un articol interesant Smile
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #40 : Martie 02, 2009, 19:35:47 »

Nu va intra in ciclu, pentru ca nu face decat sa numere niste permutari. Nu le si genereaza.  Smile
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #41 : Martie 03, 2009, 09:25:55 »

Am scris o functie recursiva si condtia de oprire am pus-o n<m, cnd returneazsa 0:
Cod:
int s(int n,int m)
  {
   if(n<m) return 0;
   return s(n-1,m-1)+n*s(n-1,m);
  }
dac dai n=4; m=2; mereu  n>m,  pentru ca scazi mereu 1 Tongue
Memorat
andrici_cezar
De-al casei
***

Karma: -47
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #42 : Martie 05, 2009, 17:01:01 »

La testul 2 permutarile sunt:
p1: 3 4 1 2
p2: 4 1 2 3
p3: 1 2 3 4
p4: 2 3 4 1
Astea sunt?
Si daca da la testul 3 unde e 8 dc este 12 dc nu sunt la fel? Whistle
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #43 : Martie 05, 2009, 17:18:25 »

La testul 2, permutarile sunt:
p1: 2 3 4 1
p2: 3 4 1 2
p3: 4 1 2 3
p4: 1 2 3 4

Pentru testul 3 s-a mai explicat de ce raspunsul e 12:
p1: 1 5 2 3 4 8 6 7 
p2: 1 4 5 2 3 7 8 6
p3: 1 3 4 5 2 6 7 8
p4: 1 2 3 4 5 8 6 7
p5: 1 5 2 3 4 7 8 6
p6: 1 4 5 2 3 6 7 8
p7: 1 3 4 5 2 8 6 7
p8: 1 2 3 4 5 7 8 6
p9: 1 5 2 3 4 3 6 7 8
p10: 1 4 5 2 3 8 6 7
p11: 1 3 4 5 2 7 8 6
p12: 1 2 3 4 5 6 7 8

Deci raspunsul e 12.
Memorat
andrici_cezar
De-al casei
***

Karma: -47
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #44 : Martie 05, 2009, 17:25:51 »

asta am mai vazut pe acest forum dar p si k ce inseamna mai exact?
sau mai bine zimi cum ai facut prima permutare ca poate inteleg asa:D
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #45 : Martie 05, 2009, 17:42:11 »

p reprezinta permutarea, iar k puterea ei
Citat
Pk(i) =
    * P(i), atunci cand k=1
    * P(Pk-1(i)), pentru k > 1
Pt testul 2 de exemplu p2(1) = p(p(1)) = p(2) = 3 Smile
Memorat
andrici_cezar
De-al casei
***

Karma: -47
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #46 : Martie 06, 2009, 09:26:33 »

aha ms
Memorat
lsorin_94
Strain


Karma: -8
Deconectat Deconectat

Mesaje: 23



Vezi Profilul
« Răspunde #47 : Aprilie 09, 2009, 11:16:19 »

poate sa imi spuna cnva ce ins bijectiva:? Idea Pray Brick wall
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #48 : Aprilie 09, 2009, 11:22:20 »

http://airinei.omad.ro/catmate/2FUNCTIA%20PUTERE%20CU%20EXPONENT%20NATURAL.pdf

De ce nu cauti pe google? Ai gasi mai multe informatii.  Thumb up
Memorat
Alexa_ioana_14
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #49 : Octombrie 03, 2009, 20:34:59 »

Am retinut intr-un vect v nr de poz dupa care se repta elementul i, si daca perioada a mai fost gasita o ignor.Am calculat cmmmc dupa formula: cmmmc=v[1]*...*v[ultimul element]/cmmdc si iau pe majoritatea testelor wa. Am incercat si cu numere mari. Are cineva idee unde busesc sursa?  Brick wall

Ps:Multumesc anticipat!
Memorat
Pagini: 1 [2] 3 4   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines