summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-12 22:18:21 -0500
committerHaidong Ji2018-08-12 22:18:21 -0500
commitfe9441e23222295ae6ffc00099dbbb29ddc5f9c5 (patch)
tree28d3d0352d92064ed2c745a97ab4a0cb7a2669a8
parent24b8ab29aad9159d1eb285f72a0557c2daea4b11 (diff)
Fibonacci naive recursive and 1st optimization done!
It was kinda tricky to get it right, with array indexing and how many I needed to calculate. Good thing I was using TDD, which helped quite a bit in getting it done!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java30
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java29
2 files changed, 59 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java b/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
new file mode 100644
index 0000000..94217ed
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
@@ -0,0 +1,30 @@
+import java.util.Scanner;
+
+public class Fibonacci {
+ public static long fib_naive(int n) {
+ if (n <= 1)
+ return n;
+
+ return fib_naive(n - 1) + fib_naive(n - 2);
+ }
+
+ public static long fib_optimized1(int i) {
+ if (i <= 1)
+ return (long) i;
+ final long[] fibArray = new long[i+1];
+ fibArray[0] = 0;
+ fibArray[1] = 1;
+ for (int j = 2; j < i+1; j++) {
+ fibArray[j] = fibArray[j - 1] + fibArray[j - 2];
+ }
+ return fibArray[i];
+ }
+
+ public static void main(String args[]) {
+ Scanner in = new Scanner(System.in);
+ int n = in.nextInt();
+
+ System.out.println(fib_optimized1(n));
+ }
+
+} \ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java
new file mode 100644
index 0000000..52df692
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FibonacciTest.java
@@ -0,0 +1,29 @@
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+public class FibonacciTest {
+
+ @Test
+ void testFibonacci0() {
+ assertEquals(0, Fibonacci.fib_naive(0));
+ assertEquals(0, Fibonacci.fib_optimized1(0));
+ }
+
+ @Test
+ void testFibonacci1() {
+ assertEquals(1, Fibonacci.fib_naive(1));
+ assertEquals(1, Fibonacci.fib_optimized1(1));
+ }
+
+ @Test
+ void testFibonacci40() {
+ assertEquals(102334155, Fibonacci.fib_naive(40));
+ assertEquals(1, Fibonacci.fib_optimized1(2));
+ assertEquals(2, Fibonacci.fib_optimized1(3));
+ assertEquals(3, Fibonacci.fib_optimized1(4));
+ assertEquals(102334155, Fibonacci.fib_optimized1(40));
+ }
+
+}