010
02.05.2003, 12:28 Uhr
~0xdeadbeef
Gast
|
Du vergisst, den seed für den Zufallszahlengenerator zu setzen. Ansonsten ist der Ansatz aber sehr schön, es auszunutzen, dass die Mengen eine maximale Größe haben.
Ich hab allerdings noch eine Idee, wie man das ganze optimieren könnte:
| C++: |
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
int main(int argc, char* argv[]){
int i,j,anzahl1,anzahl2;
char menge1[26],menge2[26],schnittmenge[26], vereinigungsmenge[26];
srand(time(0)); //seed setzen
printf("Mächtigkeit Menge1(max26): "); scanf("%d",&anzahl1);
printf("Mächtigkeit Menge2(max26): "); scanf("%d",&anzahl2);
for(i=0;i<26;i++){
menge1[ i ]=0;
menge2[ i ]=0;
schnittmenge[ i ]=0;
vereinigungsmenge[ i ]=0;
}
for(i=0;i<anzahl1;i++){
do {
j = rand() % 26;
} while (menge1[j]);
menge1[j] = 'A' + j;
}
for(i=0;i<anzahl2;i++){
do {
j = rand() % 26;
} while(menge2[j]);
menge2[j] = 'A' + j;
}
for(i=0;i<26;i++){ //Hier wird optimiert.
schnittmenge[i] = menge1[i] & menge2[i];
vereinigungsmenge[i] = menge1[i] | menge2[i];
}
printf("\nMenge 1n");
for(i=0;i<26;i++) printf("%c",menge1[ i ]);
printf("\n\nMenge 2n");
for(i=0;i<26;i++) printf("%c",menge2[ i ]);
printf("\n\nSchnittn");
for(i=0;i<26;i++) printf("%c",schnittmenge[ i ]);
printf("\n\nVereinigungn");
for(i=0;i<26;i++) printf("%c",vereinigungsmenge[ i ]);
printf("\n\n");
return 0;
}
|
Der Algorithmus nutzt aus, dass an einer bestimmten Position in menge1 und menge2 nur entweder 0 oder 'A' + index stehen kann. Ein Beispiel: Für x = 2 können folgende Kombinationen von menge1[x] und menge2[x] auftreten:
1. menge1[x] = 0, menge2[x] = 0.
Das führt dazu, dass menge1[x] & menge2[x] = 0 und menge1[x] | menge2[x] = 0
2. menge1[x] = 'C', menge2[x] = 0
Das führt dazu, dass menge1[x] & menge2[x] = 0 ist, weil 0 bitweise mit etwas anderem geundet immer 0 gibt, und menge1[x] | menge2[x] = 'C' ist, weil 0 bitweise geodert mit etwas anderem immer das andere gibt
3. menge1[x] = 0, menge2[x] = 'C'
siehe 2.
4. menge1[x] = menge2[x] = 'C'
Das führt dazu, dass menge1[x] & menge2[x] = 'C' und menge1[x] | menge2[x] = 'C' ist.
Das ist genau das, was wir für Schnitt und Vereinigung der mengen brauchen - und es spart uns ne ganze Reihe Vergleiche. |
