Java:
import java.math.BigInteger;
public abstract class BigCatalanMain {
protected static final int MAX_N = 8400;
protected static final int MIN_N = MAX_N / 2;
protected static final int RUNS = 300;
/*********************************************************************************************\
DO NOT MODIFY ANYTHING BELOW THIS LINE - and things above for your tests only (if necessary)!
\*********************************************************************************************/
public static void main(String[] args) {
if (args.length > 0) {
if(args[0].equalsIgnoreCase("naive")) {
(new BigCatalan()).cnNaiveRecLog(args.length > 1 && args[1].equalsIgnoreCase("random"));
} else if (args[0].equalsIgnoreCase("DP")) {
(new BigCatalan()).cnDynProgLog(args.length > 1 && args[1].equalsIgnoreCase("random"));
}
} else {
System.out.println("Usage: java " + BigCatalanMain.class.getCanonicalName() + " \"naive\"|\"DP\" [random]");
}
}
/*********************************************************************************************\
catalan - naive recursion
\*********************************************************************************************/
protected final void cnNaiveRecLog(boolean random) {
long timeStart, timeEnd;
// long memStart, memEnd;
int[] n = new int[RUNS];
for (int index = 0; index < RUNS; index++) {
n[index] = random ? MIN_N + (int)(Math.random() * (MAX_N - MIN_N)) : MAX_N;
}
// memStart = Runtime.getRuntime().totalMemory();
timeStart = System.currentTimeMillis();
for (int index = 0; index < RUNS; index++) {
cnNaiveRec(n[index]);
// System.gc();
}
timeEnd = System.currentTimeMillis();
// memEnd = Runtime.getRuntime().totalMemory();
System.out.println("NAIVE" + (random ? " (random) : " : " : ") + "Computation time : " + (timeEnd - timeStart) + " ms (ca. " + ((timeEnd-timeStart+50)/100)/10.0d + " s)");
// System.out.println("NAIVE" + (random ? " (random) : " : " : ") + "Java memory change : " + (memEnd - memStart) + " bytes (ca. " + ((memEnd - memStart)/(1024*1024)) + " MB)");
}
protected abstract BigInteger cnNaiveRec(int n);
/*********************************************************************************************\
catalan - dynamic programming
\*********************************************************************************************/
protected final void cnDynProgLog(boolean random) {
long timeStart, timeEnd;
// long memStart, memEnd;
int[] n = new int[RUNS];
for (int index = 0; index < RUNS; index++) {
n[index] = random ? MIN_N + (int)(Math.random() * (MAX_N - MIN_N)) : MAX_N;
}
// memStart = Runtime.getRuntime().totalMemory();
timeStart = System.currentTimeMillis();
for (int index = 0; index < RUNS; index++) {
cnDynProg(n[index]);
// System.gc();
}
timeEnd = System.currentTimeMillis();
// memEnd = Runtime.getRuntime().totalMemory();
System.out.println("DP" + (random ? " (random) : " : " : ") + "Computation time : " + (timeEnd - timeStart) + " ms (ca. " + ((timeEnd-timeStart+50)/100)/10.0d + " s)");
// System.out.println("DP" + (random ? " (random) : " : " : ") + "Java memory change : " + (memEnd - memStart) + " bytes (ca. " + ((memEnd - memStart)/(1024*1024)) + " MB)");
}
protected abstract BigInteger cnDynProg(int n);
}Kann jemand eine Unterklasse erstellen, der die Catalanzahlen berechnen?
wäre euch dankbar, bräuchte es für die schule, da sich mit diesem Programm größere Zahlen berchennen lassen sollten
Zuletzt bearbeitet von einem Moderator:
