Ungewollte Größen bei Ausgabe von Zufallszahlen

Um noch zu deinem eigentlichen Problem was zu sagen:

Du musst x vor Beginn der while-Schleife wieder auf true setzen, sonst wird die nämlich direkt übersprungen. D.h. die Array Elemente nach Index 0 werden nie zugewiesen. Die Werte die du also ausgegeben bekommst, sind die Werte, die noch von einem anderen auf dem Stack stehen, weil dein Array bei "Erzeugung" nicht mit bspw. 0 initialisiert wird.

Arijum

Vielen Dank erstmal für eure Antworten

Es ging mir bei dieser Übung hauptsächlich um Arrays, Bubblesort wird folgen, ich denke aber ich nehme einen anderne Algorithmus, hauptsache ich verstehe das ganze^^

Wusste ja garnicht, dass Arrays in dieser Form nicht erlaubt seien Oo. Wenn man doch mit Strings arbeitet, und man den Buffer beliebig erweitern will, so kommt man doch nicht drumrum

@CStoll: Vielen Dank, waren alles Denkfehler, aber doch Fehler und diesen sollte man immer vorbeugen. Natürlich sollte dort 50 statt 10 stehen und == statt = verwendet werden. thx

@Dobi: Wie du siehst arbeite ich mich schritt nach schritt ein. Das besondere am Programmieren ist eben dieses verstrckte, die vielen Algorythmen usw.^^ Eine einfache GUI ist doch langweilig Nuja arbeite im mom. hauptsächlich mit std. Evtl. probiere ich in Zukunft auch die stl Bibliotheken

@wurzelkind: könntest du mir es mir bitte nochmals mit anderen Worten erklären? Habe mir schon gedacht, dass es mit dem Stack zutun hat.. Wieso muss ein Array bei der Initialisierung mit 0 abgeglichen werden?

CStoll

Worauf wurzelkind hinauswollte: Beim ersten Durchlauf der for()-Schleife ist x noch auf true, wird aber in der while-Schleife auf false gesetzt (in der inneren for-Schleife passiert dort nichts weiter). Beim zweiten Durchlauf der for-Schleife (und jedem weiteren) steht x auf false, d.h. die while-Schleife wird gar nicht erst betreten.
Dadurch ziehst du nur eine Zufallszahl und im übrigen Array bleibt der Müll drin stehen, der beim Anlegen des Arrays dort stand. Wenn du das Array mit int Arraywerte[7]={}; gleich initialisiert hättest, wären am Ende ein Haufen Nullen angezeigt worden.

PS: Fast vergessen, die Lösung für dieses Problem: setz ein x=false; vor die while-Schleife.

Arijum

So vielen Dank nochmals an alle. Ja, der Fehler war jener, dass Arrays, sollten sie nicht gefüllt werden, mit Zufallswerten gefüllt werden. Und natürlich der Fehler mit dem einmal auf x=false gesetzten Befehl.

@CStoll: Hast da was verwechselt^^ In meinem Fall müsste ein x=true jeweils vor der while und der for Funktion eingefügt werden. Thx nochmal

Hier nun der fertige funktionierende Code:

#include <iostream>
#include <cstdlib> 
#include <time.h> 

using namespace std;

int main () {
	int i=5;	
	int Arraywerte [i];
	srand (time(0)); 	
	for (i=0;i<7;i++) {
		bool x=true;
		while (x==true) {
			Arraywerte [i]=(rand()%50)+1;
			x=false;
			for (int j=0;j<i;j++) {
				if (Arraywerte [j]==Arraywerte [i]) {
					x=true;
				}

			}
		}
		cout<<"Die Zuffalszahl Nummer "<<i<<" ist: "<<Arraywerte[i]<<'\n';
	}
}

LordJaxom

Dobi schrieb:

int i=5;   
int Arraywerte [i];

funktioniert.

Ist aber trotzdem kein C++.

CStoll

Arijum schrieb:

Hier nun der fertige funktionierende Code:

Und das Array für deine Zahlen ist immer noch zu klein - du reservierst Platz für 5 Werte, quetschst danach aber 7 Werte hinein.
(und ich habe keine Ahnung, was regulär in dem Speicher steht, den die beiden überschüssigen Elemente überschreiben)

ipsec

