Permutacie – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Permutacie – C / C++ – Fórum – Programujte.comPermutacie – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Peter D.0
Expert
4. 4. 2006   #1
-
0
-

Rad by som vypisal permutacie prvkov.
no ako som tak rozmyslal, nie je to jednoduche :)
napr (1,2,3):
123
132
213
231
321
312
-----------------
ale co tak (1,2,3,4,5,6,7,8,9)
nema niekto napad ako to tam zautomatizovat ?

Nahlásit jako SPAM
IP: ...–
Program nemusi fungovat rychle, staci ze funguje dostatecne rychle.
Reklama
Reklama
Adam Streck0
Stálý člen
4. 4. 2006   #2
-
0
-

Jasn? ?e m? - koukej, m?? funkci, kter? p?ejme jako argument index prvku (bude to nejv?t?? z ??sel, neboli po?et cifer), pole prvk? v int (samot?ejm? ukazatelem, bude nastaveno na 0) a velikost nejvy???ho prvku (na za??tku stejn? ??slo jako po?et cifer).
Tahle fukce (v cyklu, je? je pom?n?n t?m, aby velikost prvku byla v?c ne? 0 a velikost counteru je? to bude po??tat byl men?? nebo roven velikosti nejvy???ho prvku):
1) zv?t?? prvek podle indexu o jedna,
2) vytiskne ??slo z pole (samoz?ejm? kv?li indexov?n? je t?eba tisknout pozp?tku)
3) a zavol? sama sebe s indexem o jedna men??m.
4) zvedne counter o 1

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
4. 4. 2006   #3
-
0
-

Vlastně to co jsi uvedl je jednou ze základních ukázek rekurze.

Nahlásit jako SPAM
IP: ...–
Peter D.0
Expert
4. 4. 2006   #4
-
0
-

Nejako som sa v tom stratil. Mozes uviest tu funkciu ? :)

Nahlásit jako SPAM
IP: ...–
Program nemusi fungovat rychle, staci ze funguje dostatecne rychle.
Adam Streck0
Stálý člen
4. 4. 2006   #5
-
0
-

No nerad bych, jelikož nemám po ruce kompilátor, takže bych v tom klidně moh napsat chybu a nemuselo by to fungovat, ale....
Ale zkusim to:
void permutace(int * PointArr, int cifry, int prvek) {
int counter = cifry;
while (counter <= cifry) {
PointArr[prvek]++;
cout << PointArr; //Bude to teda tisknout pozpátku, pak
//se to dá upravit.
if (prvek >= 0)
permutace(PointArr, cifry, --prvek);
counter++
}
prvek++;
}

Nahlásit jako SPAM
IP: ...–
Peter D.0
Expert
4. 4. 2006   #6
-
0
-

