Java 8 Лямбда-выражения для решения фибоначчи (нерекурсивный способ)

Я начинаю использовать функцию выражения Lambda в Java 8. Лямбда-выражения довольно полезны при решении таких программ, как проверка номера, факториал и т.д.

Однако они могут эффективно использоваться при решении таких задач, как Фибоначчи, где текущее значение зависит от суммы предыдущих двух значений. Я довольно хорошо решил задачу проверки числа чисел, эффективно используя выражения Лямбда. Код для него приведен ниже.

boolean checkPrime=n>1 && LongStream.range(2, (long) Math.sqrt(n)).parallel().noneMatch(e->(n)%e==0);

В приведенном выше коде в методе noneMatch мы оцениваем текущее значение (e) в диапазоне. Но для задачи Фибоначчи нам нужны предыдущие два значения.

Как мы можем это сделать?

Ответы

Ответ 1

Простейшим решением является использование потока Pair s:

Stream.iterate(new long[]{ 1, 1 }, p->new long[]{ p[1], p[0]+p[1] })
      .limit(92).forEach(p->System.out.println(p[0]));

Из-за отсутствия стандартного типа пары он использует двухэлементный массив. Кроме того, я использую .limit(92), поскольку мы не можем оценить большее количество элементов, используя значения long. Но его легко адаптировать к BigInteger:

Stream.iterate(new BigInteger[]{ BigInteger.ONE, BigInteger.ONE },
               p->new BigInteger[]{ p[1], p[0].add(p[1]) })
      .forEach(p->System.out.println(p[0]));

Это будет работать до тех пор, пока у вас не будет достаточно памяти для представления следующего значения.

BTW, чтобы получить n-й элемент из потока:

Stream.iterate(new long[]{1, 1}, p -> new long[]{p[1], p[0] + p[1]})
    .limit(91).skip(90).findFirst().get()[1];

Ответ 2

Чтобы получить N-й элемент Фибоначчи (используя сокращение):

Stream.iterate(new long[] {1, 1}, f -> new long[] {f[1], f[0] + f[1]})
    .limit(n)
    .reduce((a, b) -> b)
    .get()[0];

Вот что происходит:

  • Stream.iterate() - создает пары чисел, каждая из которых содержит 2 последовательных элемента Фибоначчи. Мы должны использовать пары, потому что мы можем получить доступ только к последнему элементу с помощью "итерации", а не к 2 или более предыдущим элементам, поэтому для создания новой пары мы получаем последнюю пару, которая уже содержит 2 предыдущих элемента Фибоначчи, и производим следующая пара. И чтобы получить K-й элемент Фибоначчи, нам просто нужно получить левое значение из K-й пары.

  • .limit(n) - сохранить первые N пар и исключить остальные.

  • .reduce((a, b) → b) - получить последнюю пару из потока из N пар предыдущего шага.

  • .get() [0] - извлечь элемент Фибоначчи из пары (левое значение пары)

Ответ 3

решение фибоначчи (нерекурсивный способ)

Это не произойдет с вашим подходом

Генерация чисел Фибоначчи на основе предыдущих двух чисел основана на предыдущих двух числах, то есть это рекурсивный алгоритм, даже если вы реализуете его без рекурсии, но в цикле.

Существуют другие способы, основанные на показателе матрицы, поэтому вы можете вычислить n-е число фибоначчи без вычисления n-1 предыдущих чисел, но для вашей проблемы (вычисления серии) это не имеет смысла.

Итак, чтобы ответить на ваш вопрос в конце, а именно, как я могу использовать Лямбда-выражения на двух предыдущих элементах?: иметь список кортежей, каждый из которых содержит два последовательных числа, и перебирать их, добавляя новый набор для каждого шага.

Ответ 4

Если вам нужна нерекурсивная реализация, чтобы найти n-е число последовательности Фибоначчи, вы можете использовать формулу:

Un = ( (1+sqrt(5))^n - (1-sqrt(5))^n ) / (2^n * sqrt(5))

Binet's Fibonacci Number Formula

long fibonacci(int n) {
    return (long) ((Math.pow(1 + Math.sqrt(5), n) - Math.pow(1 - Math.sqrt(5), n)) /
        (Math.pow(2, n) * Math.sqrt(5)));
}

Ответ 5

Вы можете использовать переменную в своем лямбда-выражении, чтобы временно сохранить предыдущий элемент, который необходим для вычисления следующего элемента в последовательности Фибоначчи.

public class FibonacciGenerator {

        private long prev=0; 

        public void printSequence(int elements) {

            LongStream.iterate(1, n -> {n+=prev; prev=n-prev; return n;}).           
            limit(elements).forEach(System.out::println);
        }
    }

Обычно метод и поле лучше объявлять как статические, но я хотел показать, что поля экземпляра также можно использовать.

Обратите внимание, что вы не можете использовать локальную переменную (объявленную в методе или переданную методу) вместо поля, поскольку такие переменные должны быть окончательными, чтобы использовать их в лямбдах. Для нашей цели нам понадобилась изменяемая переменная для хранения различных значений во время итерации.