Hallo.
Wie kann man ein Array erzeugen, sodass die Verteilung unterschiedlich ist und gewisse Zahlen (z.B. die 0 und die 14) immer vorhanden sind?
Bis jetzt habe ich den Array so erstellt:
Ich möchte gerne die Binäre-Suche und die Interpolations-Suche mit zwecks der Laufzeit vergleichen. Hierzu erstelle ich gleich verteilte Daten also 0,1,2,3...99 und nicht gleich verteilte Daten also z.B. 0,4,6,7,14.... .
Da ich hierzu eine X-beliege Zahl suchen möchte, muss es eine Zahl sein, die immer generiert wird wenn ich auch nicht gleicht verteilte Daten erzeuge. Hat da jemand von euch eine Idee wie ich dies lösen kann?
Den kompletten Code findet ihr hier:
Wie kann man ein Array erzeugen, sodass die Verteilung unterschiedlich ist und gewisse Zahlen (z.B. die 0 und die 14) immer vorhanden sind?
Bis jetzt habe ich den Array so erstellt:
Java:
private void erzeugenVerteilt()
{
for (int i = 0; i < liste.length; i++) {
liste[i] = i*10 + zufall.nextInt(10);
}
}Ich möchte gerne die Binäre-Suche und die Interpolations-Suche mit zwecks der Laufzeit vergleichen. Hierzu erstelle ich gleich verteilte Daten also 0,1,2,3...99 und nicht gleich verteilte Daten also z.B. 0,4,6,7,14.... .
Da ich hierzu eine X-beliege Zahl suchen möchte, muss es eine Zahl sein, die immer generiert wird wenn ich auch nicht gleicht verteilte Daten erzeuge. Hat da jemand von euch eine Idee wie ich dies lösen kann?
Den kompletten Code findet ihr hier:
Java:
// BINÄRE SUCHE !!!
package A1;
import java.util.Random;
public class BinaereSuche
{
int[] liste; //Array wird definiert als "liste"
Random zufall = new Random(); // wird erzeugt für Klasse erzeugenUnsortiert()
int n = 0; // Anzahl der Suchschritte
int suchzahl; //Dies ist die gesuchte Zahl
int links; // linker Index
int rechts; // rechter Index
public BinaereSuche(int plätze) {
liste = new int [plätze];
//Anzahl an Plätze wird übergeben
}
// --> Sortiert
public void erzeugeSortiert() {
for (int i=0; i<liste.length; i++) {
//100 Zahlen werden erzeugt
liste[i] = i;
//Enthält zahlen von 0-99 --> 100 Zahlen
}
links = liste[0];
rechts = liste[99];
}
// --> Sortiert unterschiedlich verteilt
private void erzeugenVerteilt()
{
for (int i = 0; i < liste.length; i++) {
liste[i] = i*10 + zufall.nextInt(10);
}
links = liste[0];
rechts = liste[99];
}
// --> Unsortiert
public void erzeugenUnsortiert() {
for (int i=0; i<liste.length; i++){
int z1 = zufall.nextInt(100);
for (int z = 0; z < i; z++) {
if (z1 == liste[z]) {
i--;
z=100;
}else{
liste[i] = z1;
}
}
}
}
public void ausgabe() {
for (int i=0; i<liste.length; i++) {
System.out.println("Zahl: "+ liste[i] + " || Index: " + i);
}
}
//!!! Suchzahl muss also in Array vorhanden sein ??? FRAGE?
public int suchzeitBinaer(int suchzahl) {
int mitte;
//rechts = liste.length-1; // z.B. 0-99 Zahlen --> 99/2 = 49
do {
if (suchzahl >= liste.length) {
System.out.println("Suchzahl nicht enthalten");
return -1;
}
// Wenn Zahl größer als 99 in diesem Fall
mitte = (links+rechts)/2; // Mitte wird gebildet
n++;
System.out.println(mitte+" == Mitte | Schritt:" +n);
if (liste[mitte] == suchzahl) {
System.out.println("Suchzahl: " + mitte);
return mitte;
}
if (liste[mitte] > suchzahl) {
rechts = mitte-1;
n++;
System.out.println(rechts + " =="+" Rechts = Mitte -1"+" | Schritt:" +n );
}
if (liste[mitte] < suchzahl) {
links = mitte+1;
n++;
System.out.println(links + " =="+" Links = Mitte +1"+" | Schritt:" +n );
}
} while (links <= rechts && liste[mitte] != suchzahl);
System.out.println("Zahl nicht gefunden");
return -1;
}
public void ausgabe1() {
for (int i=0; i<liste.length; i++) {
System.out.println(liste[i] + " || Schritt: " + (i+1));
}
}
public static void main(String[] args)
{
BinaereSuche b1 = new BinaereSuche(100);
//b1.erzeugeSortiert();
b1.erzeugenVerteilt();
//b1.erzeugenUnsortiert();
//b1.ausgabe();
b1.suchzeitBinaer(12);
}
}
