JLI Spieleprogrammierung Foren-Übersicht JLI Spieleprogrammierung

 
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen 
 medals.php?sid=8e54312aecc5e6413b20e02331bab629Medaillen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

Algorithmus

 
Neues Thema eröffnen   Neue Antwort erstellen    JLI Spieleprogrammierung Foren-Übersicht -> Entwicklung
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

BeitragVerfasst am: 30.06.2007, 23:16    Titel: Algorithmus Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden  
valentin_
Mini JLI'ler


Alter: 34
Anmeldedatum: 16.07.2006
Beiträge: 28
Wohnort: Graz
Medaillen: Keine

BeitragVerfasst am: 01.07.2007, 08:46    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen  
abc_d
JLI Master Trainee


Alter: 34
Anmeldedatum: 27.01.2003
Beiträge: 615

Medaillen: Keine

BeitragVerfasst am: 01.07.2007, 11:38    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden  
GreveN
JLI Master


Alter: 38
Anmeldedatum: 08.01.2004
Beiträge: 901
Wohnort: Sachsen - Dresden
Medaillen: Keine

BeitragVerfasst am: 01.07.2007, 12:12    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden Yahoo Messenger MSN Messenger 
ICQ-Nummer
abc_d
JLI Master Trainee


Alter: 34
Anmeldedatum: 27.01.2003
Beiträge: 615

Medaillen: Keine

BeitragVerfasst am: 01.07.2007, 16:36    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden  
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    JLI Spieleprogrammierung Foren-Übersicht -> Entwicklung Alle Zeiten sind GMT
Seite 1 von 1

 
Gehe zu:  
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

Impressum