tak toto mi hlava neberie :-(
ako fakt nechapem postup
----
to PointArr v priklade reprezentuje to 1,2,3
cifry to je pocet prvkov, teda 3
prvok to by mal byt podla nasledneho dekrementu posledny prvok 3
----
oprav ma, ked som nieco zle pochopil.
---
je tu niekto iny co to chape ? :D

Nahlásit jako SPAM
IP: ...–
Program nemusi fungovat rychle, staci ze funguje dostatecne rychle.
Jura_0
Stálý člen
4. 4. 2006   #7
-
0
-

Ja jen dodam, ze staci pouzit i funkci vytvorenou pro tento ucel a tou je next_permutation z STL. Ale na druhou stranu nen nad to zjistit, jak to vlastne funguje. Je to priklad vytahnuty z msdn.



//////////////////////////////////////////////////////////////////////[color=black]
[/color]//[color=black]
[/color]// Compile options needed: /GX[color=black]
[/color]//[color=black]
[/color]// next_permutation.cpp : Illustrates how to use the[color=black]
[/color]// next_permutation function.[color=black]
[/color]//[color=black]
[/color]// Functions:[color=black]
[/color]//[color=black]
[/color]// next_permutation : Change the order of the sequence to the[color=black]
[/color]// next lexicograhic permutation.[color=black]
[/color]//////////////////////////////////////////////////////////////////////[color=black]
[/color][color=black]
[/color]// disable warning C4786: symbol greater than 255 character,[color=black]
[/color]// okay to ignore[color=black]
[/color][color=black]
[/color][color=black]
[/color][color=blue]#include[/color] [color=black]<[/color][color=black]iostream[/color][color=black]>[/color][color=black]
[/color][color=blue]#include[/color] [color=black]<[/color][color=black]vector[/color][color=black]>[/color][color=black]
[/color][color=blue]#include[/color] [color=black]<[/color][color=black]string[/color][color=black]>[/color][color=black]
[/color][color=blue]#include[/color] [color=black]<[/color][color=black]algorithm[/color][color=black]>[/color][color=black]
[/color][color=blue]#include[/color] [color=black]<[/color][color=black]iterator[/color][color=black]>[/color][color=black]
[/color][color=black]
[/color][color=blue]using[/color] [color=blue]namespace[/color] [color=black]std[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color][color=blue]int[/color] [color=black]main[/color][color=black]([/color][color=black])[/color][color=black]
[/color][color=black]{[/color][color=black]
[/color] [color=blue]const[/color] [color=blue]int[/color] [color=black]VECTOR[/color][color=black]_[/color][color=black]SIZE[/color] [color=black]=[/color] [color=red]3[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] // Define a template class vector of strings[color=black]
[/color] [color=blue]typedef[/color] [color=black]vector[/color][color=black]<[/color][color=black]string[/color][color=black]>[/color] [color=black]StrVector[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] //Define an iterator for template class vector of strings[color=black]
[/color] [color=blue]typedef[/color] [color=black]StrVector[/color][color=black]:[/color][color=black]:[/color][color=black]iterator[/color] [color=black]StrVectorIt[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] //Define an ostream iterator for strings[color=black]
[/color] [color=blue]typedef[/color] [color=black]ostream[/color][color=black]_[/color][color=black]iterator[/color][color=black]<[/color][color=black]string[/color][color=black]>[/color] [color=black]StrOstreamIt[/color][color=black];[/color][color=black]
[/color][color=black]
[/color] [color=black]StrVector[/color] [color=black]Pattern[/color][color=black]([/color][color=black]VECTOR[/color][color=black]_[/color][color=black]SIZE[/color][color=black])[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] [color=black]StrVectorIt[/color] [color=black]start[/color][color=black],[/color] [color=black]end[/color][color=black],[/color] [color=black]it[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] [color=black]StrOstreamIt[/color] [color=black]outIt[/color][color=black]([/color][color=black]cout[/color][color=black],[/color] [color=green]" "[/color][color=black])[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] [color=black]start[/color] [color=black]=[/color] [color=black]Pattern[/color][color=black].[/color][color=black]begin[/color][color=black]([/color][color=black])[/color] [color=black];[/color] // location of first[color=black]
[/color] // element of Pattern[color=black]
[/color][color=black]
[/color] [color=black]end[/color] [color=black]=[/color] [color=black]Pattern[/color][color=black].[/color][color=black]end[/color][color=black]([/color][color=black])[/color] [color=black];[/color] // one past the location last[color=black]
[/color] // element of Pattern[color=black]
[/color][color=black]
[/color] //Initialize vector Pattern[color=black]
[/color] [color=black]Pattern[/color][color=black][[/color][color=red]0[/color][color=black]][/color] [color=black]=[/color] [color=green]"A"[/color] [color=black];[/color][color=black]
[/color] [color=black]Pattern[/color][color=black][[/color][color=red]1[/color][color=black]][/color] [color=black]=[/color] [color=green]"B"[/color] [color=black];[/color][color=black]
[/color] [color=black]Pattern[/color][color=black][[/color][color=red]2[/color][color=black]][/color] [color=black]=[/color] [color=green]"C"[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] // print content of Pattern[color=black]
[/color] [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=green]"Before calling next_permutation...\n"[/color] [color=black]<[/color][color=black]<[/color] [color=green]"Pattern: "[/color] [color=black];[/color][color=black]
[/color] [color=blue]for[/color][color=black]([/color][color=black]it[/color] [color=black]=[/color] [color=black]start[/color][color=black];[/color] [color=black]it[/color] [color=black]![/color][color=black]=[/color] [color=black]end[/color][color=black];[/color] [color=black]it[/color][color=black]+[/color][color=black]+[/color][color=black])[/color][color=black]
[/color] [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=black]*[/color][color=black]it[/color] [color=black]<[/color][color=black]<[/color] [color=green]" "[/color] [color=black];[/color][color=black]
[/color] [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=green]"\n\n"[/color] [color=black];[/color][color=black]
[/color][color=black]
[/color] // Generate all possible permutations[color=black]
[/color][color=black]
[/color] [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=green]"After calling next_permutation...."[/color] [color=black]<[/color][color=black]<[/color] [color=black]endl[/color] [color=black];[/color][color=black]
[/color] [color=blue]while[/color] [color=black]([/color] [color=black]next[/color][color=black]_[/color][color=black]permutation[/color][color=black]([/color][color=black]start[/color][color=black],[/color] [color=black]end[/color][color=black])[/color] [color=black])[/color][color=black]
[/color] [color=black]{[/color][color=black]
[/color] [color=black]copy[/color][color=black]([/color][color=black]start[/color][color=black],[/color] [color=black]end[/color][color=black],[/color] [color=black]outIt[/color][color=black])[/color] [color=black];[/color][color=black]
[/color] [color=black]cout[/color] [color=black]<[/color][color=black]<[/color] [color=black]endl[/color] [color=black];[/color][color=black]
[/color] [color=black]}[/color][color=black]
[/color] [color=black]cin[/color][color=black].[/color][color=black]get[/color][color=black]([/color][color=black])[/color][color=black];[/color][color=black]
[/color] [color=blue]return[/color] [color=red]0[/color][color=black];[/color][color=black]
[/color][color=black]}[/color][color=black]
[/color][color=black]
[/color]

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
4. 4. 2006   #8
-
0
-

Nech?pe?? Tak principi?ln?, co to d?l? -
vyvol?? t?eba fci pro ?ty?i cifry - tzn. pro ??sla 1-4. Co se stane?
Vytvo?? se pole ?ty? prvk? na hodnot? nula a p?ed? se fci, n?sledn? se s n?m pracuje jen pomoc? ukazatele PointArr (Array, Pointer - ?ili pole, ukazatel). Prob?hne prvn? fce:
Zvedne posledn? prvek (s indexem (prvkem) 3, tam m?m chybku, mus?? dotat index o jedno men?? ne? je po?et cifer samoz?ejm?)
m?? 0001.
Zavol? se druh? fce uvnit? cyklu prvn?, index 2 se zvedne o jedna vznikne 0011.
Zavol? se t?et? fce uvnit? cyklu druh?, index 1 se zvedne o jedna vznikne 0111.
Zavol? se ?tvrt? fce uvnit? cyklu t?et?, index 0 se zvedne o jedna vznikne 1111, podn?mka nepravdiv?, dal?? fce se nezavol?, prob?h? cyklus:
2111
3111
4111
podm?nka nepravdiv?, cyklus kon??, kon?? ?tvrt? fce.
T?et? fce prob?hne cyklus zvedne na 1211 (to by se m?lo st?t, j? tam m?m chybu, tak?e tam bude 4211, proto?e jsem zapom?l na konci fce zm?nit prvek zp?t na 1)
po zvednut? prvku o jedna se zavol? zase ?tvrt? fce a zase
2211
3211............
a? skon?? t?et? funkce, tak druh? ikrementuje a zavol? t?et?, kter? inkrementuje a zavol? ?tvrtou, pak skon?? i druh? a prvn? ji zavol? znovu a ta zavol? t?et? a... a takhle to bude a? do ??sla 4444...

Jinak m?m tam chybky, tak?e by to nefungovalo, cht?l jsem jen vysv?tlit princip, a? budu m?t kompil?tor, mo?n? vytvo??m funk?n? verzi

Nahlásit jako SPAM
IP: ...–
Peter D.0
Expert
4. 4. 2006   #9
-
0
-

ach jo. trochu svetla :)
takze ked to chapem dostanem
1111 2111 3111 4111
1211 2211 3211 4211
1311 2311 3311 4311
1411 2411 3411 4411
1121 ...
----------
tieto polia budem dostavat po volani ?
(teraz neviem ci som to pochopil)
ale ked hej tak toto nie su "permutacie"
ja chcem dostat
1234 2134 ...
1243 2143
1324 2314
1342 2341
1432 2413
1423 2431