Im Übrigen wählst du von allen Möglichkeiten, doppelte Zahlen auszuschließen, die mit Abstand ineffizienteste. Ich skizziere mal eine effiziente Variante:
1. Lege einen Conatiner mit den Elementen 1 bis 49 an.
2. Wähle zufällig eine Zahl aus diesem Container im Bereich 1-49. Vertausche (swap) diese Zahl mit der letzten im Container. (Beispiel: 3 wurde gewählt -> der Container enthält nun 1, 2, 49, 4, ..., 48, 3). Die 3 ist deine erste Lottozahl.
3. Wähle zufällig eine Zahl aus dem Container im Bereich 1-48 und vertausche sie mit der vorletzten Zahl. Das ist deine zweite Lottozahl.
4. Wähle zufällig eine Zahl aus dem Container im Bereich 1-47 und vertausche sie mit der vorvorletzten Zahl. Das ist deine dritte Lottozahl.
5. Fahre nach dem Muster fort, bis du 7 Zahlen hast.

volkard

ipsec schrieb:

Im Übrigen wählst du von allen Möglichkeiten, doppelte Zahlen auszuschließen, die mit Abstand ineffizienteste.

Ich gehe davon aus, daß das kleine break noch seinen Weg in die Suchschleife findet.
Die erste Zahl trifft immer.
Die zweite mit Wahrscheinlichkeit 48/49.
Die dritte mit Wahrscheinlichkeit 47/49.
usw.
Also braucht man durchschnittlich 1+49/48+49/47+49/46+49/45+49/44 mal raten.
Also 6.33 mal. Ach, soo viel schlimmer als Dein Weg, der erstmal 49 Zahlen füllen muß, wird es schon nicht sein.
Man braucht 6.33 mal statt 6 mal rand().
Und man braucht 21.77 Arrayzugriffe statt 61.

Manchmal macht es mich traurig, daß hier so oft die Anfänger verrissen werden, und zwar immer von Neulingen mit nur zwei bis drei Jahren Erfahrung mit schwacher Faktenlage.

ipsec

Es lang mir fern, irgendetwas zu verreissen, vielmehr wollte ich Möglichkeiten aufzeigen, wie man es besser machen kann. Und wenn man von O(n²) auf O(n) kommt und einen Algorithmus mit deterministischer Laufzeit hat anstelle eines, der potentiell nie terminiert, ist das m.E. eine deutliche Verbesserung, auch wenn bei 7 aus 49 der Unterschied selten spürbar sein wird.

Und darüber hinaus mag ich zwar erst seit 4 Jahren hier angemeldet sein, mit C++ habe ich aber schon länger zu tun.

volkard

ipsec schrieb:

Es lang mir fern, irgendetwas zu verreissen,

Er hat Mühe, die native Lösung zu schaffen, da braucht er sicher kein
Im Übrigen wählst du von allen Möglichkeiten, doppelte Zahlen auszuschließen, die mit Abstand ineffizienteste.

vielmehr wollte ich Möglichkeiten aufzeigen, wie man es besser machen kann.

Haste wohl nicht geschafft, wie ich nachgewiesen habe.

Und wenn man von O(n²) auf O(n) kommt

Wenn Dein O(n) lahmer ist als sein O(n²), dann ist das akademischer Unfug.

und einen Algorithmus mit deterministischer Laufzeit hat anstelle eines, der potentiell nie terminiert,

Auch ein wenig weltfremd.

ist das m.E. eine deutliche Verbesserung, auch wenn bei 7 aus 49 der Unterschied selten spürbar sein wird.

Egal, welche nun schneller ist, seine ist sicher nicht die von allen Lösungen ineffizienteste.

Wie kommst du eigentlich auf die Rechnung zum Erwartungswert? Sie würde auch noch ein endliches Ergebnis für 50 aus 49 ergeben, wo Unendlich herauskommen müsste.

Geraten und nachgemessen. Übereinstimmung.

#include <iostream>
using namespace std;

int main (int argc, const char * argv[])
{
    double randCount=0,arrayCount=0,runCount=0;
	for(;;) {
		int zahlen[6];
		for(int i=0; i<6; ++i) {
nochmal:
			int n=rand()%49+1;
			++randCount;
			for(int j=0; j<i; ++j){
                ++arrayCount;
				if(zahlen[j]==n) {
					goto nochmal;
				}
			}
            ++arrayCount;
			zahlen[i]=n;
		}
		++runCount;
		cout<<randCount/runCount<<'\t'<<arrayCount/runCount<<'\n';
	}
}

Und darüber hinaus mag ich zwar erst seit 4 Jahren hier angemeldet sein, mit C++ habe ich aber schon länger zu tun.

