Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

Permutacije

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Permutacije

OdgovorNapisal/-a lukazlatecan » So Jun 03, 2017 11:30 am

Mislimo si neko permutacijo na množici n elementov. Če s to permutacijo po večkrat zaporedoma premešamo naše elemente, bo prej ali slej prišel vsak element nazaj na svoje prvotno mesto. Najmanjšemu številu izvedb permutacije, po katerem pride vsak element nazaj na prvotno mesto, pravimo red te permutacije.

Primer: Oglejmo si permutacijo [math]. Z eno uporabo te permutacije torej iz prvotnega vrstnega reda (1,2,3,4,5,6) nastane (3,6,4,1,5,2); iz slednjega nato, če našo permutacijo uporabimo še drugič, nastane (4,2,1,3,5,6); iz tega po tretji uporabi naše permutacije nastane (1,6,3,4,5,2), nato po četrti uporabi nastane (3,2,4,1,5,6), po peti (4,6,1,3,5,2) in po šesti (1,2,3,4,5,6). Permutacijo smo torej morali izvesti šestkrat, da smo prišli nazaj na začetni razpored, zato je red te permutacije enak 6.

Naloga
Znano je, da obstaja n! različnih permutacij n elementov. Napišite program, ki prebere n in izračuna povprečje redov vseh teh n! permutacij.

Vhodni podatki
V prvi vrstici je celo število n; zanj velja 1≤n≤50.

Izhodni podatki
Izpišite eno samo število – povprečje redov vseh permutacij n elementov, zaokroženo navzdol na celo število.

Nasvet: Če vaš programski jezik ne podpira dela z velikimi celimi števili, je za to nalogo dovolj dober tudi tip double. Za 1<n≤50 je povprečje vedno za več kot 0,005 oddaljeno od najbližjega celega števila, torej je malo verjetno, da bi zaradi zaokrožitvenih napak pri delu s plavajočo vejico na koncu, po zaokrožitvi povprečja na celo število, dobili napačen rezultat.

Primer vhoda

Koda: Izberi vse

2


Pripadajoč izhod

Koda: Izberi vse

1


Komentar
Pri n=2 imamo dve permutaciji: [math], ki ima red 1, in [math], ki ima red 2. Povprečje njunih redov je torej 1,5; ko to zaokrožimo navzdol na celo število, dobimo rezultat 1.
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

Ptolomej
Prispevkov: 253
Pridružen: Po Apr 24, 2017 9:02 pm
Kraj: Celje

Re: Permutacije

OdgovorNapisal/-a Ptolomej » So Jun 03, 2017 4:02 pm

Vsako permutacijo lahko zapišemo kot produkt ciklov. Kaj to pomeni?
Razložimo to kar na našem primeru [math].

Vidimo, da pri tej permutaciji gre 1 v 3, 3 gre v 4 in 4 gre v 1, kar običajno zapišemo [math] in to imenujemo 3-cikel.
Podobno gre 2 v 6 in 6 v 2 in imamo 2-cikel [math]. Samo 5 gre v vase in to lahko zapišemo [math].

Potem lahko zapišemo našo permutacijo takole:
\[\binom{1\ 2\ 3\ 4\ 5\
6}{3\ 6\ 4\ 1\ 5\ 2} = (1,3,4)\circ (2,6)\circ (5)\]

Običajno števila (elemente), ki gredo vase sploh ne zapišemo, saj je jasno, da se nezapisana števila preslikajo vase, torej bi mi imeli:
\[\binom{1\ 2\ 3\ 4\ 5\
6}{3\ 6\ 4\ 1\ 5\ 2} = (1,3,4)\circ (2,6)\]

Poglejmo še en primer.
\[\binom{1\ 2\ 3\ 4\ 5\
6\ 7\ 8}{7\ 6\ 3\ 1\ 2\ 5\ 4\ 8} = (1,7,4)\circ (2,6,5)\]

Obratno, iz produkta ciklov lahko nazaj zapišemo celotno permutacijo. Recimo, da permutiramo števila od 1 do 9. Potem je
\[(1,3,5,8)\circ (2,9) = \binom{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}{3\ 9\ 5\ 4\
8\ 6\ 7\ 1\ 2}\]

Red vsakega cikla je natanko njegova dolžina. Ni težko videti, da je red vsake permutacije enak najmanjšemu skupnemu večkratniku ciklov. No, morda bo ta ideja o ciklih pomagal pri razreševanju naloge. :)
Meje mojega jezika so meje mojega sveta.- Ludwig Wittgenstein

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Re: Permutacije

OdgovorNapisal/-a lukazlatecan » So Jun 03, 2017 7:07 pm

Če pogledamo na primer razcep naše permutacije na cikle: (1,3,4)(2,6)(5)
Imamo tri cikle katerih dolžine so 3,2,1. Najmanjši skupni večkratnik je torej: v(3,2,1)=6. Se pravi lahko rečemo da ima taka permutacija red 6.
Ugotoviti moramo še torej koliko je takih permutacij, ki so sestavljene iz 3-cikla, 2-cikla in 1-cikla, kar ne bi smelo biti pretežko ...
Pogledali smo si primer, za permutacijo sestavljeno iz 3-cikla, 2-cikla in 1-cikla. Koliko pa je različnih oblik permutacij? Pomagamo si lahko z razčlenitvijo naravnega števila na pozitivne naravne sumande, pri čemer sumandi predstavljajo dolžine ciklov.
Za namig/pomoč prilagam naslednji program, ki razčleni število n na sumande.

Koda: Izberi vse

public class Sumandi {
    public static void main(String[] args) {
        int n = 5;
        razcepiNaSumande(n, n, "");
    }

    public static void razcepiNaSumande(int n, int m, String sestevek){
        if(n == 0){
            System.out.println(sestevek);
            return;
        }
        for(int i = Math.min(n,m); i>=1; i--){
            razcepiNaSumande(n-i, i, sestevek + " " + i);
        }
    }
}
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler


Vrni se na “Finale”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost