Doppelte Arraywerte

Athar

Wenn die Reihenfolge der Zahlen keine Rolle spielt, einfach std::sort + std::unique anwenden. Danach sind die Zahlen der Größe nach sortiert.
Wenn die Reihenfolge aber beibehalten werden muss, dann einfach das Array umkopieren und die Elemente währenddessen in ein set packen. Wenn ein Wert schon drin ist, ignorieren.

Sebastian Pizer

KevDi schrieb:

ich hab seit diesem Schuljahr Programmieren in C++ in der Schule. Nun sollen wir ein Program schreiben bei dem 6 Zufallszahlen in ein Feld geschrieben werden. Nun soll das Feld auf doppelte Einträge überprüft werden.

Sind keine doppelten Einträge im Feld mehr, soll es ausgegeben werden.

Ist das wirklich die Aufgabe? Was soll denn passieren, wenn Du einen doppelten Eintrag findest?

Oder ist die Aufgabe vielleicht "Schreibe ein Programm, was 6 Zufallszahlwn zwischen 1 bis 49 ausgibt, wovon keine Zahl doppelt vorkommt."? 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.

KevDi schrieb:

int main()
{
   const int anz = 6;
   int feld[anz];
    
   srand(time(NULL));
    
   for (int i = 0; i < anz; i++)
   {
      feld[i] = rand()%49+1;
         cout<<feld[i]<<" ";
   }
   getch();
   return 0;
}
Mein Problem ist das ich keine Ahnung hab wie ich nun überprüfen kann ob die eine Zahl doppelt vorkommt oder nicht.

Es handelt sich also nicht um ein C++ Problem; denn Schleifen und if kennst Du ja angeblich. Du suchst nach einem Algorithmus der Dein Problem löst.

Nun, die Ausgabe in der Schleife, in der Du zu Zufallszahlen berechnest, ist hier nicht zielführend; denn wenn Du die ersten Elemente ausgegeben hast, weißt Du ja noch nicht, ob nicht dann doch noch Einträge folgen, die Du schonmal hattest. Du müsstest also erst die Zahlen berechnen, dann prüfen und dann eventuell ausgeben.

Bevor ich aber weitere Tipps gebe, warte ich lieber Deine Antwort ab auf meine erste Frage.

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.