Für Dich speziell hätte ich die Jahre wohl höher legen sollen. Aber allgemein scheint so bei 2 bis 3 Erfahrungsjahren das Maximum des von mir angesprochenen Problems zu liegen.

Die Mecker geht auch kaum an Dich. Du warst nur gerade da, um ein Problem anzusprechen, das mich seit Jahren juckt.

volkard

Wie kommst du eigentlich auf die Rechnung zum Erwartungswert? Sie würde auch noch ein endliches Ergebnis für 50 aus 49 ergeben, wo Unendlich herauskommen müsste.

Mal schauen...
49/49 + 49/48 + 49/47 + 49/ 46 + ... + 49/3 + 49/2 + 49/1 + 49/0
Naja, Unendlich würde ich nicht sagen, sondern Undefiniert.

Mitleid

ipsec schrieb:

Es lang mir fern, irgendetwas zu verreissen, vielmehr wollte ich Möglichkeiten aufzeigen, wie man es besser machen kann. Und wenn man von O(n²) auf O(n) kommt und einen Algorithmus mit deterministischer Laufzeit hat anstelle eines, der potentiell nie terminiert, ist das m.E. eine deutliche Verbesserung, auch wenn bei 7 aus 49 der Unterschied selten spürbar sein wird....

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert. Und da "der Algorithmus" hier keine variable Eingabe hat würde mich mal interessieren was hier dein n sein soll?

SeppJ

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Und da "der Algorithmus" hier keine variable Eingabe hat würde mich mal interessieren was hier dein n sein soll?

Ahh, da ist mit ipsec ein bisschen der innere Programmierer durchgebrannt, der ein Problem immer so abstrakt wie möglich behandelt. Du weißt sicherlich selbst, was er mit n meint. Und sein Algorithmus ist sicher auch für sehr viele Fälle von X Zahlen aus Y der beste. Nur bei dem X/Y Verhältnis des konkreten Problems 6 aus 49 ist er schlechter als der naive Algorithmus (der für allgemeine X und Y tatsächlich sehr ineffizient werden kann).

Mitleid

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Die Annahme, dass rand() sich standardkonform verhält reicht.

SeppJ schrieb:

...Du weißt sicherlich selbst, was er mit n meint. ...

Nö. Erklärs mir.

Ich hab die vorgeschlagenen Lösungen und meinen eigenen Ansatz (von dem ich mir mehr erhofft hatte ) mal gegeneinander gebencht; nach jeder Ziehung wird die Summe zusammengerechnet, um 1. den Optimizer zu überlisten und 2. die Benutzung der gezogenen Zahlen zu simulieren, die ja nachträglich zu erwarten ist. std::set verliert hier natürlich etwas; wenn euch die Benutzung der gezogenen Zahlen nicht interessiert, sind die Ergebnisse für den std::set-Ansatz dementsprechend wertlos. Code:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>

#include <cstdlib>
#include <ctime>

int const TURNS = 10000000;

int main() {
  std::clock_t bench[5];
  long sum = 0;

  std::srand(std::time(0));

  bench[0] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    std::set<int> s;

    do {
      s.insert(std::rand() % 49 + 1);
    } while(s.size() < 6);

    sum += std::accumulate(s.begin(), s.end(), 0);
  }

  bench[1] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    int numbers[] = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
                      31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
                      41, 42, 43, 44, 45, 46, 47, 48, 49, 50 };

    for(int j = 0; j < 6; ++j) {
      std::swap(numbers[j], numbers[std::rand() % (49 - j) + j]);
    }

    sum += std::accumulate(numbers, numbers + 6, 0);
  }

  bench[2] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    int werte[6];
    for(int j = 0; j < 6; ++j) {
      bool keep_going = true;

      while(keep_going) {
        werte[j] = std::rand() % 49 + 1;
        keep_going = false;

        for(int k = 0; k < j; ++k) {
          if(werte[k] == werte[j]) {
            keep_going = true;
            break;
          }
        }
      }
    }

    sum += std::accumulate(werte, werte + 6, 0);
  }

  bench[3] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    bool already_used[50] = {};
    int werte[6];

    for(int j = 0; j < 6; ++j) {
      int x;

      do {
        x = std::rand() % 49 + 1;
      } while(already_used[x]);

      werte[j] = x;
      already_used[x] = true;
    }

    sum += std::accumulate(werte, werte + 6, 0);
  }

  bench[4] = std::clock();

  std::cout << sum << '\n'
            << "std::set:  " << double(bench[1] - bench[0]) / CLOCKS_PER_SEC << '\n'
            << "ipsec:     " << double(bench[2] - bench[1]) / CLOCKS_PER_SEC << '\n'
            << "TE:        " << double(bench[3] - bench[2]) / CLOCKS_PER_SEC << '\n'
            << "bool-Feld: " << double(bench[4] - bench[3]) / CLOCKS_PER_SEC << '\n';
}

