Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

permutacije
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
sir1
Gost





PostPostano: 20:35 ned, 19. 9. 2004    Naslov: permutacije Citirajte i odgovorite

Ima li koja dobra duša da mi riješi ovaj zadatak(dva)?

Napisite program koji ucitava neku rijec i ispisuje sve permutacije slova tih rijeci.
npr. sad -> sda, ads, asd, dsa, das

i koji ispisuje sve permutacije nekog broja
npr. 123 -> 132,231,213,312,321
Ima li koja dobra duša da mi riješi ovaj zadatak(dva)?

Napisite program koji ucitava neku rijec i ispisuje sve permutacije slova tih rijeci.
npr. sad -> sda, ads, asd, dsa, das

i koji ispisuje sve permutacije nekog broja
npr. 123 -> 132,231,213,312,321


[Vrh]
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 21:15 ned, 19. 9. 2004    Naslov: Citirajte i odgovorite

[code:1]int perm(char *s, char *new, int k) {
int i, len;
char old;

if ((len = strlen(s)) == k)
printf("%s\n", new);
else
for (i = 0; i < len; i++) {
if (s[i] != '*') {
old = s[i];
s[i] = '*';
new[k] = old;
perm(s, new, k + 1);
s[i] = old;
new[k] = '\0';
}
}
}

// Poziv:

int main() {
char *s, *n;
int i;

s = (char *)malloc(4 * sizeof(char));
strcpy(s, "sad");
n = (char *)malloc((strlen(s) + 1) * sizeof(char));
for (i = 0; i < strlen(s); i++)
n[i] = '\0';
perm(s, n, 0);
free(n);
free(s);
}[/code:1]

Moglo se to i ljepse, ali mi se ovako cinilo najpreglednije. :)
Kod:
int perm(char *s, char *new, int k) {
  int i, len;
  char old;

  if ((len = strlen(s)) == k)
    printf("%s\n", new);
  else
    for (i = 0; i < len; i++) {
      if (s[i] != '*') {
        old = s[i];
        s[i] = '*';
        new[k] = old;
        perm(s, new, k + 1);
        s[i] = old;
        new[k] = '\0';
      }
    }
}

// Poziv:

int main() {
  char *s, *n;
  int i;

  s = (char *)malloc(4 * sizeof(char));
  strcpy(s, "sad");
  n = (char *)malloc((strlen(s) + 1) * sizeof(char));
  for (i = 0; i < strlen(s); i++)
    n[i] = '\0';
  perm(s, n, 0);
  free(n);
  free(s);
}


Moglo se to i ljepse, ali mi se ovako cinilo najpreglednije. Smile



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
ZELENIZUBNAPLANETIDO
SADE

Forumaš(ica)
Forumaš(ica)


Pridružen/a: 04. 03. 2004. (19:56:15)
Postovi: (54F)16
Sarma = la pohva - posuda
= 12 - 5
Lokacija: hm?

PostPostano: 22:23 ned, 19. 9. 2004    Naslov: Citirajte i odgovorite

A bez rekurzije? ;)
A bez rekurzije? Wink



_________________

Pupoljak nije negiran. Rekao sam to i ponovit cu to jos jedanput. Pupoljak NIJE negirAn.
MADD
(Mothers Against Dirty Dialectics)
Based on a true story. NOT.
Ko ih sljivi, mi sviramo punk Wink
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 0:01 pon, 20. 9. 2004    Naslov: Citirajte i odgovorite

lahko, za neki relativno malen broj permutacija zadanog niza (koji npr. stane u integer ili long long...).
numeriras ih sve, ides od 0 do br_perm-1 i divas/modas znak po znak.
lahko, za neki relativno malen broj permutacija zadanog niza (koji npr. stane u integer ili long long...).
numeriras ih sve, ides od 0 do br_perm-1 i divas/modas znak po znak.



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Ce
Gost





PostPostano: 17:47 sub, 3. 6. 2006    Naslov: Citirajte i odgovorite

Bi li mi netko mogao objasniti princip kako da ispisem sve permutacije n-clanog skupa /ne niza brojeva od 1 do n!/ (koji je dan u nekakvom polju),pa da ja to probam srocit u kod?
Mislim,to bi trebalo ici nekako ovako: fixiramo jedan element i ispermutiramo sve ostale,koje permutiramo opet tako da fixiramo jedan pa ispermutiramo ostale itd. Tu se vidi da mi treba nekakva for petlja kojom fixiram element i unutar nje rekurzivni poziv i tako,al nejde mi bas kad to treba tocno zapisati. :?
ovaj gornji vsegov kod radi za troclani skup,kod cetveroclanog vec ispisuje nekakav cudan znak na kraju svake permutacije,a kod npr.sesteroclanog skupa ispisuje samo permutacije koje pocinju sa zadnja tri elementa skupa.
Eto. Hvala na bilo kakvoj pomoci. :)
Bi li mi netko mogao objasniti princip kako da ispisem sve permutacije n-clanog skupa /ne niza brojeva od 1 do n!/ (koji je dan u nekakvom polju),pa da ja to probam srocit u kod?
Mislim,to bi trebalo ici nekako ovako: fixiramo jedan element i ispermutiramo sve ostale,koje permutiramo opet tako da fixiramo jedan pa ispermutiramo ostale itd. Tu se vidi da mi treba nekakva for petlja kojom fixiram element i unutar nje rekurzivni poziv i tako,al nejde mi bas kad to treba tocno zapisati. Confused
ovaj gornji vsegov kod radi za troclani skup,kod cetveroclanog vec ispisuje nekakav cudan znak na kraju svake permutacije,a kod npr.sesteroclanog skupa ispisuje samo permutacije koje pocinju sa zadnja tri elementa skupa.
Eto. Hvala na bilo kakvoj pomoci. Smile


