Permutacije
Objavljeno: 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
Pripadajoč izhod
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.
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.