Ergebnis mit gcc 4.6.1 und -O3:

6000173451
std::set:  7.08
ipsec:     0.96
TE:        1.13
bool-Feld: 1.11

Bei niedrigeren Optimierungsstufen ist das Ergebnis weniger günstig für ipsec. Ich vermute, dass der gcc hier die komplette Schleife ausklappt, weil die Zahl der Durchläufe zur Compilezeit bekannt ist - im Gegensatz zu den anderen Ansätzen.

SeppJ

Mitleid schrieb:

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Die Annahme, dass rand() sich standardkonform verhält reicht.

Ganz sicher nicht. Laut Standard liefert rand() einfach nur Pseudozufallszahlen zwischen 0 und RAND_MAX. Streng genommen ist noch nicht einmal die Verteilung vorgegeben, aber selbst wenn man von Gleichverteilung ausgeht reicht das nicht. Eher im Gegenteil. Damit der Algorithmus terminiert, müsste garantiert sein, dass in endlicher Zeit mehr als 5 verschiedene Zahlen gezogen werden. Das wäre der Qualität der Zufallszahlen abträglich.

seldon schrieb:

Bei niedrigeren Optimierungsstufen ist das Ergebnis weniger günstig für ipsec. Ich vermute, dass der gcc hier die komplette Schleife ausklappt, weil die Zahl der Durchläufe zur Compilezeit bekannt ist - im Gegensatz zu den anderen Ansätzen.

Das ist ja auch sein volles Recht, das so zu machen. Letztendlich interessiert doch nur die volloptimierte Variante. Danke für den Test. Das bool-Feld und ipsec würde ich nach mehreren Durchläufen bei mir, die deine Ergebnisse auch mit anderen Compilern bestätigen, als gleich ansehen. Beide dicht gefolgt vom TE.

volkard

int werte[6];
		for(int j = 0; j < 6; ++j) {
nochmal:
			int z = std::rand() % 49 + 1;
			for(int k = 0; k < j; ++k)
				if(werte[k] == z) {
					goto nochmal;
				}
			werte[j]=z;
		}

std::set:  3.94
ipsec:     0.83
TE:        0.73
bool-Feld: 0.75
goto:      0.7

Mitleid

SeppJ schrieb:

Mitleid schrieb:

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Die Annahme, dass rand() sich standardkonform verhält reicht.

Ganz sicher nicht. Laut Standard liefert rand() einfach nur Pseudozufallszahlen zwischen 0 und RAND_MAX. Streng genommen ist noch nicht einmal die Verteilung vorgegeben, aber selbst wenn man von Gleichverteilung ausgeht reicht das nicht. Eher im Gegenteil. Damit der Algorithmus terminiert, müsste garantiert sein, dass in endlicher Zeit mehr als 5 verschiedene Zahlen gezogen werden. Das wäre der Qualität der Zufallszahlen abträglich.

Der Standard garantiert dir, dass für einen bestimmten, mit srand() angenommenen Startwert die Folge der mit rand() erzeugten Pseudozufallszahlen identisch ist. Somit wird das ein endliches Problem, welches sich für jeden Fall wunderbar durchprobieren lässt. Der Beweis der Terminierung kann also stets locker erbracht werden.

SeppJ

Das ist doch Unsinn! Das hat mit der Standardkonformität der Implementierung überhaupt gar nichts zu tun! Du probierst für jede Implementierung einfach nur aus, ob der Algorithmus terminiert. Aber weder garantiert dir der Standard an sich, dass der Algorithmus durch die vorgegebenen Eigenschaften von rand() immer terminiert, noch kennst du die Implementierung und musst für jede davon den Algorithmus erneut testen. Super Beweis!

Und schönerweise hast du damit sogar schon gezeigt, wie der Gegenbeweis läuft: Ich muss nur einen einzigen Startwert finden, der in einer Endlosschleife endet. Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren? Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

volkard

SeppJ schrieb:

Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren?

Ich würde darauf wetten. Das heißt, ich würde den Algo des Threaderstellers ohne Schmerzen in Produktivcode verwenden.

Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

Ja, deswegen kann der Standard hier nichts garantieren.