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