14. Računanje kombinacija. - rešenje
Varijacije bez ponavljanja. Permutacije. Kombinacije bez ponavljanja.
Na sledećoj slici je pokazano kako se kreiraju i izračunavaju varijacije od n elemenata k-te klase, bez ponavljanja, na primeru, šta su permutacije, u čemu je razlika između varijacija i kombinacija bez ponavljanja i kako da se njihov broj odredi.
Slika 1: Kombinatorika: Varijacije i kombinacije bez ponavljanja, od n elemenata, k-te klase na primeru.
Neka je dat skup elemenata N i neka su to u posmatranom primeru prirodni brojevi od 1-5. Od tih brojeva, prikazeno je na slici 1, kako se formiraju varijacije 2.(levo) i 3.(desno) klase od 5 elemenata. Broj n=5 elemenata potiče od skupa N, a to je broj elemenata dostupan za pravljenje varijacija. Npr. 1-2, je varijacija klase 2 jer dve cifre se nalaze u varijaciji, dok 1-2-3, je varijacija kase 3.
Da bi smo dobili ukupan broj varijacija od 5 elemenata 2. klase, posmatrajmo na koliko različitih načina je moguće izabrati prvu cifru iz jedne varijacije, a to je zapravo u ovom primeru 5(n), gde je n broj elemenata skupa N.
Na sledećem mestu je moguće izabrati za 1 manji broj različitih cifara, ako su varijacije bez ponavljanja, jer je jedan element skupa već "rezervisan" za prvo mesto. Dakle imamo 5 grupa varijacija sa cifrom 1 na prvom mestu, 5 grupa sa cifrom 2 na prvom mestu itd. što znači množimo sa brojem mogućnosti na 2. mestu, što je u ovom primeru 4.
Dakle broj varijacija od 5 elemenata 2 klase je:
Da bi smo dobili ukupan broj varijacija od 5 elemenata 2. klase, posmatrajmo na koliko različitih načina je moguće izabrati prvu cifru iz jedne varijacije, a to je zapravo u ovom primeru 5(n), gde je n broj elemenata skupa N.
Na sledećem mestu je moguće izabrati za 1 manji broj različitih cifara, ako su varijacije bez ponavljanja, jer je jedan element skupa već "rezervisan" za prvo mesto. Dakle imamo 5 grupa varijacija sa cifrom 1 na prvom mestu, 5 grupa sa cifrom 2 na prvom mestu itd. što znači množimo sa brojem mogućnosti na 2. mestu, što je u ovom primeru 4.
Dakle broj varijacija od 5 elemenata 2 klase je:
V52=5*4 = 20
Treba dalje uočiti, da ako se klasa poveća za 1, dakle ako je k=3, treba dodati još jednu cifru u postojeću varijaciju klase 2. klase, tako da se broj mogućnosti povećava onoliko puta, koliko je moguće varirati element na trećem mestu u varijaciji, a to je u primeru za 1 manje nego na prethodnom mestu, dakle 3(5-2), jer smo dva elementa već ranije postavili. Svako sledeće povećanje bi dodalo za (n-k+1) novih mogućnosti, pa je formula za broj varijacija bez ponavljanja od n elemenata klase k:
Vnk=n*(n-1)*(n-2)*...*(n-k+1)
Specijalan slučaj varijacija kada je klasa jednaka broju elemenata, dakle kad je n=k nazivaju se permutacije od n elemenata i računaju se:
P=n*(n-1)*(n-2)*...*1= n!
Broj kombinacija bez ponavljanja
Ako posmatramo primer za klasu 2 i 3 može se uočiti sledeće:
Varijacije 1-2 i 2-1 su dve različite varijacije, ali je u pitanju ista kombinacija, jer redosled elemenata u varijaciji kod kombinacije nije bitan, već samo cifre, kao "grupa". Broj kombinacije u tom slučaju 2 puta manji.
U slučaju 3. klase to bi bilo npr: 1-2-3,1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1 predstavlja 6 različitih kombinacija, ali je reč o jednoj kombinaciji. Dakle u slučaju klase 3, broj kombinacija je 2*3=6 puta manji nego broj varijacija.
U opštem slučaju za n elemenata klase k, broj varijacija je mani k!(k faktorijel) puta, a to je zapravo broj permutacija od k elemenata.
Broj kombinacija od n elemenata k-te klase se dakle izračunava:
Varijacije 1-2 i 2-1 su dve različite varijacije, ali je u pitanju ista kombinacija, jer redosled elemenata u varijaciji kod kombinacije nije bitan, već samo cifre, kao "grupa". Broj kombinacije u tom slučaju 2 puta manji.
U slučaju 3. klase to bi bilo npr: 1-2-3,1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1 predstavlja 6 različitih kombinacija, ali je reč o jednoj kombinaciji. Dakle u slučaju klase 3, broj kombinacija je 2*3=6 puta manji nego broj varijacija.
U opštem slučaju za n elemenata klase k, broj varijacija je mani k!(k faktorijel) puta, a to je zapravo broj permutacija od k elemenata.
Broj kombinacija od n elemenata k-te klase se dakle izračunava:
Cnk=Vnk/K!
Cnk=n*(n-1)*(n-2)*...*(n-k+1)/K!
Cnk=n*(n-1)*(n-2)*...*(n-k+1)/K!
U nastavku je dato rešenje zadatka u programskom jeziku "c":
Rešenje zadatka - kod:
#include <stdio.h>
#include <math.h>
/*funkcija koja određuje vrednost faktorijela nekog celog broja*/
int faktorijel(int x)
{
int F;
F=1;
while(x>1)
{
F=F*x;
x--;
}
return F;
}
int kombinacije(int n1,int k1)//5,3
{
int K,T;
K=1;
T=n1;
while(T>n1-k1){//5>2,4>2,3>2
K=K*T; //K=1*5=5; K=5*4=20; K=20*3=60
T--;
}
int brKomb=K/faktorijel(k1); //brKomb=60/6=10
return brKomb; //return 10
}
int main()
{
int n,k,p,S=0;
printf("n=?,k=?,p=?\n");
scanf("%d%d%d",&n,&k,&p);
for(int pi=0; pi<=p; pi++)
{
int koef=(int)pow(-1,pi);
int komb=kombinacije(n,k+pi); //Pozifa funkciju koja računa broj kombinacija od n elemenata klase k+pi
printf("%d + %d * %d\n",S,koef,komb);
S=S+koef*komb;
}
printf("%d\n",S);
return 0;
}
#include <math.h>
/*funkcija koja određuje vrednost faktorijela nekog celog broja*/
int faktorijel(int x)
{
int F;
F=1;
while(x>1)
{
F=F*x;
x--;
}
return F;
}
int kombinacije(int n1,int k1)//5,3
{
int K,T;
K=1;
T=n1;
while(T>n1-k1){//5>2,4>2,3>2
K=K*T; //K=1*5=5; K=5*4=20; K=20*3=60
T--;
}
int brKomb=K/faktorijel(k1); //brKomb=60/6=10
return brKomb; //return 10
}
int main()
{
int n,k,p,S=0;
printf("n=?,k=?,p=?\n");
scanf("%d%d%d",&n,&k,&p);
for(int pi=0; pi<=p; pi++)
{
int koef=(int)pow(-1,pi);
int komb=kombinacije(n,k+pi); //Pozifa funkciju koja računa broj kombinacija od n elemenata klase k+pi
printf("%d + %d * %d\n",S,koef,komb);
S=S+koef*komb;
}
printf("%d\n",S);
return 0;
}
|
Prethodno
|< Funkcije u C/C++ jeziku -primeri |
Sledeće
Algoritmi-primeri >| |