Nahlásit jako SPAM
IP: ...–
Program nemusi fungovat rychle, staci ze funguje dostatecne rychle.
Adam Streck0
Stálý člen
4. 4. 2006   #10
-
0
-

Sorry, pochopil jsi správně, já nevěděl přesně, co jsou to permutace :((. Až budu mít trochu času, tak nad tím popřemýšlím.

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
5. 4. 2006   #11
-
0
-

Jinak už ti zase blbne zvýrazňování syntaxe - závorky

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
6. 4. 2006   #12
-
0
-

I'm GOD, workship me!!!

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
6. 4. 2006   #13
-
0
-



#include <iostream>
using namespace std;

void permutace(int * pointer, int size);
void swap(int & a, int & b);
void print(int * pointer, int size);
int faktorial(int cislo, int citac);
int zjisti_a(int counter);
int zjisti_b(int counter);

int main() {
cout << "Zadejte pocet prvku (cifer): n";
int size;
cin >> size;
int array[size]; // Pole pro ulo?en? ??sla
for (int counter = 1; counter <= size; counter++)
array[counter - 1] = counter; // Na?ten? pole po sob? jdouc?mi ??sly
permutace(array, size);
cin.get();
cin.get();
}

void permutace(int * pointer, int size) {
int counter = 1;
int cyklu = faktorial(size, size); // zjist? po?et permutac?
int a; // korekce prvn?ho m?n?n?ho prvku prvku
int b; // korekce druh?ho m?n?n?ho prvku prvku
while (counter <= cyklu) {
a = zjisti_a(counter); // zjist? korekci prvn?ho m?n?n?ho prvku prvku
b = zjisti_b(counter); // zjist? korekci druh?ho m?n?n?ho prvku prvku
print(pointer, size); // v?stup
swap(pointer[size - a], pointer[size - b]); // z?m?na prvk?
counter++;
}
}

void swap(int & a, int & b) { // Zam?n? prvky
int temp;
temp = a;
a = b;
b = temp;
}

void print(int * pointer, int size) {
for (int counter = 0; counter < size; counter++) //Vytiskne v?echny prvky pole
cout << pointer[counter];
cout << endl;
}

int faktorial(int navrat, int cislo) { // Rekurzivn? fce pro v?po?et faktori?lu
cislo--;
if (cislo > 0) // Podm?nka pro rekurzivn? vol?n?
navrat *= faktorial(cislo, cislo); /* Rekurzivn? vol? sama sebe s prvkem o jedna men??m a n?sob? j?m v?sledek (pro v?po?et faktori?lu) */
return navrat; //vrac? hodnotu n?vratu
}

int zjisti_a(int counter) { // Zjist? korekci pro po?ad? prvku a (prvn?ho prvku)
if((counter % faktorial(7, 7)) == 0) //Pro ka?d? 7! prvek
return 8;
if((counter % faktorial(6, 6)) == 0) //Pro ka?d? 720 prvek
return 7;
if((counter % faktorial(5, 5)) == 0) //Pro ka?d? 120 prvek
return 6;
if((counter % faktorial(4, 4)) == 0) //Pro ka?d? 24 prvek
return 5;
if((counter % faktorial(3, 3)) == 0) //Pro ka?d? ?est? prvek
return 4;
if((counter % faktorial(2, 2)) == 0) //Pro ka?d? druh? prvek
return 3;
else // Pro ostatn? prvky
return 2;
}

int zjisti_b(int counter) { // Zjist? korekci pro po?ad? prvku b (druh?ho prvku)
counter %= 24; // Celo??seln? zbytek po d?len? 24
if((counter % 18) == 0) //Pro 18-ct? prvkek ze 24
return 3;
if((counter % 12) == 0) //Pro 12-ct? prvkek ze 24
return 2;
else
return 1; // Pro ostatn? prvky
}

/* Po?ad? zam??ovan?ch prvk? z?vis? na z?konech pro permutace, kter? jsem vypozoroval p?i pokusech s permutacemi */
/* Program po??t? jen pro permutace do 8 ??d?, jeliko? tyto permutace stejn? ani rozum? nevyp??e..., pro v?t?? permutace je pot?eba p?idat p??slu?n? ??dek na za??tek fce zjisti_a, jedn? se o stejn? ??dek jako jsou ostatn?, jen o jeden ??d vy???*/

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
6. 4. 2006   #14
-
0
-

A? bude ?as, dod?m koment??e, te? to fakt nedop??u, jelik? nem?m ?as - Kdo na to p?ijde jak to je, m? u m? bomb?n ;)... Jinak program v?m vyobraz? jen permutace p?ti - permutace ?esti u? maj? 720 ??dk?, tak?e budou u??zl?, program dopo??t? permutace max do permutac? 7, kdo by ale cht?l z n?jak?ho d?vodu v?c p?idejte p?ed ??dek:
if((counter % faktorial(7, 7)) == 0)
return 8;
??dek:
if((counter % faktorial(8, 8)) == 0)
return 9;
a tak d?le.....

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
6. 4. 2006   #15
-
0
-

Jinak to hodim ještě do zdrojáků...

Nahlásit jako SPAM
IP: ...–
Adam Streck0
Stálý člen
6. 4. 2006   #16
-
0
-

Tak jsem přidal i komentáře.

Nahlásit jako SPAM
IP: ...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 129 hostů

Podobná vlákna

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý