Hallo
Folgende Aufgabe habe ich in einem Lehrbuch für Algorithmen gefunden.
Soweit ich das Verstanden habe, sollen vier Versuche gestartet werden (für N = 10^3, 10^4 ... usw) wobei zwei Arrays mit N 6-stelligen Zufallszahlen gefüllt werden. Anschließend soll geprüft werden, wieviele der Elemente in Array A in Array B vorhanden sind. Das ganze soll für jeden Wert für N, T mal gemacht werden.
Das bedeutet ich soll T mal jeweils 1 000, 10 000 100 000 und 1 000 000 Zufallszahlen zwischen 100 000 und 999 999 in zwei Arrays speichern, und dabei zählen, wieviele Werte in Array A in Array B vorhanden sind und daraus dann den Durchschnitt berechnen.
Für einen Testlauf mit t = 1 habe ich folgende Ausgabe in der Konsole:
Number of Trials: 1
N: 1000 Average of matching numbers: 1.0
N: 10000 Average of matching numbers: 61.0
N: 100000 Average of matching numbers: 7112.0
N: 1000000 Average of matching numbers: 496953.0
Hab ich irgendwo einen Denkfehler gemacht? Sind das realistische Werte?
Folgende Aufgabe habe ich in einem Lehrbuch für Algorithmen gefunden.
Write a Binary Search method that takes an int value T as command-line argument and runs T trials of the following experiment for N=10^3,10^4,10^5, and 10^6 : generate two arrays of N randomly generated positive six-digit int values. Find the number of values that appear in both arrays. Print a table giving the average value of this quantity over the T trials for each value of N.
Soweit ich das Verstanden habe, sollen vier Versuche gestartet werden (für N = 10^3, 10^4 ... usw) wobei zwei Arrays mit N 6-stelligen Zufallszahlen gefüllt werden. Anschließend soll geprüft werden, wieviele der Elemente in Array A in Array B vorhanden sind. Das ganze soll für jeden Wert für N, T mal gemacht werden.
Das bedeutet ich soll T mal jeweils 1 000, 10 000 100 000 und 1 000 000 Zufallszahlen zwischen 100 000 und 999 999 in zwei Arrays speichern, und dabei zählen, wieviele Werte in Array A in Array B vorhanden sind und daraus dann den Durchschnitt berechnen.
Java:
public static void binSearchTrials(int t)
{
System.out.println("Number of Trials: " + t + "\n");
//start with n = i random numbers;
for(int i = 1000; i <= Math.pow(10, 6); i *= 10)
{
int[] a = new int[i];
int[] b = new int[i];
double[] sumsAfterTrial = new double[t];
//start with trial number = j + 1;
for(int j = 0; j < t; j++)
{
double sum = 0.0;
//fill the arrays with n 6 digit random numbers
for(int k = 0; k < i; k++)
{
a[k] = StdRandom.uniform(100000, 1000000);
b[k] = StdRandom.uniform(100000, 1000000);
}
Arrays.sort(b);
for(int l = 0; l < a.length; l++)
{
//binarySearch returns -1 if key can't be found in array
if(binarySearch(a[l], b) > 0)
{
sum++;
}
}
sumsAfterTrial[j] = sum;
}
double sumOfAverages = 0.0;
for(int k = 0; k < t; k++)
{
sumOfAverages += sumsAfterTrial[k];
}
System.out.println("N: " + i + " Average of matching numbers: " + sumOfAverages / t + "\n");
}
}
Für einen Testlauf mit t = 1 habe ich folgende Ausgabe in der Konsole:
Number of Trials: 1
N: 1000 Average of matching numbers: 1.0
N: 10000 Average of matching numbers: 61.0
N: 100000 Average of matching numbers: 7112.0
N: 1000000 Average of matching numbers: 496953.0
Hab ich irgendwo einen Denkfehler gemacht? Sind das realistische Werte?