public interface Fibonacci {

  /**
   * Calcule la valeur du terme de la suite de Fibonacci pour le rang indiqué.
   *
   * REGLE #0 f(0) = 0
   * REGLE #1 f(1) = 1
   * REGLE #2 f(n) = f(n-1) + f(n-2) si 2 < n
   * REGLE #3 f(n) = Exception si n < 0
   *
   * Premiers termes : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
   *
   * cf. https://fr.wikipedia.org/wiki/Suite_de_Fibonacci
   *
   * @param n le rang
   * @return la valeur du terme pour le rang indiqué
   * @throws IllegalArgumentException si le rang indiqué est négatif
   */
  int calculate(int n);

public interface Fibonacci {    /**    * Calcule la valeur du terme de la suite de Fibonacci pour le rang indiqué.    *    * REGLE #0 f(0) = 0    * REGLE #1 f(1) = 1    * REGLE #2 f(n) = f(n-1) + f(n-2) si 2 < n    * REGLE #3 f(n) = Exception si n < 0    *     * Premiers termes : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597    *     * cf. https://fr.wikipedia.org/wiki/Suite_de_Fibonacci    *    * @param n le rang    * @return la valeur du terme pour le rang indiqué    * @throws IllegalArgumentException si le rang indiqué est négatif    */   int calculate(int n);

public class RecursiveFibonacci implements Fibonacci {

  @Override
  public int calculate(int n) {
    throw new UnsopportedOperationException("bientôt");
  }

public class RecursiveFibonacci implements Fibonacci {    @Override   public int calculate(int n) {     throw new UnsopportedOperationException("bientôt");   }

public abstract class AbstractFibonacciTest {

  protected Fibonacci fibonacci;

  @Test
  public void testCalculateIndex0() {
    // Arrange
    final int n = 0;
    final int expected = 0;

    // Act
    final int result = fibonacci.calculate(n);

    // Assert
    Assertions.assertEquals(expected, result);
  }

public abstract class AbstractFibonacciTest {    protected Fibonacci fibonacci;    @Test   public void testCalculateIndex0() {     // Arrange     final int n = 0;     final int expected = 0;      // Act     final int result = fibonacci.calculate(n);      // Assert     Assertions.assertEquals(expected, result);   }

class RecursiveFibonacciTest extends AbstractFibonacciTest {

