summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-14 15:47:11 -0500
committerHaidong Ji2018-08-14 15:47:11 -0500
commit9633df82de06c9ef6b88bb2068e3fdf19a1554c4 (patch)
tree16f3aa314d15a4cc923466f108a82f8879576e78
parentfe9441e23222295ae6ffc00099dbbb29ddc5f9c5 (diff)
Last digit of fib and some renaming refactoring!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java30
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java14
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java32
3 files changed, 69 insertions, 7 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java b/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java
new file mode 100644
index 0000000..5467782
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FibLastDigit.java
@@ -0,0 +1,30 @@
+import java.util.Scanner;
+
+public class FibLastDigit {
+
+ public static int lastDigitNaive(int n) {
+ if (n <= 1)
+ return n;
+ return (lastDigitNaive(n - 1) + lastDigitNaive(n - 2)) % 10;
+ }
+
+ public static int lastDigitOptimized(int n) {
+ if (n <= 1)
+ return n;
+ final int[] fibLastDigitArray = new int[n + 1];
+ fibLastDigitArray[0] = 0;
+ fibLastDigitArray[1] = 1;
+ for (int i = 2; i < n + 1; i++) {
+ fibLastDigitArray[i] = (fibLastDigitArray[i - 1] + fibLastDigitArray[i - 2]) % 10;
+ }
+ return fibLastDigitArray[n];
+ }
+
+ public static void main(String[] args) {
+ Scanner in = new Scanner(System.in);
+ int n = in.nextInt();
+
+ System.out.println(lastDigitOptimized(n));
+ }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java b/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
index 94217ed..53388fe 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/Fibonacci.java
@@ -8,16 +8,16 @@ public class Fibonacci {
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];
+ public static long fib_optimized1(int n) {
+ if (n <= 1)
+ return (long) n;
+ final long[] fibArray = new long[n+1];
fibArray[0] = 0;
fibArray[1] = 1;
- for (int j = 2; j < i+1; j++) {
- fibArray[j] = fibArray[j - 1] + fibArray[j - 2];
+ for (int i = 2; i < n+1; i++) {
+ fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
- return fibArray[i];
+ return fibArray[n];
}
public static void main(String args[]) {
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java
new file mode 100644
index 0000000..4646c62
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FibLastDigitTest.java
@@ -0,0 +1,32 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+public class FibLastDigitTest {
+ @Test
+ void testFibonacci0() {
+ assertEquals(0, FibLastDigit.lastDigitNaive(0));
+ assertEquals(0, FibLastDigit.lastDigitOptimized(0));
+ }
+
+ @Test
+ void testFibonacci1() {
+ assertEquals(1, FibLastDigit.lastDigitNaive(1));
+ assertEquals(2, FibLastDigit.lastDigitNaive(3));
+ assertEquals(1, FibLastDigit.lastDigitOptimized(1));
+ assertEquals(2, FibLastDigit.lastDigitOptimized(3));
+ }
+
+ @Test
+ void testFibonacci40() {
+ assertEquals(5, FibLastDigit.lastDigitNaive(40));
+ assertEquals(5, FibLastDigit.lastDigitOptimized(40));
+ assertEquals(9, FibLastDigit.lastDigitOptimized(331));
+ assertEquals(5, FibLastDigit.lastDigitOptimized(327305));
+// assertEquals(1, Fibonacci.fib_optimized1(2));
+// assertEquals(2, Fibonacci.fib_optimized1(3));
+// assertEquals(3, Fibonacci.fib_optimized1(4));
+// assertEquals(102334155, Fibonacci.fib_optimized1(40));
+ }
+
+}