Differences

This shows you the differences between two versions of the page.

varijacije [2011/12/09 03:14] (current)
jelica.vasiljevic created
Line 1: Line 1:
 +====== Šta su varijacije? ======
 +
 +===Definicije===
 +   *Varijacije k-te klase( **bez ponavljanja** ) skupa A od n elementa je __svaka uredjena k-torka__ različitih elemenata tog skupa.
 +   *Broj varijacija bez ponavljanja k-te klase je n(n-1)(n-1)...(n-k+1).
 +
 + 
 +
 +==Postavka problema==
 +
 +Za zadati prirodan broj n treba generisati sve varijacije k-te klase skupa A={1,2,..n}. Na primer za n=4 i k=3 program bi trebalo da izgeneriše sledeci varijacije :
 +
 +1 2 3\\
 +1 2 4\\
 +1 3 4\\
 +1 3 4\\
 +2 1 3\\
 +...\\
 +Biće ih ukupno 24 (4*3*2=24).
 +
 +=== Rešnje problema u programskom jeziku C===
 +\\
 +Ove je prikazano rešenje koje koristi rekurziju:\\
 +<code C>
 +#include <stdio.h>
 +#include <stdlib.h>
 +
 +void varijacije(int n,int k,int pozicija, int niz[],int ubacen[])
 + {
 + int i;
 +
 + if (pozicija > k)
 + {
 + for (i=1;i<k+1;i++)
 + printf("%d ",niz[i]);
 + printf("\n");
 + }
 + else
 + {
 + for (i=1;i<n+1;i++)
 + {
 + if (ubacen[i]==0)
 + {
 + niz[pozicija]=i;
 + ubacen[i]=1;
 + varijacije(n,k,pozicija+1,niz,ubacen);
 + ubacen[i]=0;
 + }
 + }
 + }
 +
 + }
 +
 +main()
 +{
 +int *niz,*ubacen;
 +int n,k;
 +printf("Unesite broj elemenata skupa i klasu\n");
 +printf("n:");
 +scanf("%d",&n);
 +printf("k:");
 +scanf("%d",&k);
 +niz=(int *)malloc((k+1)*sizeof(int));
 +ubacen=(int*)calloc(n+1,sizeof(int));
 +varijacije(n,k,1,niz,ubacen);
 +}
 +</code>
 +
 +== Objašnjenje==
 + \\
 +Promenljive:\\
 +niz : niz u koji se smešta izgenerisana varijacija. On ima k+1 elemenata zbog indeksiranja u C-u koja kreću od 0\\
 +ubacen: niz integer-a koji ima n elemenata.Na početku su svi njegovi elementi inicijalizovani sa 0 (( f-ja calloc() )). Niz je uveden da označi da li je neki element uključen u tekuću varijaciju ili ne (0- nije, 1- uključen je).\\
 +n : broj elemenata skupa A čije varijacije k-te klase generišemo\\
 +k : klasa\\
 +pozicija : pozicija za koju trenutno tražimo element. Pošto su varijacije k-te klase, ona može biti najviše k.\\
 +Neka je n=4 a k=3;\\
 +Pri prvom pozivu f-je varijacije() u niz se na 1. poziciju stavlja 1, i ubacen[1]=1, dakle označavamo da je 1 već ušlo u tekuću varijaciju (posto su varijacije bez ponavljanja jedan element može najviše jednom da se pojavi).
 +U ovom trenutku niz je {0,1,0,0}(( ovde je navedeno 4 elementa zbog indeksiranja u C-u koja počinju od 0.Vredosti koje  figurišu u ovom programu nalaze se na indeksima od 1 pa do k)).
 +Zatim se vrši rekurzivan poziv f-je varijacije() (prethodna f-ja neće moći da pređe na sledeću instrukciju (ubacen[i]=0),sve dok se ne do kraja ne izvrši rekurzivno pozvana f-ja) sa izmenjenim parametrom pozicija= pozicija +1 tj. za poziciju 2 jer smo naši odgovarajuću vrednost za pozicija=1. Ova f-ja prihvata izmenjene podatke i u nizovima niz i ubacen ((nizovi su pokazivači)).Zbog toga ona u okviru for petlje prvi put nailazi na ubacen=0 za i=2. Ubacuje 2 u niz, ponovo poziva varijacije() sa promenjenim parametrima. Ova f-ja sad prvi put nailazi da je ubacen[i]=0 za i=3,i ubacuje 3 u niz. Sada i ona rekurzivno poziva f-ju varijacije() za vrednost pozicija=4. Pri izvršavanju ove f-je biće ispunjen uslov da je pozicija > 3, stampaće se \\
 +1 2 3\\
 +i ova f-ja završava sa radom. Sada se redom završavaju f-je : najpre f-ja koja je u niz ubacila 3, vraća ubacen[3]=0,vraća se u for-petlju, povećava i na 4 i ponovo poziva varijacije() za poziciju 4 koja kao rezultat daje \\
 +1 2 4\\  
 +...
 +
 +== Primedba==
 +\\
 +Program vrši generisanje samo varijacija skupa oblika A={1,2,...n}. Poboljšana verzija bi bila da radi sa bilo kojim skupom (slova, znakovi, višecifreni brojevi...). To može da se reši tako da se svakom elementu pridruži indeks koji odgovara poziciji tog elementa u polaznom skupu. Štampaju se umesto niz[i] ,polazni_niz[niz[i]].
 +
 +
 + 
 
varijacije.txt · Last modified: 2011/12/09 03:14 by jelica.vasiljevic
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki