Kombinationen von Spielsteinen
-
Hallo,
ich hatte die Frage schon in einem anderen Forum gestellt, bekam aber nur unzulängliche Antworten. Ich hoffe jetzt hier etwas mehr Auskunft oder sogar ein Programmbeispiel zu bekommen.
Das Problem ist, daß Spielsteine in allen möglichen Reihenfolgen hintereinander angeordnet werden sollen. Es gibt rote, schwarze und weisse Steine. Die Steine gleicher Farbe sind nicht voneinander zu unterscheiden. Kein ausgegebenes Muster darf doppelt vorkommen und für jedes Muster müssen alle Steine verwendet werden. Die Anzahl der Steine muss frei vorgegeben werden können.
Meine erste Idee war, erst alle möglichen Anordnungen zu erzeugen, die zu sortieren und dann doppelte Muster zu löschen. Leider funktioniert das nicht richtig, sobald die Anzahl der Steine grösser wird.
Irgendjemand behauptete, daß man das direkt lösen könnte, wußte aber nicht wie. Habt ihr vielleicht eine Idee, wie man das besser lösen kann?Jetzt schon danke für eure Antworten
Janine
-
Welche Lösungen/Sources hast Du denn bereits ??
-
Hallo Janine,
ich dachte doch gleich, dass mir das bekannt vorkommt. Immerhin hast Du die Aufgabenstellung praezisiert.
Derjenige, der behauptet hat, dass es auch direkt ginge, der weiss auch wie's geht! Nur hat derjenige keine Lust Dir das Denken abzunehmen. Es handelt sich exakt um das gleiche Problem, wie bei der Frage wo 4 weisse und 4 schwarze Kugeln auf 8 Felder verteilt werden mussten - nur halt einen kleinen Schritt kniffliger.
Ich hab Dir's schonmal gesagt. Es ist nix anderes als eine spezielle Art zu zaehlen! Versteh einfach die Kugeln unterschiedlicher Farbe als Stellen unterschiedlicher Wertigkeit. Das Muster gleichfarbiger Kugeln bestimmt die Ziffernwertigkeit. Sagen wir einfach mal, dass die Rangfolge rot, schwarz, weiss gelte. Dann belegst Du zunaechst die Plaetze mit roten Kugeln, dann die noch freien mit den schwarzen und fuellst dann die noch freien mit den weissen auf. Nun suchst Du die naechste Belegung fuer die schwarzen Kugeln (die weissen dienen ja nur als Fueller), wenn es keine Moeglichkeit mehr gibt (ohne eine rote verdraengen zu muessen), dann schiebst Du alle schwarzen an den Anfang zurueck und suchst die naechste Belegung fuer die roten Kugeln. Dabei gilt dass schwarze Kugeln von den roten an den Anfang verdraengt werden durfen. Na ja, das Schema musste Dir halt ueberlegen. Du solltest aber draufkommen, wenn Du Dir die Anordnung des Beispiels anschaust, das nur mit schwarzen (0) und weissen (1) Kugeln arbeitet.
Der Thread im spotlight sollte uebrigens nicht beleidigend sein, aber die ewige Fragerei nach ner Komplettloesung hat genervt! Man hat schliesslich noch was anderes zu tun, als Hausaufgaben zu loesen. (Tipp am Rande, Du kannst auch das Zaehlschema direkt auf dem Muster realisieren).
Die Idee mit der Gruppenbildung war uebrigens deswegen so Sch..., weil Du wahnsinnig viele Doppel hast, dadurch jede Menge Speicher verbraetst und das Ganze wahnsinnig langsam wird.#include <stdio.h> #include <stdlib.h> #define NDIGITS 4 #define NPOSITIONS 8 int main(void) { unsigned char *p, d[NDIGITS+1]; // Pointer und Feld fuer 'Ziffern' char buf[NPOSITIONS+1]; // Puffer fuer Ausgabemuster unsigned char i; unsigned char c=0; // Nur ein Spaltenzaehler fuer Zeilenumbrueche // Anfangsbelegung erzeugen memset(d, 0, sizeof(d)); d[NDIGITS]=NPOSITIONS-NDIGITS; do { // Nur ein kleiner Trick um die Anzeige hinzukriegen memset(buf, '0', NPOSITIONS); // Ausgabemuster initialisieren buf[NPOSITIONS] = '\0'; // Muster terminieren for(i=NDIGITS; i--; buf[d[i]+i]='1'); // Die Einsen ins Muster reinbasteln fputs(buf, stdout); // Muster ausgeben fputc( (c=(c+1)%7)?' ':'\n', stdout); // Zeilenumbrueche bzw. Blanks ausgeben // Die eigentliche Weiterzaehlerei for(i=NDIGITS, p=d; i && ++*p>*(p+1); i--, *p++=0); } while(i); // i wird zu Null, falls ein Ueberlauf auftritt if(c) putchar('\n'); // ggf. Zeilenumbruch einfuegen return 0; }
-
Hallo Mady,
ich habe mein Programm soweit verbessert, daß es auch mit längeren Zeichenketten funktioniert. Aber das Programm wird sehr langsam, sobald die Zeichenketten länger werden. Der Vorschlag von y@cc bringt mir nichts, weil er nur mit zwei Zeichen richtig arbeitet. Ich würde mich wirklich freuen, wenn du mir Verbesserungsvorschläge hättest.
Jetzt schon danke
Janine
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h> // Prototypen int Fakultaet(int Zahl); void Permutation(int Erstes); int Vergleiche(void * String1, void * String2); void Sortiere(void); void Ausgabe(void); char Muster[]="rrrrsssww"; // eine beliebige Zeichenfolge int Anzahl=0; // Anzahl der möglichen Anordnungen char **Array=NULL; // Array mit den Mustern int LfdNr=0; // momentan einzutragendes Muster int Eindeutige=0; // Anzahl der eindeutigen Muster void main(void) { int i; // Die Anzahl ist die Fakultät der Zeichenzahl Anzahl=Fakultaet(strlen(Muster)); printf("Es gibt %d Möglichkeiten\n", Anzahl); // Speicher für das Array anfordern Array=malloc(Anzahl*sizeof(char *)); if(Array==NULL) { printf("Es konnte kein Speicher angelegt werden\n"); exit(0); } printf("Ich berechne nun die möglichen Anordnungen\n"); Permutation(0); printf("Ich sortiere nun die Muster\n"); Sortiere(); Ausgabe(); // Speicher für Array wieder freigeben free(Array); printf("Es gibt %d eindeutige Lösungen\n", Eindeutige); } int Fakultaet(int Zahl) { int Ergebnis; if(Zahl==0) { Ergebnis=1; } else { Ergebnis=Zahl*Fakultaet(Zahl-1); } return Ergebnis; } void Permutation(int Erstes) { int Ersatz; char temp; if (Erstes==strlen(Muster)) { Array[LfdNr]=malloc(strlen(Muster)+1); strcpy(Array[LfdNr], Muster); LfdNr=LfdNr+1; } else { for (Ersatz=Erstes; Ersatz<strlen(Muster); Ersatz=Ersatz+1) { temp=Muster[Erstes]; Muster[Erstes]=Muster[Ersatz]; Muster[Ersatz]=temp; Permutation(Erstes+1); temp=Muster[Erstes]; Muster[Erstes]=Muster[Ersatz]; Muster[Ersatz]=temp; } } } int Vergleiche(void * String1, void * String2) { int Ergebnis; // Komisch, aber nur so funktioniert es Ergebnis=strcmp(*(char **) String1, *(char **) String2); return Ergebnis; } void Sortiere(void) { // Das muß noch verbessert werden qsort(Array, LfdNr, sizeof(char *), Vergleiche); } void Ausgabe(void) { int i; int MusterNr; MusterNr=0; printf("%s\n", Array[0]); // Sonderfall Eindeutige=1; for (i=0; i<Anzahl; i=i+1) { if(strcmp(Array[MusterNr], Array[i])!=0) { printf("%s\n", Array[i]); MusterNr=i; Eindeutige=Eindeutige+1; } } }
-
Es ist vollbracht. Ich habe ein Programm, das alle Kombinationen direkt berechnet und ich habe es sogar geschafft es deutlich unverständlicher zu machen als y@cc's Lösung.
#include <stdio.h> #include <stdlib.h> int *m,*n; char *l; int rot,schwarz,weiss,nges; int printKomb() { int x,i,j; for(x=0; x<nges; x++) l[x]='W'; for(x=0; x<rot; x++) l[m[x]]='R'; for(x=0, i=0, j=0; x<nges; x++) { if(j<schwarz) if(n[j]==i && l[x]=='W') { l[x]='S'; j++; i++; } if(l[x]=='W') i++; } printf(l); printf(" "); return 0; } int main(int argc, char *argv[]) { int i,j,k,x,i2,j2,k2,ende,ende2,z,komb; rot=2; schwarz=3; weiss=4; komb=0; printf("\nWieviele Weisse?"); scanf("%d",&weiss); printf("\nWieviele Rote?"); scanf("%d",&rot); printf("\nWieviele Schwarze?"); scanf("%d",&schwarz); printf("\n"); nges=rot+schwarz+weiss; l=calloc(nges+1, sizeof(char)); l[nges]='\0'; m=calloc(rot, sizeof(int)); for(x=0; x<rot; x++) m[x]=x; n=calloc(schwarz, sizeof(int)); z=0; i=rot-1; j=i; ende=0; do{ if(j==i) { for(x=0; x<schwarz; x++) n[x]=x; i2=schwarz-1; ende2=0; j2=i2; do { if(j2==i2) { printKomb(); komb++; if(!(++z%5)) { printf("\n"); z=0; } } k2=0; if(j2==i2) { if( n[j2] < ((schwarz+weiss)-1) ) { n[j2]++; k2=1; } } else if ( n[j2] < ((schwarz+weiss)-1-(i2-j2)) ) { n[j2]++; for(x=j2+1; x<=i2; x++) n[x]=n[x-1]+1; k2=1; j2=i2; } if(k2==0) { if(j2==0) ende2=1; else j2--; } } while(!ende2); } k=0; if(j==i) { if( m[j] < (nges-1) ) { m[j]++; k=1; } } else if ( m[j] < (nges-1-(i-j)) ) { m[j]++; for(x=j+1; x<=i; x++) m[x]=m[x-1]+1; k=1; j=i; } if(k==0) { if(j==0) ende=1; else j--; } } while(!ende); printf("\nEs gibt %d Kombinationen.",komb); return 0; }[ Dieser Beitrag wurde am 28.10.2002 um 00:38 Uhr von DrZoidberg editiert. ]
-
Ergänzung: Mein Programm sollte lieber rekursiv geschrieben werden. Ist dann deutlich kürzer und übersichtlicher. Hab jetzt aber keine Lust mehr das umzuschreiben.
-
Hallo und vielen dank,
es funktioniert einwandfrei! Leider verstehe ich nicht so recht, wie es funktioniert, aber das bekomme ich sicher noch heraus. Jetzt habe ich wenigstens eine funktionierende Lösung, die ich analysieren kann.
Nochmals vielen dank
Janine