  public RecursiveFibonacciTest() {
    fibonacci = new RecursiveFibonacci();
  }

class RecursiveFibonacciTest extends AbstractFibonacciTest {    public RecursiveFibonacciTest() {     fibonacci = new RecursiveFibonacci();   }

@Test
public void testCalculateIndex1() {
  // Arrange
  final int n = 1;
  final int expected = 0;

  // Act
  final int result = fibonacci.calculate(n);

  // Assert
  Assertions.assertEquals(expected, result);
}

@Test public void testCalculateIndex1() {   // Arrange   final int n = 1;   final int expected = 0;    // Act   final int result = fibonacci.calculate(n);    // Assert   Assertions.assertEquals(expected, result); }

@Test
public void testCalculateIndex2() {
  // Arrange
  final int n = 2;
  final int expected = 2;

  // Act and assert
  doTestCalculate(n, expected);
}

@Test
public void testCalculateIndex3() {
  // Arrange
  final int n = 3;
  final int expected = 3;

  // Act and assert
  doTestCalculate(n, expected);
}

@Test
public void testCalculateIndex4() {
  // Arrange
  final int n = 4;
  final int expected = 5;

  // Act and assert
  doTestCalculate(n, expected);
}

@Test public void testCalculateIndex2() {   // Arrange   final int n = 2;   final int expected = 2;    // Act and assert   doTestCalculate(n, expected); }  @Test public void testCalculateIndex3() {   // Arrange   final int n = 3;   final int expected = 3;    // Act and assert   doTestCalculate(n, expected); }  @Test public void testCalculateIndex4() {   // Arrange   final int n = 4;   final int expected = 5;    // Act and assert   doTestCalculate(n, expected); }

@Test
public void testCalculate() {
  // Arrange
  final int[] expecteds = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 };

  // Act and assert
  for(int n = 0; n < expected.length; n++) {
    doTestCalculate(n, expected[n]);
  }
}

@Test public void testCalculate() {   // Arrange   final int[] expecteds = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987};    // Act and assert   for (int n = 0; n < expected.length; n++) {     doTestCalculate(n, expected[n]);   } }

@ParameterizedTest
@CsvSource(value = {"0:0", "1:1", "2:1", "3:2", "4:3", "5:5", "6:7", "7:13", "8:21"}, delimiter = ':')
public void testCalculate(final int n, final int expected) {
  doTestCalculate(n, expected);
}

@ParameterizedTest @CsvSource(value = {"0:0", "1:1", "2:1", "3:2", "4:3", "5:5", "6:7", "7:13", "8:21"}, delimiter = ':') public void testCalculate(final int n, final int expected) {   doTestCalculate(n, expected); }

@ParameterizedTest
@CsvFileSource(resources = "/fibonaccicsv", delimiter = ':', numLinesToSkip = 1)
public void testCalculate(final int n, final int expected) {
  doTestCalculate(n, expected);
}

@ParameterizedTest @CsvFileSource(resources = "/fibonaccicsv", delimiter = ':', numLinesToSkip = 1) public void testCalculate(final int n, final int expected) {   doTestCalculate(n, expected); }

@Test
public void testCalculateNegative() {
  // Arrange
  final int n = -1;

  // Act
  Assertions.assertThrows(IllegalArgumentException.class, () -> {
    fibonacci.calculate(n);
  }
}

@Test public void testCalculateNegative() {   // Arrange   final int n = -1;    // Act   Assertions.assertThrows(IllegalArgumentException.class, () -> {     fibonacci.calculate(n);   } }

@Test(expected = IllegalArgumentException.class)
public void testCalculateNegative() {
  // Arrange
  final int n = -1;

  // Act
  fibonacci.calculate(n);
}

@Test(expected = IllegalArgumentException.class) public void testCalculateNegative() {   // Arrange   final int n = -1;    // Act   fibonacci.calculate(n); }

public class RecursiveFibonacci implements Fibonacci {

  @Override
  public int calculate(int n) {
    // REGLE 1
    if(n == 0) {
      return 0;
    }

    throw new UnsupportedOperationException("bientôt");
  }

public class RecursiveFibonacci implements Fibonacci {    @Override   public int calculate(int n) {     // REGLE 1     if (n == 0) {       return 0;     }      throw new UnsupportedOperationException("bientôt");   }

@Override
public int calculate(int n) {
  // REGLE 1
  if(n == 0) {
    return 0;
  }

  if(n == 1) {
    return 1;
  }

  throw new UnsupportedOperationException("bientôt");
}

@Override public int calculate(int n) {   // REGLE 1   if (n == 0) {     return 0;   }    if (n == 1) {     return 1;   }    throw new UnsupportedOperationException("bientôt"); }

@Override
public int calculate(int n) {
  // REGLE 1
  if(n == 0 || n == 1) {
    return n;
  }

  throw new UnsupportedOperationException("bientôt");
}

@Override public int calculate(int n) {   // REGLE 1   if (n == 0 || n == 1) {     return n;   }    throw new UnsupportedOperationException("bientôt"); }

@Override
public int calculate(int n) {
  ...

  return calculate(n – 1) + calculate(n – 2);
}

@Override public int calculate(int n) {   ...    return calculate(n – 1) + calculate(n – 2); }

@Override
public int calculate(int n) {
  // REGLE 4
  if(n < 0) {
    throw new IllegalArgumentException("The parameter n can not be negative!");
  }

  ...
}

@Override public int calculate(int n) {   // REGLE 4   if (n < 0) {     throw new IllegalArgumentException("The parameter n can not be negative!");   }    ...
}

@Test
public void testCalculateVeryLong() {
  // Arrange
  final int n = 50;

  // Act
  fibonacci.calculate(n);
}

@Test public void testCalculateVeryLong() {   // Arrange   final int n = 50;    // Act   fibonacci.calculate(n); }

@Test
public void testCalculateVeryLong() {
  // Arrange
  final int n = 50;

  // Act
  // Assertions.assertTimeout(Duration.ofMillis(500), () -> ...
  Assertions.assertTimeoutPreemptively(Duration.ofMillis(500), () -> {
    fibonacci.calculate(n);
  });
}

@Test public void testCalculateVeryLong() {   // Arrange   final int n = 50;    // Act   // Assertions.assertTimeout(Duration.ofMillis(500), () -> ...   Assertions.assertTimeoutPreemptively(Duration.ofMillis(500), () -> {     fibonacci.calculate(n);   }); }

private Map<Integer, Integer> memo = new HashMap<>();

@Override
public int calculate(int n) {
  ...

  final Integer memorized = memo.get(n);
  if(memorized != null) {
    return memorized;
  }

  // REGLE 3
  final int result = calculate(n – 1) + calculate(n – 2);
  memo.put(n, result);

  return result;
}

private Map<Integer, Integer> memo = new HashMap<>();  @Override public int calculate(int n) {   ...
   final Integer memorized = memo.get(n);   if (memorized != null) {     return memorized;   }    // REGLE 3   final int result = calculate(n – 1) + calculate(n – 2);   memo.put(n, result);    return result; }

@Test
public void testCalculateBigCalue() {
  // Arrange
  final int n = 62;

  // Act
  final int result = fibonacci.calculate(n);
  System.out.println(result);
}

@Test public void testCalculateBigCalue() {   // Arrange   final int n = 62;    // Act   final int result = fibonacci.calculate(n);   System.out.println(result); }

public interface Fibonacci {

  BigInteger calculate(int n);

public interface Fibonacci {    BigInteger calculate(int n);

private void doTestCalculate(fina int n, final BigInteger expected) {
  ...
}

@ParameterizedTest
@CsvFileSource(...)
public void testCalculate(final int n, final BigInteger expected) {
  doTestCalculate(n, expected);
}

@Test
public void testCalculateBigValue() {
  // Arrange
  final int n = 62;

  // Act
  final BigInteger result = fibonacci.calculate(n);

  // Assert
  Assertions.assertTrue(0 < result.compareTo(BigInteger.ZERO));
}

private void doTestCalculate(fina int n, final BigInteger expected) {   ... }  @ParameterizedTest @CsvFileSource(...) public void testCalculate(final int n, final BigInteger expected) {   doTestCalculate(n, expected); }  @Test public void testCalculateBigValue() {   // Arrange   final int n = 62;    // Act   final BigInteger result = fibonacci.calculate(n);    // Assert   Assertions.assertTrue(0 < result.compareTo(BigInteger.ZERO)); }

private Map<Integer, BigInteger> memo = new HashMap<>();

@Override
public BigInteger calculate(int n) {
  // REGLE 4
  if(n < 0) {
    throw new IllegalArgumentException("The parameter n can not be negative!");
  }

  // REGLE 1, 2
  if(n == 0 || n == 1) {
    return BigInteger.valueOf(n);
  }

  final BigInteger memorized = memo.get(n);
  if(memorized != null) {
    return memorized;
  }

  // REGLE 3
  final BigInteger result = calculate(n – 1).add(calculate(n – 2));
  memo.put(n, result);

  return result;
}

private Map<Integer, BigInteger> memo = new HashMap<>();  @Override public BigInteger calculate(int n) {   // REGLE 4   if (n < 0) {     throw new IllegalArgumentException("The parameter n can not be negative!");   }    // REGLE 1, 2   if (n == 0 || n == 1) {     return BigInteger.valueOf(n);   }    final BigInteger memorized = memo.get(n);   if (memorized != null) {     return memorized;   }    // REGLE 3   final BigInteger result = calculate(n – 1).add(calculate(n – 2));   memo.put(n, result);    return result; }

public interface KBonacci {

  /**
   * Calcule la valeur du terme de la suite de K-Bonacci pour le rang n et la récurrence p indiqués.
   *
   * REGLE #0 f(0) = 0
   * REGLE #1 f(n) = 1 si 0 < n < p
   * REGLE #2 f(n) = f(n-1) + f(n-2) + ... + f(n-p-1) si p < n
   * REGLE #3 f(n) = Exception si n < 0 ou si p < 0
   *
   * Premiers termes pour p=3 : 0, 1, 1, 2, 4, 7, 13, 24, 44, 81...
   *
   * cf. Tribonacci https://fr.wikipedia.org/wiki/Suite_de_Tribonacci
   * @param n le rang
   * @param p la récurrence
   * @return la valeur du terme pour le rang et la récurrence indiqués
   * @throws IllegalArgumentException si le rang ou la récurrence indiqués sont négatifs
   */
  BigInteger calculate(int n, int p);

public interface KBonacci {    /**    * Calcule la valeur du terme de la suite de K-Bonacci pour le rang n et la récurrence p indiqués.    *    * REGLE #0 f(0) = 0    * REGLE #1 f(n) = 1 si 0 < n < p    * REGLE #2 f(n) = f(n-1) + f(n-2) + ... + f(n-p-1) si p < n    * REGLE #3 f(n) = Exception si n < 0 ou si p < 0    *    * Premiers termes pour p=3 : 0, 1, 1, 2, 4, 7, 13, 24, 44, 81...    *    * cf. Tribonacci https://fr.wikipedia.org/wiki/Suite_de_Tribonacci    *    * @param n le rang    * @param p la récurrence    * @return la valeur du terme pour le rang et la récurrence indiqués    * @throws IllegalArgumentException si le rang ou la récurrence indiqués sont négatifs    */   BigInteger calculate(int n, int p);

public class RecursiveKBonacci implements KBonacci {

  @Override
  public BigInteger calculate(int n, int p) {
    throw new UnsupportedOperationException("bientôt");
  }

public class RecursiveKBonacci implements KBonacci {    @Override   public BigInteger calculate(int n, int p) {     throw new UnsupportedOperationException("bientôt");   }   

public abstract class AbstractTribonacciTest {

  protected KBonacci kbonacci;
  protected int p;

  private void doTestCalculate(final int n, final BigInteger expected) {
    // Act
    final BigInteger result = kbonacci.calculate(n, p);

    // Assert
    Assertions.assertEquals(expected, result);
  }

  @parameterizedTest
  @CsvFileSource(resources = "/Tribonacci.csv", delimiter = ':', numLinesToSkip = 1)
  public void testCalculate(final int n, final BigInteger expected) {
    doTestCalculate(n, expected);
  }

public abstract class AbstractTribonacciTest {    protected KBonacci kbonacci;   protected int p;    private void doTestCalculate(final int n, final BigInteger expected) {     // Act     final BigInteger result = kbonacci.calculate(n, p);      // Assert     Assertions.assertEquals(expected, result);   }    @parameterizedTest   @CsvFileSource(resources = "/Tribonacci.csv", delimiter = ':', numLinesToSkip = 1)   public void testCalculate(final int n, final BigInteger expected) {     doTestCalculate(n, expected);   }

public class RecursiveTribonacciTest extends AbstractTribonacciTest {

  @BeforeEach
  public void before() {
    kbonacci = new RecursiveKbonacci();
    p = 3;
  }

public class RecursiveTribonacciTest extends AbstractTribonacciTest {    @BeforeEach   public void before() {     kbonacci = new RecursiveKbonacci();     p = 3;   }

public class RecursiveKBonacci implements KBonacci {

  @Override
  public BigInteger calculate(int n, int p) {
    // REGLE 0
    if(n == 0) {
      return BigInteger.ZERO;
    }

    // REGLE 1
    if(n < p) {
      return BigInteger.ONE;
    }

    throw new UnsupportedOperationException("bientôt");
  }

public class RecursiveKBonacci implements KBonacci {    @Override   public BigInteger calculate(int n, int p) {     // REGLE 0     if (n == 0) {       return BigInteger.ZERO;     }      // REGLE 1     if (n < p) {       return BigInteger.ONE;     }      throw new UnsupportedOperationException("bientôt");   }

private Map<Integer, Map<Integer, BigInteger>> memo = new HashMap<>();

private BigInteger getMemoized(final int n, final int p {
  final Map<Integer, BigInteger> map = memo.get(p);
  return map != null ? map.get(n) : null;
}

@Override
public BigInteger calculate(int n, int p) {
  // REGLE 3
  if(n < 0) {
    throw new IllegalArgumentException("...”);
  }
  if(p < 0) {
    throw new IllegalArgumentException("...”);
  }

  // REGLE 0
  if(n == 0) {
    return BigInteger.ZERO;
  }

  // REGLE 1
  if(n < p) {
    return BigInteger.ONE;
  }

  final BigInteger memorized = getMemoized(n, p);
  if(memorized != nul) {
    return memorized;
  }

  BigInteger result = BigInteger.ZERO;
  for(int i = 0; i < p; i++) {
    result = result.add(calculate(n – 1 – i, p));
  }

  memo.computeIfAbsent(p, k -> new HashMap<>())
      .put(n, result);

  return result;
}

private Map<Integer, Map<Integer, BigInteger>> memo = new HashMap<>();  private BigInteger getMemoized(final int n, final int p {   final Map<Integer, BigInteger> map = memo.get(p);   return map != null ? map.get(n) : null; }  @Override public BigInteger calculate(int n, int p) {   // REGLE 3   if (n < 0) {     throw new IllegalArgumentException("...”);   }   if (p < 0) {     throw new IllegalArgumentException("...”);   }    // REGLE 0   if (n == 0) {     return BigInteger.ZERO;   }    // REGLE 1   if (n < p) {     return BigInteger.ONE;   }    final BigInteger memorized = getMemoized(n, p);   if (memorized != nul) {     return memorized;   }    BigInteger result = BigInteger.ZERO;   for (int i = 0; i < p; i++) {     result = result.add(calculate(n – 1 – i, p));   }    memo.computeIfAbsent(p, k -> new HashMap<>())           .put(n, result);    return result; }

public class RecursiveKFibonacci
    extends RecursiveKBonacci
    implements Fibonacci, KBonacci {

  private final static int RECURRENCE = 2;

  @Override
  public BigInteger calculate(int n) {
    return calculate(n, RECURRENCE);
  }

public class RecursiveKFibonacci         extends RecursiveKBonacci         implements Fibonacci, KBonacci {    private final static int RECURRENCE = 2;    @Override   public BigInteger calculate(int n) {     return calculate(n, RECURRENCE);   }

public class RecursiveKFibonacciTest extends AbstractFibonacciTest {

  @BeforeEach
  public void before() {
    fibonacci = new RecursiveKFibonacci();
  }

public class RecursiveKFibonacciTest extends AbstractFibonacciTest {    @BeforeEach   public void before() {     fibonacci = new RecursiveKFibonacci();   }