Ich habe als Hausaufgabe folgenden Code bekommen:
Er soll ein Programm darstellen, welches mit anzeigt, ob die von mir (noch nicht) implementierten Methoden, die den größten gemeinsamen Teiler (= greates commen dividend = gcd) auf euklidischer oder naive Art errechnen sollen, korrekt sind.
Wenn ich das Programm starte, bekomme ich folgende Fehlermeldung:
Wenn ich die Methoden implementiere, bekomme ich natürlich immer noch die gleiche Fehlermeldung. Wir sollen nicht (wir dürfen sogar nicht) am sonstigen Code basteln. Ist der Code fehlerhaft?
Java:
import java.math.BigInteger;
import java.util.Random;
public class Gcd {
public static BigInteger gcdNaive(BigInteger a, BigInteger b) {
// bitte implementieren Sie diese Methode
return BigInteger.ZERO;
}
public static BigInteger gcdEuclid(BigInteger a, BigInteger b) {
// bitte implementieren Sie diese Methode
return BigInteger.ZERO;
}
public static boolean testNaive(int sample_size, int num_bits, Random random) {
for(int i = 0; i < sample_size; i++) {
BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
BigInteger gcd = gcdNaive(a, b);
if(!gcd.equals(a.gcd(b))) {
System.out.println("Naive algorithm: Wrong solution!");
System.out.println(" for gcd(" + a + ", " + b + "):"
+ " Expected " + a.gcd(b) + " but got " + gcd);
return false;
}
}
return true;
}
public static boolean testEuclid(int sample_size, int num_bits, Random random) {
for(int i = 0; i < sample_size; i++) {
BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
BigInteger gcd = gcdEuclid(a, b);
if(!gcd.equals(a.gcd(b))) {
System.out.println("Euclidean algorithm: Wrong solution!");
System.out.println(" for gcd(" + a + ", " + b + "):"
+ " Expected " + a.gcd(b) + " but got " + gcd);
return false;
}
}
return true;
}
public static long benchmarkNaive(int sample_size, int num_bits, Random random) {
long time_sum = 0;
for(int i = 0; i < sample_size; i++) {
BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
long start = System.nanoTime();
BigInteger gcd = gcdNaive(a, b);
time_sum += System.nanoTime() - start;
if(!gcd.equals(a.gcd(b)))
System.out.println("Naive algorithm: Wrong solution!");
}
return time_sum / sample_size;
}
public static long benchmarkEuclid(int sample_size, int num_bits, Random random) {
long time_sum = 0;
for(int i = 0; i < sample_size; i++) {
BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
long start = System.nanoTime();
BigInteger gcd = gcdEuclid(a, b);
time_sum += System.nanoTime() - start;
if(!gcd.equals(a.gcd(b)))
System.out.println("Euclidean algorithm: Wrong solution!");
}
return time_sum / sample_size;
}
public static void main(String[] args) {
Random random = new Random();
boolean ok = true;
if(!testNaive(100, 16, random)) {
ok = false;
}else{
System.out.println("Naive algorithm seems to be correct!");
}
if(!testEuclid(100, 16, random)) {
ok = false;
}else{
System.out.println("Euclidean algorithm seems to be correct!");
}
if(!ok)
return;
int sample_size = 10;
System.out.println("Benchmark:");
System.out.println(String.format("%12s %24s %24s",
"#bits", "runtime (naive)", "runtime (Euclidean)"));
int num_bits = 4;
while(true) {
long naive_time = benchmarkNaive(sample_size, num_bits, random);
long euclid_time = benchmarkEuclid(sample_size, num_bits, random);
System.out.println(String.format("%12s %24s %24s", num_bits,
((naive_time / 1000000L) + "." + String.format("%06d", naive_time % 1000000L)),
((euclid_time / 1000000L) + "." + String.format("%06d", euclid_time % 1000000L))));
if(naive_time * sample_size > 5L * 1000000000L
|| euclid_time * sample_size > 5L * 1000000000L)
break;
num_bits = num_bits << 1;
}
System.out.println("All timings are averages over " + sample_size
+ " runs measured in ms");
}
};
Er soll ein Programm darstellen, welches mit anzeigt, ob die von mir (noch nicht) implementierten Methoden, die den größten gemeinsamen Teiler (= greates commen dividend = gcd) auf euklidischer oder naive Art errechnen sollen, korrekt sind.
Wenn ich das Programm starte, bekomme ich folgende Fehlermeldung:
Exception in thread "main" java.lang.Error: Unresolved compilation problems:
The method format(Locale, String, Object[]) in the type String is not applicable for the arguments (String, String, String, String)
The method format(String, Object[]) in the type String is not applicable for the arguments (String, long)
The method format(String, Object[]) in the type String is not applicable for the arguments (String, long)
at gcdP.Gcd.main(Gcd.java:123)
Wenn ich die Methoden implementiere, bekomme ich natürlich immer noch die gleiche Fehlermeldung. Wir sollen nicht (wir dürfen sogar nicht) am sonstigen Code basteln. Ist der Code fehlerhaft?
Zuletzt bearbeitet: