Posted By: Aldar (posledni mohykan) on 'CZriddles' Title: Re: Lloydova patnactka Date: Fri Mar 27 19:06:40 1998 > Tak to kriterium resitelnosti uz vime... Je to vice mene znamenko > permutace, bez 0 (prazdneho policka) (jednoduse se presoupa do pozice > [4;4]) A znamenko se vypocita takto: > > (-1)^(pocet inverzi) > (-1)^(pocet cyklu liche delky) > (-1)^(transpozic) > inverze: Usporadame-li prvky X do posloupnosti (1,2,...,n) (kde n je pocet prvku X). muzeme permutaci znazornit tabulkou p(1) p(2) P(3) .... p(n) ^ ^ ^ ^ ^ | | | | | 1 2 3 .... n Kazdou dvojici i<j, kde p(i)>p(j) nazveme inverzi tabulky (permutace) pozn.: to je vlastne to, co tady vise popisoval Xofon... cyklus: Jakoukoliv usporadanou n-tici (x1,x2,...,xn), pokud p(xi)=p(xi+1) pro i=1,..,n-1 a p(xn)=x1 nazveme cyklem permutace p delky n-1 jinymi slovy: "cilova" permutace zjistujeme cyklus /--------------- /--------------- | 1 | 2 | 3 | 4 | | 5 | 1 | 2 | 4 | ----------------- ----------------- | 5 | 6 | 7 | 8 | | 7 | 6 | 3 | 8 | ----------------- ----------------- | 9 |10 |11 |12 | | 9 |10 |11 |12 | ----------------- ----------------- |13 |14 |15 | | |13 |14 |15 | | ---------------/ ---------------/ takze zjistime delku cyklu na [1;1], je tam c. 5, na miste petky je 7, na miste sedmicky je 3jka, na miste 3 je 2, na miste 2 je 1 a na miste 1 je zase 5 5->7->3->2->1-> 5->..... takze mame cyklus delky 4, coz je sude cislo, takze se nezapocitava... jiny cyklus tam neni, takze to nema reseni... transpozice: permutaci p : X -> X bude transpozice, existuje-li x<>y z X tak, ze p(x)=y, p(y)=x a jinak p(z)=z pro z z X-{x,y} jinymi slovy: pokud soupneme prazne policko, tak udelame 1 transpozici nebo taky, pokud prohodime kterekoliv 2 policka... > > Ale jinak: > > Nevite nekdo, kdyz uz vim, ze to ma reseni, kolik je maximalni odhad > > poctu tahu k vyreseni? Urcite je to podstatne mensi cislo, nez pocet > > vsech stavu, ktere vedou k reseni (n!/2 ; n=16). Nejak to vychazi na cca > > 50... > Jak to myslis? Maximalni odhad. Nemas na mysli odhad minimalniho poctu tahu > pri znamem zadani? Slo mi o to, ze pri hledani reseni prohledavanim do hloubky staci hledat do nejake max. urovne, reseni by melo byt nad ni (samozrejme, pokud hledame nejake optimalnejsi a nestaci nam prohledavani do hloubky s nejakym algoritmem, dokud nenarazime na reseni...(vetsinou to byva takovych 30000 tahu ;-)) > Alnagon > > <Lepe, kdyz se certi zeni, nez kdyz se zeny certi> Doufam, ze to bylo srozumitelne... takovy drobny vytazek z algebry... tento post mel aspon jednu vyhodu, konecne jsem se to naucil... :-) Cuz Aldar