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!

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));
+	}
+
+}