Zufalls Generator

life

das mit den doppelten zufallszahlen verhindern geht auch effektiver.. siehe z.b. hier:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-139206-and-highlight-is-*zufall*.html

snoopy9134

hab jetzt den code n bissi verändert, hab noch das problem, bei 2 gleichen zahlen bekomm ich beide hintereinander aufn bildschirm nur jetzt anstatt von 5
zufalsszahlen 6.
wollte es mit der if bediengung zurechtrücken geht aba net!!!

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int main()
{

	int z[5];

	srand(time(NULL));//einmal bei Programmstart

	for(int i=0;i<5;++i)

	{
			z[i]=rand()%49+1;

			for(int j=0; j<i; j++)

				{
					if(z[i]==z[j])
						{
							i--;
							break;

						}

				}

	if(z[i]!=z[j])
		{

			cout<<'\t'<<z[i];
		}
	}
return 0;
}

ps.life dein vorschlag is n bissi zu kompliziert, hab mich mit den klassen noch net beschäftigt, aba kommt noch

CStoll

Ich hätte da noch eine andere Idee, wie du deine Lotto-Ziehung machen kannst:

set<int> zahlen;
while(zahlen.size()<6)
  zahlen.insert(rand()%49+1);

(das set<> stellt sicher, daß jedes Element nur einmal eingefügt werden kann, d.h. am Ende der Schleife stehen in "zahlen" 6 garantiert unterschiedliche Zufallszahlen drin)

life

CStoll schrieb:

Ich hätte da noch eine andere Idee, wie du deine Lotto-Ziehung machen kannst:
set<int> zahlen;
while(zahlen.size()<6)
  zahlen.insert(rand()%49+1);
(das set<> stellt sicher, daß jedes Element nur einmal eingefügt werden kann, d.h. am Ende der Schleife stehen in "zahlen" 6 garantiert unterschiedliche Zufallszahlen drin)

ist doch (fast) genauso ineffektiv.. wie teuer ist denn insert? log n?

CStoll

Ja, insert() ist O(log n) - der Test in deinem ursprünglichen Programm ist O(n)

life

CStoll schrieb:

Ja, insert() ist O(log n) - der Test in deinem ursprünglichen Programm ist O(n)

in meinem Programm ist er O(1), weil garkein Test stattfindet.. Das finden der n paarweise verschiedenen Zufallzahlen kosten somit nur O(n). Bei dir kostet das Ganze dann O(n logn) und bei der Version vom Threadersteller O(n²) und beides nur sofern keine Zahl doppelt gewürfelt wurde..

CStoll

Um 6 aus 49 zu ermitteln, mache ich mir noch keine großen Gedanken über die Performance (und bei größeren Mengen würde ich wohl random_shuffle() verwenden). Und bedenkst du auch, daß deine Variante deutlich mehr Speicherplatz (und Zeit) benötigt, um die Suche überhaupt vorzubereiten? (gerade wenn nur eine kleine Teilmenge der möglichen Werte gesucht wird, dürfte selbst O(n²) günstiger sein als O(n+m))

life

du solltest aber bedenken, dass dein verfahren mit etwas pech einfach ewig dauert (wenn man davon ausgeht, dass rand echte zufallszahlen liefert).. Relevant wird das besonders, wenn sich dein n dem Wertebereich m stark annähert. So z.b. wenn du jetzt 48 paarweise verschiedene Zufallszahlen zwischen 0 - 50 suchen möchtest..

random_shuffle ist für das Problem auch nicht unbedingt meine erste Wahl, da du damit einfach viel zu viel machst und dann nachher wieder ein Teil rausschmeißt (wobei random_shuffle dann besser wird wenn sich n m annähered (also genau umgekehrt))..

Jester

life schrieb:

das mit den doppelten zufallszahlen verhindern geht auch effektiver..

Wie, noch effektiver als wenn keine doppelten mehr drin sind? Also sozusagen *gar* keine doppelten mehr drin? Oder meinst Du vielleicht effizienter? :p
Aber ne schöne Lösung!

Allerdings kann man die erwartete Anzahl an Schritten ausrechnen. Die Schätze ich mal auf knapp über 1, bei diesen Werten. Die Wahrscheinlichkeit, daß es terminiert liegt übrigens bei 1. Die für unendliches Weiterlaufen bei 0, es kann also eigentlich nicht unendlich lange laufen. Beliebig lange schon, aber halt nicht unendlich.

life

Jester schrieb:

Allerdings kann man die erwartete Anzahl an Schritten ausrechnen. Die Schätze ich mal auf knapp über 1, bei diesen Werten. Die Wahrscheinlichkeit, daß es terminiert liegt übrigens bei 1. Die für unendliches Weiterlaufen bei 0, es kann also eigentlich nicht unendlich lange laufen. Beliebig lange schon, aber halt nicht unendlich.

Beliebig lange kann aber schon ganz lange sein ;). Und im "worst-case" braucht der Algorithmus nunmal unendliche lange, obwohl die wahrscheinlichkeit für den "worst-case" bei 0 liegt (hört sich zugegebenermaßen irgendwie paradox an)

Jester

Nein, dieser worst-case tritt sicher nicht ein. Seine Wahrscheinlichkeit liegt nämlich bei 0.

life

Auch wenn der Fall nie auftritt, denke ich, kann man ihn als worst-case bezeichnen.. oder was ist dann deiner Meinung nach der worst-case bei dem Algorithmus? :p

Jester

life schrieb:

Auch wenn der Fall nie auftritt, denke ich, kann man ihn als worst-case bezeichnen.. oder was ist dann deiner Meinung nach der worst-case bei dem Algorithmus? :p

Das ist natürlich ne berechtigte Frage.

Aber wie relevant ist ein "worst-case", der nie eintritt?

CStoll

"worst case" ist der schlechteste Fall, der eintreten KANN - von daher brauchst du etwas definitiv unmögliches nicht zu betrachten

Jester schrieb:

Wie, noch effektiver als wenn keine doppelten mehr drin sind? Also sozusagen *gar* keine doppelten mehr drin? Oder meinst Du vielleicht effizienter? :p

Da fällt mir zu ein, wie(*) einmal ein Prof süffisant zu mir sagte:

Ihre (Programm-)Lösung ist wirklch sehr effizient,
nur leider nicht effektiv

Seitdem hat sich der Unterschied zwischen effizient und effektiv bei
mir eingebrannt

P.S.: (*) Nein, in diesem Fall meine ich wirklich wie und nicht als

Jester

CStoll schrieb:

"worst case" ist der schlechteste Fall, der eintreten KANN - von daher brauchst du etwas definitiv unmögliches nicht zu betrachten

Dann gibt es allerdings auch Algorithmen, die garkeinen worst-case besitzen...

xGhost

Es gibt nur eine Gute version

http://www.openbsd.org/de/crypto.html#prng

Musst mal schauen wo die die libs bekommst.
Ist glaube ich in glibc integriert *irrtum vorbehalten*

gg