4 verschiedenen (Zufalls-)Zahlen

[loik]

Moin,
ich möchte, dass am Ende 4 verschiedene Zahlen in ein Array geschrieben sind.
Bisher hab ich diesen Code, der allerdings noch nicht wirklich funktionstüchtig ist. Allerdings komme ich nicht mehr weiter:

...
int max=6;
srand(time(0));
int array[4];
for(int i=0; i<4; i=i+1)
{
	int zzahl = rand() % max + 1;	
	array[i]=zzahl;	
	for(int j=0; j<4; j=j+1)
	{
		while(array[i]==array[i-j]&&i!=0) 
		{
				int zzahl = rand() % max + 1;
				array[i]=zzahl;
				break;
		}
	}
}
cout<<array[0]<<array[1]<<array[2]<<array[3];
...

Soweit so gut: Mit der While Schleife will ich eigentlich überprüfen, ob der neue Wert[i] mit irgendeinem schon vergebenen Wert[i-j] übereinstimmt und, falls das der Fall ist, einen neuen Wert zuweisen.

Leider klappt das nicht.
Hoffe mein Problem ist klar geworden und jemand hat eine Lösung oder hilft mir meine Denkblockade zu entfernen

Gruß loik

[loik]

Moin,
bin ein bisschen weitergekommen und hab einige Dumme Fehler selbst gefunden, nur funktionieren tut das ganze immernoch nicht so wie ich es möchte:

...
int max=6;
srand(time(0));
int array[4];
for(int i=0; i<4; i=i+1)
{
	int zzahl = rand() % max + 1;	
	array[i]=zzahl;	
	for(int j=1; j<4; j=j+1)
	{
		if(i!=0)
		{
			while(array[i]==array[i-j])
			{
					int zzahl = rand() % max + 1;
					array[i]=zzahl;
			}
		}
	}
}
cout<<array[0]<<array[1]<<array[2]<<array[3];
...

Das Problem liegt nach wie vor in der While Schleife: Zwar erkennt das Programm nun richtig, dass ein Wert schon da war, aber wenn er den Wert neu setzt, überprüft er dies nicht nocheinmal ...

Hoffe es gibt eine einfache Möglichkeit mir dabei zu helfen.

Gruß loik

[drakon]

Also ich habe rege Mühe zu verstehen, was du mit deinem Code machen willst.
Ich weiss zwar, was du machen willst, aber dein Code ist sehr verwirrend und wird so wahrscheinlich niemals dein gewünschtes Ergebnis beinhalten.

Probier dein Problem ein wenig zu konkretisieren und dir besser zu überlegen, welche Schritte dazu notwendig sind.

Also ich würde vorschlagen, dass du das ganze mal löscht und dir Gedanken macht, was du willst und was da alles für Schritte notwendig sind.

Ich persönlich würde da einen ganz anderen Ansatz wählen für dein Problem.
Ich würde da einfach ein Array mit allen 6 Zahlen füllen, die möglich sind. std::random_shuffle darauf anwenden und dann 4 Zahlen da rauspicken.
Aber du kannst es ruhig auch mal durch deinen Ansatz versuchen. Ist sicher lehrreicher, als der std:: - Ansatz.

btw:
Warum machst du für die Ausgabe nicht auch einfach eine Schleife?

[loik]

Jo, vielen dank!
Nach etwa so einer Funktion habe ich gesucht:)

Falls es von interesse ist:
Meine Überlegungen:
1. ich möchte 4 Zahlen in einen Array packen -> Zufallszahl(1-max)

for(int i=0; i<4; i=i+1)
{
    int zzahl = rand() % max + 1;   
    array[i]=zzahl;

2. Überprüfen ob ein Wert in diesem Array schonmal vorkam

for(int j=1; j<4; j=j+1)
    {
        if(i!=0)
        {
            while(array[i]==array[i-j])
            {

3. und falls ja, eine neue Zufallszahl in den Array speichern

int zzahl = rand() % max + 1;
                    array[i]=zzahl;
            }
        }
    }
}

Ich glaube durchaus, dass es möglich wäre auf diese Weise zu meinem gewünschten Ergebnis zu gelangen,
da mir jetzt aber eine "bessere" Lösung gesagt wurde, benutze ich auch diese.

Gruß loik

[KeksX]

Also ich würde es mit einer einfachen for-Schleife regeln:

for(int i=0;i<4;i++){
  array[i] = rand() % max + 1;
}

So wird in jedes der 4 Elemente eine eigene Zufallszahl geschrieben. Du benötigst lediglich, wie du es ja bereits schon stehen hattest,

int max;

und

srand(time(0));
int array[4];

Und die Ausgabe kannst du ebenfalls mit der for-Schleife lösen:

for(i=0;i<4;i++){
cout<<array[i]<<endl;
}

Also das wäre meine Lösung...

[Tachyon]

KeksX schrieb:

...

Dann hat er aber auch mit einer 4:max Wahrscheinlichkeit Dubletten in seinem Array, und das will er nicht.

[Nexus]

loik schrieb:

Meine Überlegungen:
1. ich möchte 4 Zahlen in einen Array packen -> Zufallszahl(1-max)
2. Überprüfen ob ein Wert in diesem Array schonmal vorkam
3. und falls ja, eine neue Zufallszahl in den Array speichern

Dieser Ansatz ist ziemlich subobtimal, da er eine exponentielle Zeitkomplexität () mit sich bringt.

Du musst bedenken, dass bei jedem neuen Element die vorhergehenden Elemente überprüft werden. Zudem wird die Wahrscheinlichkeit, dass ein Element bereits vorkommt, mit zunehmendem Fortschritt grösser. Das wirkt sich bei grossen Arrays fatal aus.

Deshalb würde ich etwas Ähnliches wie std::random_shuffle() implementieren, sodass das Array zuerst erstellt wird und dann zufällig Elemente vertauscht werden. Dann läuft dein Algorithmus auch in O(n), ist also linear von der Anzahl der Elemente abhängig.

Statt Arrays würde ich dir auch raten, STL-Container zu verwenden.

[drakon]

Nexus schrieb:

Dieser Ansatz ist ziemlich subobtimal, da er eine exponentielle Zeitkomplexität () mit sich bringt.

Ich glaube kaum, dass er weiss, was das jetzt bedeutet, noch relevant für ihn ist.

Zu deinem Code:

Mal ein wenig allgemein:

i = i + 1; // ist das gleiche, wie:
i++; // (post-inkrement) oder:
++i; // (pre-inkrement)

Das einzige, was du da beachten musst ist der Rückgabewert:

int i = 2;
if (i++ == 3)... // Bedingung nicht erfüllt, da i inkrementiert wird und dann das "alte" i zurückgegeben wird
i = 2;
if (++i == 3)...//Bedingung erfüllt, da i inkrementiert wird und auch zurückgegeben wird

Das siehst du vor allem in Schleifenausdrücken.

while(array[i]==array[i-j])

Das ist äusserst gefährlich. OK. i ist sicher grösser 0, aber was ist den jetzt, wenn i 1 ist und j 2? array[-1] ?! Spätestens hier sollte sich dein Programm aufhängen. (ich bin mir nicht sicher, ob du das ev. als "bis" gelesen hast und nicht als "minus"..?! Ist das möglich? )

Man kann das Problem durchaus durch deinen Ansatz lösen, aber das erfordert ein weng mehr Aufmerksamkeit, als meine Variante. - Das sie ineffizienter ist mal davon abgesehen. (wie korrekt von Nexus bemängelt)

Wen ich Zeit finde (und Lust habe), werde ich das nachher mal kurz machen.

EDIT:
Hier, habs nicht ausführlich getestet, sollte aber laufen..

void calc ()
{
	int zahlen[4];
	int max = 6;

	//zuerst mal alles leeren
	for (int i = 0; i < 4 ; ++i)
	{
		zahlen[ i ] = 0;
	}

	//für jede Stelle
	for (int i = 0; i < 4 ; ++i)
	{
		//eine Zahl bekommen
		zahlen [ i ] = rand () % max + 1;

		//mit jeder anderen vergleichen
		for (int y = 0; y < 4;)
		{
			//Wenn y == i, dann wäre es ein vergleich mit sich selbs, also überspringen
			if ( y == i)
			{
				++y;
				continue;
			}

			//Wenn wir eine Gleichheit haben 
			if ( zahlen [ i ] == zahlen [ y ] )
			{
				//Nochmal probieren
				zahlen [ i ] = rand () % max + 1;

				//jetzt könnten wir einen Konflikt mit einer anderen Zahl haben
				//also nochmal von Anfang an
				y = 0;
			}
			else
				++y;
		}
	}
}

[Nexus]

drakon schrieb:

Ich glaube kaum, dass er weiss, was das jetzt bedeutet, noch relevant für ihn ist.

Nun ja, ich wollte ihn einfach darauf hinweisen, da er ja seine Überlegungen präsentiert hat. Bei Wikipedia findet man unter Zeitkomplexität z.B. relativ schnell etwas. Im Übrigen hab ich ja anschliessend noch erläutert, wieso der Algorithmus in O(2^x) wächst.

Sich ein bisschen mit Zeitkomplexität und Laufzeit auszukennen kann sowieso nicht schaden.

Aber gut, dass du dir extra noch Zeit für den Code genommen hast.

[Tachyon]

[quote="Nexus"]

drakon schrieb:

... wieso der Algorithmus in O(2^x) wächst

Mal abgesehen davon, dass die Komplexität auch von der Anzahl der möglichen Zufallssymbole abhängt, und dass die ganze Geschichte ohnehin nicht stabil ist, wie kommst Du auf O(2^x)?

[Nexus]

Tachyon schrieb:

O(2^x)?

Ich denke, das ist die Komplexitätsklasse für exponentielles Wachstum, oder? Man schreibt ja auch O(n), wenn die Anzahl Operationen 35*n + 7 beträgt...

Okay, n wäre vielleicht besser gewesen als x... Ist es das, was du meinst?

[Tachyon]

So wie ich das sehe, ist die Komplexität O(n²). Wenn es blöd läuft, hat man eine Endlosschleife.

[drakon]

Tachyon schrieb:

So wie ich das sehe, ist die Komplexität O(n²). Wenn es blöd läuft, hat man eine Endlosschleife.

Jo, klar, ich wollte ihm ja nur zeigen, wie das mit seinem Ansatz in etwa geht.. Einen besseren Vorschlag habe ich ja schon längst gemacht..;)

@Nexus:
5 Minuten sind nicht soo viel..

[Nexus]

Hm... Tut mir leid, wenn ich was Falsches erzählt habe.

Quadratisch würde Sinn machen, da ja n Mal eine Zufallszahl erzeugt wird und jeweils die vorherigen Elemente überprüft werden. Jedoch ist das nicht alles.

Macht denn die Tatsache, dass gegen Ende der Sequenz die Wahrscheinlichkeit für eine noch nicht vorhandene Zufallszahl immer kleiner wird, nichts aus? Dadurch müssen bei einer bereits vorhandenen Zahl alle Elemente bis dahin noch einmal überprüft werden, was ja einen erheblichen Einfluss auf die Laufzeit hat.

Das war auch meine Überlegung; selbst wenn exponentiell vielleicht nicht stimmt, wächst die Average-Case-Laufzeit mehr als quadratisch. Beim letzten Element hat man beispielsweise nur eine Wahrscheinlichkeit von 1/n, genau die richtige Zahl zu treffen, was sich bei grossen n stark in die Länge ziehen kann.

[Nexus]

Hmm... Gehört zwar vielleicht nicht mehr zur Ursprungsfrage, aber seid ihr ganz sicher, dass die Laufzeit quadratisch ist? Würde mich schon noch interessieren...

[drakon]

Du überprüfst jede Zahl mit jeder anderen. Wie lange das schlussendlich geht ist nicht die Frage. Tachyon hat ja bereits gesagt, dass man durchaus eine "Endlosschleife" hat. Wobei das auch nicht richtig ist. Der Algorithmus kann theoretisch 1000 Jahre laufen, aber ein Ende hat er immer.

[Tachyon]

drakon schrieb:

Du überprüfst jede Zahl mit jeder anderen. Wie lange das schlussendlich geht ist nicht die Frage. Tachyon hat ja bereits gesagt, dass man durchaus eine "Endlosschleife" hat. Wobei das auch nicht richtig ist. Der Algorithmus kann theoretisch 1000 Jahre laufen, aber ein Ende hat er immer.

Woher willst Du das wissen? Wenn Du Pech (bzw. die Menge ausreichend Groß ist) hast, dann hast Du eine sich wiederholende Folge von Zufallszahlen (und irgendwann wird sie sich wiederholen, sofern es sich um die üblichen Pseudozufallszahlen handelt), bei der Du nur Dubletten produzierst. Wenn der Krempel bereits 1000 Jahre durch hat, ist das sogar ziemlich wahrscheinlich.
Das gibt dann eine echte Endlosschleife.
Der Algorithmus für sich genommen hat jedenfalls O(n²). Das sieht man eigentlich ziemlich direkt.

[drakon]

Tachyon schrieb:

...

OK. Das hätte ich vlt. mal noch hinschreiben sollen, dass Vorausgesetzt ist, dass es kein PRNG sein sollte. - Hat ja eigentlich nichts mit dem Algorithmus selbst zu tun.

Ansonsten darf hinter rand ja auch sowas stehen:

int rand ()
{
return 2;
}

[Nexus]

Tachyon schrieb:

Der Algorithmus für sich genommen hat jedenfalls O(n²). Das sieht man eigentlich ziemlich direkt.

Naja, das ist wohl mehr oder weniger Übungssache. Mit Zeitkomplexität und Algorithmen kenne ich mich sowieso nicht wahnsinnig gut aus...

Aber ich dachte, die Komplexitätsklasse gebe an, in welchem Mass die Laufzeit wächst, wenn mehr Elemente dazukommen. Und das ist meiner Ansicht nach in diesem Falle mehr als quadratisch, deshalb kann ich es nicht ganz nachvollziehen...

[Tachyon]

Nexus schrieb:

Tachyon schrieb:

Der Algorithmus für sich genommen hat jedenfalls O(n²). Das sieht man eigentlich ziemlich direkt.

Naja, das ist wohl mehr oder weniger Übungssache. Mit Zeitkomplexität und Algorithmen kenne ich mich sowieso nicht wahnsinnig gut aus...

Aber ich dachte, die Komplexitätsklasse gebe an, in welchem Mass die Laufzeit wächst, wenn mehr Elemente dazukommen. Und das ist meiner Ansicht nach in diesem Falle mehr als quadratisch, deshalb kann ich es nicht ganz nachvollziehen...

Ne, die ist schon quadratisch. Das kannst Du auch leicht selbst ausprobieren, mit dem Algo, den drakon hier gepostet hat. Einfach die Iterationen mitzählen und mal mit der Arraylänge spielen. Sofern da kein Bock drin ist, sollten die Iterationen näherungsweise quadratisch zur Arraylänge wachsen.
Man geht ja für die O-Notation nicht vom Worstcase aus. Sonst hätte Quicksort auch nicht O(n log(n)) sondern ebenfalls O(n²).
Ich muss aber gestehen, dass ich das Thema auch immer ziemlich ätzend fand. Inzwischen gehts aber.