[Vrh]
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 19:28 sub, 3. 6. 2006    Naslov: Citirajte i odgovorite

[quote="Ce"]Bi li mi netko mogao objasniti princip kako da ispisem sve permutacije n-clanog skupa /ne niza brojeva od 1 do n!/ (koji je dan u nekakvom polju),pa da ja to probam srocit u kod?[/quote]

Svejedno je permutiras li niz brojeva od 1 do n ili n-clani skup. 8)

[quote="Ce"]ovaj gornji vsegov kod radi za troclani skup,kod cetveroclanog vec ispisuje nekakav cudan znak na kraju svake permutacije,a kod npr.sesteroclanog skupa ispisuje samo permutacije koje pocinju sa zadnja tri elementa skupa.[/quote]

vsegin kod alocira memoriju za 4 [tt]char[/tt]-a, sto odgovara stringu do 3 slova. 8) Kod se lako modificira za vise. ;)
Ce (napisa):
Bi li mi netko mogao objasniti princip kako da ispisem sve permutacije n-clanog skupa /ne niza brojeva od 1 do n!/ (koji je dan u nekakvom polju),pa da ja to probam srocit u kod?


Svejedno je permutiras li niz brojeva od 1 do n ili n-clani skup. Cool

Ce (napisa):
ovaj gornji vsegov kod radi za troclani skup,kod cetveroclanog vec ispisuje nekakav cudan znak na kraju svake permutacije,a kod npr.sesteroclanog skupa ispisuje samo permutacije koje pocinju sa zadnja tri elementa skupa.


vsegin kod alocira memoriju za 4 char-a, sto odgovara stringu do 3 slova. Cool Kod se lako modificira za vise. Wink



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
maitjas
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 23. 06. 2006. (17:51:54)
Postovi: (A)16
Spol: muško
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 0:23 ned, 25. 6. 2006    Naslov: Citirajte i odgovorite

[quote="Ce"]Bi li mi netko mogao objasniti princip kako da ispisem sve permutacije n-clanog skupa, pa da ja to probam srocit u kod?[/quote]
Evo srocen tebi kod, pa ti princip skuziti probaj.
[code:1]int *p=NULL;
int n;
void printaj(int *p) {
int i;
printf("\n");
for(i=0;i<n;i++)
printf("%d",p[i]);
}
void rotirka(int m) {
int i,t;
t=p[m];
for(i=m;i<n-1;i++)
p[i]=p[i+1];
p[n-1]=t;
}
void perm(int poc) {
int i;
if(n-poc<2)
return;
for(i=poc;i<n-1;i++) {
perm(poc+1);
rotirka(poc);
printaj(p);
}
perm(poc+1);
rotirka(poc);
}
int main() {
int j;
printf("n=");
scanf("%d",&n);
p=(int*)malloc(n*sizeof(int));
for(j=0;j<n;j++)
p[j]=j+1; //printaj(p);
perm(0);
free(p);
}[/code:1]
Zadatak sam manje vise (vise) prepisao iz Vulinove zbirke. Sto se tice (ovog) principa... :roll:
Ce (napisa):
Bi li mi netko mogao objasniti princip kako da ispisem sve permutacije n-clanog skupa, pa da ja to probam srocit u kod?

Evo srocen tebi kod, pa ti princip skuziti probaj.
Kod:
int *p=NULL;
int n;
void printaj(int *p) {
     int i;
     printf("\n");
     for(i=0;i<n;i++)
          printf("%d",p[i]);
}
void rotirka(int m) {
     int i,t;
     t=p[m];
     for(i=m;i<n-1;i++)
          p[i]=p[i+1];
     p[n-1]=t;
}
void perm(int poc) {
     int i;
     if(n-poc<2)
          return;
     for(i=poc;i<n-1;i++) {
          perm(poc+1);
          rotirka(poc);
          printaj(p);         
     }
     perm(poc+1);
     rotirka(poc);
}
int main() {
     int j;
     printf("n=");
     scanf("%d",&n);
     p=(int*)malloc(n*sizeof(int));
     for(j=0;j<n;j++)
          p[j]=j+1;  //printaj(p);
     perm(0);
     free(p);
}

Zadatak sam manje vise (vise) prepisao iz Vulinove zbirke. Sto se tice (ovog) principa... Rolling Eyes


[Vrh]
Korisnički profil Pošaljite privatnu poruku
mdoko
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 30. 11. 2002. (22:17:12)
Postovi: (71A)16
Spol: muško
Sarma = la pohva - posuda
199 = 237 - 38
Lokacija: Heriot-Watt University, Edinburgh

PostPostano: 1:21 ned, 25. 6. 2006    Naslov: Citirajte i odgovorite

[quote="maitjas"]
ti princip skuziti probaj.
[/quote]
Jedan od algoritama za ispis permutacija opisan je u [i]D. Veljan: Kombinatorna i diskretna matematika, str. 55 i 56.[/i]
Taj algoritam ispisuje permutacije u leksikografskom poretku.
maitjas (napisa):

ti princip skuziti probaj.

Jedan od algoritama za ispis permutacija opisan je u D. Veljan: Kombinatorna i diskretna matematika, str. 55 i 56.
Taj algoritam ispisuje permutacije u leksikografskom poretku.



_________________
Extraordinary claims require extraordinary evidence. – Carl Sagan
[Vrh]
Korisnički profil Pošaljite privatnu poruku Posjetite Web stranice
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2 Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan