diff --git a/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java new file mode 100644 index 000000000000..41b3052a70e9 --- /dev/null +++ b/core-java-modules/core-java-numbers-3/src/main/java/com/baeldung/padovan/PadovanSeriesUtils.java @@ -0,0 +1,75 @@ +package com.baeldung.padovan; + +public class PadovanSeriesUtils { + + public static int nthPadovanTermRecursiveMethod(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + return nthPadovanTermRecursiveMethod(n - 2) + nthPadovanTermRecursiveMethod(n - 3); + } + + public static int nthPadovanTermRecursiveMethodWithMemoization(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + int[] memo = new int[n + 1]; + memo[0] = 1; + memo[1] = 1; + memo[2] = 1; + return nthPadovanTermRecursiveMethodWithMemoization(n, memo); + } + + private static int nthPadovanTermRecursiveMethodWithMemoization(int n, int[] memo) { + if (memo[n] != 0) { + return memo[n]; + } + memo[n] = nthPadovanTermRecursiveMethodWithMemoization(n - 2, memo) + nthPadovanTermRecursiveMethodWithMemoization(n - 3, memo); + return memo[n]; + } + + public static int nthPadovanTermIterativeMethodWithArray(int n) { + int[] memo = new int[n + 1]; + if (n == 0 || n == 1 || n == 2) { + return 1; + } + memo[0] = 1; + memo[1] = 1; + memo[2] = 1; + for (int i = 3; i <= n; i++) { + memo[i] = memo[i - 2] + memo[i - 3]; + } + return memo[n]; + } + + public static int nthPadovanTermIterativeMethodWithVariables(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + int p0 = 1, p1 = 1, p2 = 1; + int tempNthTerm; + for (int i = 3; i <= n; i++) { + tempNthTerm = p0 + p1; + p0 = p1; + p1 = p2; + p2 = tempNthTerm; + } + return p2; + } + + public static int nthPadovanTermUsingFormula(int n) { + if (n == 0 || n == 1 || n == 2) { + return 1; + } + + // Padovan spiral constant (plastic number) - the real root of x^3 - x - 1 = 0 + final double PADOVAN_CONSTANT = 1.32471795724474602596; + + // Normalization factor to approximate Padovan sequence values + final double NORMALIZATION_FACTOR = 1.045356793252532962; + + double p = Math.pow(PADOVAN_CONSTANT, n - 1); + return (int) Math.round(p / NORMALIZATION_FACTOR); + } +} + diff --git a/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java b/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java new file mode 100644 index 000000000000..8988160d0afd --- /dev/null +++ b/core-java-modules/core-java-numbers-3/src/test/java/com/baeldung/padovan/PadovanSeriesUtilsUnitTest.java @@ -0,0 +1,104 @@ +package com.baeldung.padovan; + +import static org.junit.Assert.assertEquals; +import org.junit.Test; + +public class PadovanSeriesUtilsUnitTest { + + // Test base cases for all methods + @Test + public void givenBaseCases_thenReturnCorrectValues() { + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(2)); + + assertEquals(1, PadovanSeriesUtils.nthPadovanTermUsingFormula(0)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermUsingFormula(1)); + assertEquals(1, PadovanSeriesUtils.nthPadovanTermUsingFormula(2)); + } + + // Test recursive method + @Test + public void givenTermToCalculate_thenReturnThatTermUsingRecursion() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermRecursiveMethod(term)); + } + + // Test recursive method with memoization + @Test + public void givenTermToCalculate_thenReturnThatTermUsingRecursionWithMemoization() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(term)); + } + + // Test iterative method with array + @Test + public void givenTermToCalculate_thenReturnThatTermUsingIterationWithArray() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(term)); + } + + // Test iterative method with variables + @Test + public void givenTermToCalculate_thenReturnThatTermUsingIterationWithVariables() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(term)); + } + + // Test formula method + @Test + public void givenTermToCalculate_thenReturnThatTermUsingFormula() { + int term = 10; + int expectedValue = 12; + assertEquals(expectedValue, PadovanSeriesUtils.nthPadovanTermUsingFormula(term)); + } + + // Test multiple terms to verify sequence correctness + @Test + public void givenMultipleTerms_thenReturnCorrectSequence() { + // Padovan sequence: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151 + int[] expectedSequence = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151}; + + for (int i = 0; i < expectedSequence.length; i++) { + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermRecursiveMethod(i)); + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(i)); + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(i)); + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(i)); + // Formula method may have slight approximation errors for larger terms + if (i < 15) { // Test formula for first 15 terms only + assertEquals("Term " + i, expectedSequence[i], PadovanSeriesUtils.nthPadovanTermUsingFormula(i)); + } + } + } + + // Test that all methods return the same result for the same input + @Test + public void givenSameInput_thenAllMethodsReturnSameResult() { + int term = 15; + + int recursiveResult = PadovanSeriesUtils.nthPadovanTermRecursiveMethod(term); + int memoizedResult = PadovanSeriesUtils.nthPadovanTermRecursiveMethodWithMemoization(term); + int arrayResult = PadovanSeriesUtils.nthPadovanTermIterativeMethodWithArray(term); + int variablesResult = PadovanSeriesUtils.nthPadovanTermIterativeMethodWithVariables(term); + + assertEquals(recursiveResult, memoizedResult); + assertEquals(recursiveResult, arrayResult); + assertEquals(recursiveResult, variablesResult); + } +} \ No newline at end of file