Doppelte Arraywerte

Sebastian Pizer schrieb:

Zu diesem Problem gibt es mehrere Lösungswege, von denen auch welche dabei sind, die keine extra Überprüfung auf doppelte Einträge benötigen.

ich heiß zwar nicht KevDi aber denkst du dabei an spezielle algos, und wenn ja kannst mir mal nen tipp geben das ich schon mal bischen los googlen kann ?

lg lolo

knivil

noobLolo schrieb:

ich heiß zwar nicht KevDi aber denkst du dabei an spezielle algos, und wenn ja kannst mir mal nen tipp geben das ich schon mal bischen los googlen kann ?

Benutze doch die Suchfunktion. Das Problem trat hier schon oefters auf. Auch ist Ziehen ohne Zuruecklegen nun nicht schwer zu implementieren. Man macht es einfach so wie bei einer realen Lottoziehung. Hier, irgendwo weit unten: http://www.c-plusplus.net/forum/viewtopic-var-t-is-172876.html

Ja es geht da um das Lottoprogramm. Hab auch schon danach gegooglet aber die Lösungen die da genannt wurden, wurden aber mit anderen Methoden gelöst als die die wir bisher in der schule gemacht haben. DIe konkrete aufgabe ist die das wir ein Programm schreiben müssen was 6 Zufallszahlen zwischen 1 und 49 in ein Feld schreibt wobei keine davon doppelt vorkommen darf und dann ausgibt.

also so hab ichs jetzt mal versucht

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
	srand(time(0));
	int arr[50] = {0};
	int count = 0;
	int buffer;
	while(count < 6){
	  buffer = rand()%49+1;
	  if(arr[buffer] == 0){
	    arr[buffer] = buffer;
	    printf("%d\n",buffer);
	    count++;
	  }
	}
	return 0;
}

lg lolo

knivil

while(count < 6){
      buffer = rand()%49+1;
      if(arr[buffer] == 0){
        count++;
      }

Prinzipiell eine Endlosschleife, aber unwahrscheinlich. Jedoch kann sie durchaus mehr als 6 Versuche brauchen. Das ist schlecht.

Sebastian Pizer

knivil schrieb:

while(count < 6){
      buffer = rand()%49+1;
      if(arr[buffer] == 0){
        count++;
      }
Prinzipiell eine Endlosschleife, aber unwahrscheinlich. Jedoch kann sie durchaus mehr als 6 Versuche brauchen. Das ist schlecht.

Naja, in diesem Fall dürfte das mit einer der schnellsten Ansätze sein. Der Erwartungswert der Schleifendurchläufe für die x. Zahl (angefangen mit 0) ist 49/(49-x) nach Bernulli. Das macht dann durchschnittlich

$ \sum_{x=0}^5 \frac{49}{49-x} \approx 6,33 $

6,33 Schleifendurchläufe, wenn ich mich nicht verrechnet habe -- unter der Annahme, dass rand()%49+1 gleichverteilte und unabhängige Zufallswerte liefert. Klar, das kann auch mal überschritten werden... Aber in 27% der Fälle schafft man sogar die 6 Durchläufe. Die Wahrscheinlichkeit, dass man 3mal "Würfeln" muss pro neue Ziehung ist unter 1,1%. Der schlimmste Fall ist wirklich eine Endlosschleife, jedoch mit Wahrscheinlichkeit 0.

Ich finde die Variante mit dem Vertauschen aber auch am elegantesten. Hier nur der Psdueo-Code:

int arr[49] = {1,2,3,...,49};
for (int x=0; x<6; ++x) {
  int z = rand()%(49-x) + x;
  tausche arr[x] mit arr[z]
}
ausgabe von arr[0], arr[1], ..., arr[5]

noobLolo schrieb:

... und wenn ja kannst mir mal nen tipp geben das ich schon mal bischen los googlen kann ?

lg lolo

wie wäre es damit:

#include <algorithm> // std::copy, std::random_shuffle, std::swap
#include <cstdlib> // srand
#include <ctime> // time
#include <iostream>
#include <iterator> // std::ostream_iterator

int main()
{
    using namespace std;
    srand( time(0) );
    const int N = 49;
    const int anz = 6;
    int kugeln[N];
    for( int kugel = 1; kugel <= N; ++kugel )
        kugeln[kugel-1] = kugel;
    int feld[anz];
    int n = N;
    for( int i = 0; i < anz; ++i )
    {
        int i_zufall = rand() % n;
        feld[i] = kugeln[i_zufall]; // nehme eine zufällige Kugel im Intervall [0..n)
        kugeln[i_zufall] = kugeln[--n];     // fülle die entnommene Kugel durch die letzte Kugel auf und reduziere gleichzeitig die Anzahl
    }

    copy( feld, feld+anz, ostream_iterator< int >( cout << anz <<" aus " << N << ": ", " " ) ); // .. und ausgeben
    cout << endl;
    return 0;
}

denke das ist auf jeden fall schneller als ein array mit 50 werten anzulegen, mischen um dann 6 rauszuholen, denke die schleife wird ganz selten öfter als 12 mal durchlaufen... das ist keine endlos schleife, sonst würd sie ja nie terminieren...

wenn du was hast was das mit 6 loops schafft dann zeig mal her:)

lg lolo

Sebastian Pizer schrieb:

Ich finde die Variante mit dem Vertauschen aber auch am elegantesten. Hier nur der Psdueo-Code:
int arr[49] = {1,2,3,...,49};
for (int x=0; x<6; ++x) {
  int z = rand()%(49-x) + x;
  tausche arr[x] mit arr[z]
}
ausgabe von arr[0], arr[1], ..., arr[5]

ich kann mich ja irren, aber ist es nicht so, dass hier die Zahlen 1 bis 6 etwas öfter vorkommen können, als alle anderen? Sollte man nicht die Schleife aus diesem Grund von x=0 bis x<49 laufen lassen?

Sebastian Pizer

Werner_logoff schrieb:

ich kann mich ja irren, aber ist es nicht so, dass hier die Zahlen 1 bis 6 etwas öfter vorkommen können, als alle anderen?

Nein, eigentlich nicht. Also, davon abgesehen, dass rand()%N keine exakte Gleichverteliung liefert. Die Schleifen-Invariante ist: Die ersten x Elemente wurden schon fest ausgewählt und die Elemente dahinter "sind noch im Sack". Ein neues Element wird zufällig aus "dem Sack" ausgewählt. Die Sortierung "im Sack" spielt keine Rolle, da z gleichverteilt "gezogen" wird.

Es ist also im Endeffekt das gleiche wie das, was Du machst -- nur in einem einzigen Array, was beides speichert: Ausgewählte Elemente und die noch übrigen Elemente.