[es] - Permutacije, pomoc

echelon
Ne radim ništa...a da ti pravo kažem,
nemam ni kad...
Sam svoj majstor; elektronika/PC
CAP

Član broj: 8585
Poruke: 174
*.tel.net.ba.

+2 Profil

Permutacije, pomoc

^{17.08.2008. u 15:50 - pre 191 meseci}

pozdrav.
imam jedan zadatak cije rjesenje ne razumijem. ako ima neka dobra dusa da mi objasni na svoj nacin.
zadatak glasi ovako:
"Koliko ima različitih riječi dobivenih permutiranjem slova u riječi MATEMATIČARKA u kojima
nema susjednih slova A?"

nema smisla da prepisujem rjesenje kad ga ne razumijem....

hvala.

Odgovor na temu

zzzz
milan kecman
bluka

Član broj: 11810
Poruke: 2154
92.241.128.*

+196 Profil

Re: Permutacije, pomoc

^{17.08.2008. u 16:50 - pre 191 meseci}

Pokušaj sa nešto lakšim zadatkom pa onda primjeni ista pravila na taj složeniji.

Naprimjer riječ MAMA.

Da su sva slova različita bilo bi P=4!=24 permutacije.
Ali imamo 2xM i 2xA pa rezultat dijelimo sa 2!*2!.Rezultat je dakle
Q=24/4=6.(MMAA;MAMA;MAAM;AMMA;AMAM;AAMM)

Ali imamo još i zahtjev da A ne može biti uz A.
A to se može desiti tri puta, ili drukčije rečeno n-1=4-1 puta.

Oduzmimo to od 6 pa ispade samo 3.(MAMA;AMMA;AMAM)

Sad je valjda lakše riješiti?
Ali pazi na to da tamo ima 4xA, pa na ovo treba malo utrošiti truda.

________________________________

Najbolja kritika formule za Sagnac effect:
https://www.omicsonline.org/op...090-0902-1000189.php?aid=78500

OK evo prave formule:P=2wft^2 [period]

Odgovor na temu

Matemaciklista

Član broj: 191131
Poruke: 1
*.eunet.yu.

Profil

Re: Permutacije, pomoc

^{20.08.2008. u 17:39 - pre 190 meseci}

Code:

/**
* Vraća broj načina na koje je moguće rasporediti k slova "A" na n mesta,
* tako da su medjusobno udaljena bar d mesta.
*
* Npr.
*
* p(4,9,2)=15
*
* 1  ..A.A.A.A
* 2  .A.A.A.A.
* 3  .A.A.A..A
* 4  .A.A..A.A
* 5  .A..A.A.A
* 6  A.A.A.A..
* 7  A.A.A..A.
* 8  A.A.A...A
* 9  A.A..A.A.
* 10 A.A..A..A
* 11 A.A...A.A
* 12 A..A.A.A.
* 13 A..A.A..A
* 14 A..A..A.A
* 15 A...A.A.A
*
*/
int p(int k, int n, int d){
    int m=d*(k-1)+1;
    if(k<=0||n<=0||n<m||d<=0)return 0;
    if(m==n)return 1;
    if(k==1)return n;
    return p(k-1,n-d,d)+p(k,n-1,d);
}

U konkretnom zadatku ("MATEMATIČARKA"), reč sadrži 13 slova, od kojih 4 "A", 2 "M" i 2 "T" dok se ostala slova pojavljuju jednom. Slova "A" je moguće rasporediti na

p(4,13,2)=210

različita načina. Za svaki od njih preostala slova je moguće rasporediti na

(13-4)!/(2!*2!)=90720

različita načina, pa je rešenje 210*90720=19051200.

Što se tiče funkcije p, evo par objasnjenja u slučaju da nije najjasnije...

m je minimalan broj polja potreban za smeštanje k slova "A" medjusobno udaljena najmanje d polja.

Sledeće 3 linije manje-više govore za sebe.

Linija

Code:

p(k-1,n-d,d)+p(k,n-1,d);

znači da se do rezultata dolazi rekurzivno. Pogledaj svaki od ovih primera, s leva na
desno

Code:

   x.x
  x.x.
  x..x
x.x..
x..x.
x...x
x.x...
x..x..
x...x.
x....x

   x.x.x
  x.x.x.
  x.x..x
  x..x.x
x.x.x..
x.x..x.
x.x...x
x..x.x.
x..x..x
x...x.x
x.x.x...
x.x..x..
x.x...x.
x.x....x
x..x.x..
x..x..x.
x..x...x
x...x.x.
x...x..x
x....x.x

   x.x.x.x
  x.x.x.x.
  x.x.x..x
  x.x..x.x
  x..x.x.x
x.x.x.x..
x.x.x..x.
x.x.x...x
x.x..x.x.
x.x..x..x
x.x...x.x
x..x.x.x.
x..x.x..x
x..x..x.x
x...x.x.x
x.x.x.x...
x.x.x..x..
x.x.x...x.
x.x.x....x
x.x..x.x..
x.x..x..x.
x.x..x...x
x.x...x.x.
x.x...x..x
x.x....x.x
x..x.x.x..
x..x.x..x.
x..x.x...x
x..x..x.x.
x..x..x..x
x..x...x.x
x...x.x.x.
x...x.x..x
x...x..x.x
x....x.x.x

Pogledaj poslednji deo, gde su 4 x-a raspoređena na 10 mesta i gde se x uvek nalazi na prvom. Ukoliko izbrišeš prva dva polja s leva, dobićeš sve moguće načine da se rasporede 3 x-a (jedan je izbrisan) na 8 mesta. Tom broju je potrebno dodati sve moguce nacine da se x rasporedi na 9 mesta (prvo mesto je već iskorišćeno).

Ili malo uprošćenije:

(broj načina da smestiš 4 x-a na 10 mesta)
=
(broj načina da smestiš 4 x-a na 10 mesta, tako da se x nalazi na prvom)
+
(broj načina da smestiš 4 x-a na 10 mesta, tako da se x ne nalazi na prvom)

Odgovor na temu