Колкото и да е странно, този въпрос има 0 гласа за, но 4 отговора и не намирам нито един от тях за наистина задоволителен. Ето пример за внедряване + тест, използвайки 4 различни метода и сравнявайки ги:
import java.util.ArrayList;
import java.util.HashMap;
public class Fib {
// Straightforward implementation:
public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
// Using array:
static int[] memoArray;
public static int fibArray(int n) {
memoArray = new int[n];
return fibArrayHelper(n);
}
private static int fibArrayHelper(int n) {
if (n <= 1) {
return n;
} else {
if (memoArray[n - 2] != 0) {
return memoArray[n - 2];
}
memoArray[n - 2] = fibArrayHelper(n - 2) + fibArrayHelper(n - 1);
return memoArray[n - 2];
}
}
// Using ArrayList:
static ArrayList < Integer > memoArrayList = new ArrayList < Integer > ();
public static int fibArrayList(int n) {
return fibArrayListHelper(n);
}
private static int fibArrayListHelper(int n) {
if (n <= 1) {
return n;
} else {
if (n - 2 < memoArrayList.size())
return memoArrayList.get(n - 2);
else {
memoArrayList.add(fibArrayListHelper(n - 2) + fibArrayListHelper(n - 1));
return memoArrayList.get(n - 2);
}
}
}
// Using HashMap:
static HashMap < Integer, Integer > memoHash = new HashMap < Integer, Integer > ();
static public int fibHashMap(int n) {
if (n <= 1)
return n;
if (memoHash.get(n) == null) {
memoHash.put(n - 2, fibHashMap(n - 1) + fibHashMap(n - 2));
}
return memoHash.get(n - 2);
}
public static void main(String args[]) {
long preTime, postTime;
int x = 35;
preTime = System.nanoTime();
System.out.printf("%17s: %d", "fib(" + x + ")", fib(x));
postTime = System.nanoTime();
System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);
preTime = System.nanoTime();
System.out.printf("%17s: %d", "fibArray(" + x + ")", fibArray(x));
postTime = System.nanoTime();
System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);
preTime = System.nanoTime();
System.out.printf("%17s: %d", "fibArrayList(" + x + ")", fibArrayList(x));
postTime = System.nanoTime();
System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);
preTime = System.nanoTime();
System.out.printf("%17s: %d", "fibHashMap(" + x + ")", fibHashMap(x));
postTime = System.nanoTime();
System.out.printf(", computed in %10d nanoseconds.\n", postTime - preTime);
}
}
person
Clément
schedule
02.02.2017