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)