лестница, 1 или 2 ступени за раз, ошибка рекурсии / Фибоначчи - PullRequest
Новая
       39

лестница, 1 или 2 ступени за раз, ошибка рекурсии / Фибоначчи

0 голосов
/ 03 августа 2020

Я знаю, что есть много уже существующих вопросов об этой проблеме, но я не нашел ничего, что отвечало бы на мой. Моя рекурсия отлично работает для более низких чисел (я пробовал int 10), но когда я расширяю ее до 100, она становится ровно на один шаг ниже, чем должна. Не уверен, почему.

Мой код: 

public BigDecimal distinctLadderPaths(int rungs) {
    if (rungs < 0)
      throw new ArithmeticException("Ladders can't have negative rungs."); // if negative, throw exception
    else if (rungs == 0)
      return BigDecimal.valueOf(0); //if zero, return zero
    else if (rungs <= 2)
      return BigDecimal.valueOf(rungs); //if 1 or 2, return 1 or 2, respectively
    else{
      long[] f = new long[(rungs + 1)]; //create long Array for memory (f for fibonacci)
      f[0] = 0; //1 steps
      f[1] = 1; //2 steps
      for(int i = 2; i <= rungs; i++) { //loop
        f[i] = f[i - 1] + f[i - 2]; //at each step in the loop, add 1 step lower and 2 steps lower from the number of iterations
      }
      return BigDecimal.valueOf(f[rungs]); //return fibonacci value at final step of the rungs as BigDecimal
    }
  }

тестовый код: 

@Test
  public void testDistinctLadderPaths100 (){
    int rungs = 100;
    BigDecimal expected = new BigDecimal("573147844013817084101");
    BigDecimal result = lp.distinctLadderPaths(rungs);
    assertEquals(expected, result);
  }

Мне сказали, что результат должен быть 57314784401381708410, но я получение 3736710778780434371 (число Фибоначчи на 99-м шаге). Есть идеи, почему?

Ответы [ 2 ]

4 голосов
/ 03 августа 2020

Вы используете массив long для хранения данных. Диапазон типа данных long в java равен -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. И результат сотой фабрики выходит за рамки длинного типа данных. Вот почему java округляет дополнительные данные и дает результат как 3736710778780434371. Попробуйте использовать любой другой тип данных, он будет работать нормально. В логах нет проблемы c, это проблема типа данных.

Рабочий пример может выглядеть так: 

BigInteger[] f = new BigInteger[(rungs + 1)]; //create BigInteger Array for memory (f for fibonacci)
      f[0] = BigInteger.valueOf(1); //1 steps
      f[1] = BigInteger.valueOf(1); //2 steps
      for(int i = 2; i <= rungs; i++) { //loop
        f[i] = f[i - 1].add(f[i - 2]); //at each step in the loop, add 1 step lower and 2 steps lower from the number of iterations
      }
2 голосов
/ 03 августа 2020

последовательность фибоначчи начинается с 1. Последовательность 1, 1, 2, 3, 5, 8 .. поэтому инициализируйте f [0] = f [1] = 1;

...