|
JLI Spieleprogrammierung
|
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
abc_d JLI Master Trainee
Alter: 34 Anmeldedatum: 27.01.2003 Beiträge: 615
Medaillen: Keine
|
Verfasst am: 30.06.2007, 23:16 Titel: Algorithmus |
|
|
Hallo,
ich habe ein Problem damit einen Algorithmus zu finden:
Ich habe 7 Karten, und muss jede mit jeder zu 5 Karten kombinieren, so wie beim Poker.
Am besten kann man es wahrscheinlich mit einem Alphabet erklären:
Man hat 7 Buchstaben zur Verfügung (int Chars[7] = {0,1,2,3,4,5,6}).
Jetzt sollen die Buchstaben zu einem 5-Buchstaben Wort kombiniert werden, eine Buchstabenkombination darf allerdings nicht zwei mal vorkommen (0123456 == 0123465).
Ein Beispiel mit 4 Buchstaben auf 2-Buchstaben Wörter:
Chars[4] = {0, 1, 2,3}
012
013
123
230
Mein Problem ist es, das ich keinen Algorithmus finde, der mir pro Kombination ein Array mit 5 aus den 7 Elementen füllt. Notfalls kann ich per Permutation alle Arrays als Liste in eine Liste werfen, die Arrays dann sortieren und anschließend doppelte entfernen, ich hätte aber lieber einen eleganteren Algorithmus. _________________ http://mitglied.lycos.de/sarti/linuxisevil.gif Linux is evil - get the fact.
Never touch a running System - der Systemling |
|
Nach oben |
|
|
valentin_ Mini JLI'ler
Alter: 34 Anmeldedatum: 16.07.2006 Beiträge: 28 Wohnort: Graz Medaillen: Keine
|
Verfasst am: 01.07.2007, 08:46 Titel: |
|
|
so funktionierts, weiß aber nicht ob dir der Algorithmus shön genug ist...
CPP: | #include <stdio.h>
#include <time.h>
#include <stdlib.h>
void main(void)
{
srand((unsigned)time(NULL));
int Chars[7] = {0,1,2,3,4,5,6};
int Combination[5];
bool b_Doppelt = false;
for(int i=0;i<5;i++)
{
do
{
b_Doppelt = false;
Combination[i] = Chars[rand()%7];
for(int j=0;j<i;j++)
{
if(Combination[i] == Combination[j])
{
b_Doppelt = true;
break;
}
}
}while(b_Doppelt == true);
}
for(i=0;i<5;i++)
{
printf(" Zahl %d: %d\n",i+1,Combination[i]);
}
getchar();
}
|
valentin_ |
|
Nach oben |
|
|
abc_d JLI Master Trainee
Alter: 34 Anmeldedatum: 27.01.2003 Beiträge: 615
Medaillen: Keine
|
Verfasst am: 01.07.2007, 11:38 Titel: |
|
|
Danke für die Arbeit, aber ich brauche nicht nur eine Kombination sondern alle die möglich sind. _________________ http://mitglied.lycos.de/sarti/linuxisevil.gif Linux is evil - get the fact.
Never touch a running System - der Systemling |
|
Nach oben |
|
|
GreveN JLI Master
Alter: 38 Anmeldedatum: 08.01.2004 Beiträge: 901 Wohnort: Sachsen - Dresden Medaillen: Keine
|
Verfasst am: 01.07.2007, 12:12 Titel: |
|
|
Im Prinzip ist es recht easy, du konstruierst dir einen 5-stufigen Baum, wo jeder Knoten 7 Zweige hat, an den Knoten bzw. Blättern stehen jeweils die "Karten". Diesen Baum grast du dann rekursiv ab und hängst die Knoteneinträge an eine Liste an, da du so aber auch doppelte Einträge bekommst, musst du einen Test einbauen, ob der jeweilige Eintrag schon existiert. Dazu könntest du natürlich die Liste durchsuchen, du kannst dir aber auch einfach ein Bool-Array oder dergleichen halten und musst den Karten eben Indizes zu ordnen, es geht aber auch anders.
Im Prinzip ist ein Baum auch nix anderes als ein Graph, insofern könntest du auch einfach einen zyklischen Graph konstruieren mit den 7 Karten als Knoten, indem jeder Knoten von jedem anderem aus erreichbar ist, dafür brauchst du natürlich eine geeignete Datenstruktur. Dann gehst du einfach immer 5 Schritte in diesem Graphen und musst nur wieder immer schauen ob der nächste Schritt noch zulässig ist, sprich ob der nächste Knoten noch nicht besucht wurde.
Aber ich hoffe dir ist bewusst, dass das immerhin 2520 Kombinationen sind. |
|
Nach oben |
|
|
abc_d JLI Master Trainee
Alter: 34 Anmeldedatum: 27.01.2003 Beiträge: 615
Medaillen: Keine
|
Verfasst am: 01.07.2007, 16:36 Titel: |
|
|
Ich glaube ich mache das am besten mit der stl Methode für Permutationen:
Code: |
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
int main(void)
{
std::vector<std::vector<int> > CardArray;
int *FiveCardList = new int[5];
int f[] = { 0, 1, 2, 3, 4, 5, 6 }, *const fn = f + sizeof(f) / sizeof(*f);
do
{
std::vector<int> Combination;
for(int a = 0; a < 5; a++)
Combination.push_back(f[a]);
CardArray.push_back(Combination);
}
while(std::next_permutation(f, fn));
CardArray.erase(std::unique(CardArray.begin(), CardArray.end()), CardArray.end());
std::cout << CardArray.size() << std::endl;
return 0;
}
|
Edit:
Ok, das Zeugt killt meine ganze Arbeit für die Optimierung. _________________ http://mitglied.lycos.de/sarti/linuxisevil.gif Linux is evil - get the fact.
Never touch a running System - der Systemling |
|
Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
Powered by phpBB © 2001, 2005 phpBB Group Deutsche Übersetzung von phpBB.de
|