+2 Daumen
1,7k Aufrufe

Aufgabe:

Grundsätzlich geht es um Zeitkomplexität, daher muss selber ein Algorithmus geschrieben werden, der nacheinander für die Indizes eines Arrays (also 0 bis size-1) eine Zufallszahl von 1 bis size erzeugt.

Ist die erzeugte Zufallszahl aber schon im Array enthalten, soll sie verworfen und neu generiert werden.


Problem/Ansatz:

Mein Problem ist eigentlich wie folgt (mein Java ist nicht so gut, wie meine Note es aussagt ;) ):

Ich habe mehrere Ansätze ausprobiert, aber scheiter gerade an folgendem Problem. Wenn ich über das Array iteriere, prüfe ich ob die generierte Zufallszahl im Array enthalten ist, findet er ein Duplikat, wird die Zahl neu generiert, aber weiter über das Array iteriert, heißt eine Zufallszahl die schon vorher vorgekommen ist, kann erneut vorkommen.

Leider stehe ich hier etwas auf dem Schlauch und es ist wahrscheinlich recht trivial.



int[] a = new int[size]; 

for(int i=0; i<a.length; i++) {
    int rnd = (int)(1+Math.random()*(size-1));
      for(int j=0; j<a.length; j++) {
        if(a[j] == rnd) {
        rnd = (int)(1+Math.random()*(size-1));
        } else {
        a[i] = rnd;
      }
    }
}


Update:

Okay, noch ein bisschen weiter gemacht, neuer Code mit deutlich besserem Ergebnis:

int[] a = new int[size];
       
      for (int i = 0; i < a.length;  ++i) {
      a[0] = (int)(1+Math.random()*(size-1));
            for (int j = 0; j < i; j++) {
                if (a[j] == a[i]) {
                    a[i] = (int)(1+Math.random()*(size));
                    j = 0;
                }
            }
        }

Das Problem ist in diesem Fall eher, das der Check für die Zahl im Index 0 nicht richtig funktioniert.

Avatar von

1 Antwort

+1 Daumen
 
Beste Antwort

int[] a = new int[size]; 

for(int i=0; i<a.length; i++) {
    bool unique;
do {
        int rnd = (int)(1+Math.random()*(size-1));
unique = true;
      for(int j=0; j < i; j++) {
        if(a[j] == rnd) {
unique = false;
        break;
        }
    }
if (unique) {
a[i] = rnd;
}
} while (!unique);
}
Die Zeitkomplexität ist katastrophal.
Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community