Пожалуйста, объясните этот простой код:
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Я смущен последней строкой, особенно потому, что если n = 5, например, будет вызываться fibonacci (4) + fibonacci (3) и так далее, но я не понимаю, как этот алгоритм вычисляет значение в индексе 5 этим метод. Пожалуйста, объясните с большим количеством деталей!
В последовательности фибоначчи каждый элемент представляет собой сумму двух предыдущих. Итак, вы написали рекурсивный алгоритм.
Итак,
fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(2) = fibonacci(1) + fibonacci(0)
Теперь вы уже знаете fibonacci(1)==1 and fibonacci(0) == 0. Таким образом, вы можете впоследствии рассчитать другие значения.
Теперь,
fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5
И из последовательности фибоначчи 0,1,1,2,3,5,8,13,21.... видно, что для 5th element последовательность фибоначчи возвращает 5.
См. здесь Учебное пособие по рекурсии.
В коде есть 2 проблемы:
fibonacci(n - 1) + fibonacci(n - 2) Подход к нерекурсивному коду:
double fibbonaci(int n){
double prev=0d, next=1d, result=0d;
for (int i = 0; i < n; i++) {
result=prev+next;
prev=next;
next=result;
}
return result;
}
В псевдокоде, где n = 5, имеет место следующее:
fibonacci (4) + fibonnacci (3)
Это разбивается на:
(fibonacci (3) + fibonnacci (2)) + (fibonacci (2) + fibonnacci (1))
Это разбивается на:
(((fibonacci (2) + fibonnacci (1)) + ((fibonacci (1) + fibonnacci (0))) + (((fibonacci (1) + fibonnacci (0)) + 1))
Это разбивается на:
((((fibonacci (1) + fibonnacci (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))
Это разбивается на:
(((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))
В результате получается: 5
Учитывая, что последовательность фибоначчи 1 1 2 3 5 8..., 5-й элемент равен 5. Вы можете использовать ту же методологию для определения других итераций.
Иногда рекурсия может быть затруднена. Просто оцените его на листе бумаги для небольшого числа:
fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3
Я не уверен, как Java действительно оценивает это, но результат будет таким же.
Вы также можете упростить свою функцию следующим образом:
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
F(n)
/ \
F(n-1) F(n-2)
/ \ / \
F(n-2) F(n-3) F(n-3) F(n-4)
/ \
F(n-3) F(n-4)
Важно отметить, что этот алгоритм является экспоненциальным, поскольку он не сохраняет результат предыдущих расчетных чисел. например, F (n-3) называется 3 раза.
Подробнее см. алгоритм по главе dasgupta 0.2
Большинство ответов хороши и объясняет, как работает рекурсия в Fibonacci.
Ниже приведен анализ трех методов, которые включают рекурсию:
Вот мой код для тестирования всех трех:
public class Fibonnaci {
// Output = 0 1 1 2 3 5 8 13
static int fibMemo[];
public static void main(String args[]) {
int num = 20;
System.out.println("By For Loop");
Long startTimeForLoop = System.nanoTime();
// returns the fib series
int fibSeries[] = fib(num);
for (int i = 0; i < fibSeries.length; i++) {
System.out.print(" " + fibSeries[i] + " ");
}
Long stopTimeForLoop = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));
System.out.println("By Using Recursion");
Long startTimeRecursion = System.nanoTime();
// uses recursion
int fibSeriesRec[] = fibByRec(num);
for (int i = 0; i < fibSeriesRec.length; i++) {
System.out.print(" " + fibSeriesRec[i] + " ");
}
Long stopTimeRecursion = System.nanoTime();
System.out.println("");
System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));
System.out.println("By Using Memoization Technique");
Long startTimeMemo = System.nanoTime();
// uses memoization
fibMemo = new int[num];
fibByRecMemo(num-1);
for (int i = 0; i < fibMemo.length; i++) {
System.out.print(" " + fibMemo[i] + " ");
}
Long stopTimeMemo = System.nanoTime();
System.out.println("");
System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
}
//fib by memoization
public static int fibByRecMemo(int num){
if(num == 0){
fibMemo[0] = 0;
return 0;
}
if(num ==1 || num ==2){
fibMemo[num] = 1;
return 1;
}
if(fibMemo[num] == 0){
fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
return fibMemo[num];
}else{
return fibMemo[num];
}
}
public static int[] fibByRec(int num) {
int fib[] = new int[num];
for (int i = 0; i < num; i++) {
fib[i] = fibRec(i);
}
return fib;
}
public static int fibRec(int num) {
if (num == 0) {
return 0;
} else if (num == 1 || num == 2) {
return 1;
} else {
return fibRec(num - 1) + fibRec(num - 2);
}
}
public static int[] fib(int num) {
int fibSum[] = new int[num];
for (int i = 0; i < num; i++) {
if (i == 0) {
fibSum[i] = i;
continue;
}
if (i == 1 || i == 2) {
fibSum[i] = 1;
continue;
}
fibSum[i] = fibSum[i - 1] + fibSum[i - 2];
}
return fibSum;
}
}
Вот результаты:
By For Loop
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
For Loop Time:347688
By Using Recursion
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Recursion Time:767004
By Using Memoization Technique
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Memoization Time:327031
Следовательно, мы можем видеть, что memoization является наилучшим временем и близко подходит для совпадений циклов.
Но рекурсия занимает самое длинное, и, возможно, вам следует избегать в реальной жизни. Также, если вы используете рекурсию, убедитесь, что вы оптимизировали решение.
Это лучшее видео, которое я нашел, что полностью объясняет рекурсию и последовательность Фибоначчи в Java.
http://www.youtube.com/watch?v=dsmBRUCzS7k
Это его код для последовательности, и его объяснение лучше, чем я мог когда-либо пытаться ввести его.
public static void main(String[] args)
{
int index = 0;
while (true)
{
System.out.println(fibonacci(index));
index++;
}
}
public static long fibonacci (int i)
{
if (i == 0) return 0;
if (i<= 2) return 1;
long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
return fibTerm;
}
Для решения рекурсивного решения фибоначчи важно сохранить вывод меньших чисел фибоначчи, получая значение большего числа. Это называется "Memoizing".
Вот код, который использует memoizing меньшие значения фибоначчи, в то время как получение большего числа фибоначчи. Этот код эффективен и не выполняет несколько запросов одной и той же функции.
import java.util.HashMap;
public class Fibonacci {
private HashMap<Integer, Integer> map;
public Fibonacci() {
map = new HashMap<>();
}
public int findFibonacciValue(int number) {
if (number == 0 || number == 1) {
return number;
}
else if (map.containsKey(number)) {
return map.get(number);
}
else {
int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}
Майкл Гудрич и др. обеспечивают действительно умный алгоритм в структурах данных и алгоритмах в Java, для рекурсивного решения линейного времени фибоначчи, возвращая массив из [fib (n), fib (n-1)].
public static long[] fibGood(int n) {
if (n < = 1) {
long[] answer = {n,0};
return answer;
} else {
long[] tmp = fibGood(n-1);
long[] answer = {tmp[0] + tmp[1], tmp[0]};
return answer;
}
}
Это дает fib (n) = fibGood (n) [0].
в последовательности fibonacci, первые два элемента - 0 и 1, каждый другой элемент - сумма двух предыдущих элементов. то есть:
0 1 1 2 3 5 8...
так что 5-й элемент - это сумма 4-го и 3-го пунктов.
Последовательность Fibbonacci - это сумма, которая суммирует результат числа при добавлении к предыдущему результату, начиная с 1.
so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
Как только мы поймем, что такое Fibbonacci, мы можем начать разбивать код.
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Первое, если состояние проверяет базовый регистр, где цикл может вырваться. Нижеприведенный оператор else if делает то же самое, но его можно переписать так...
public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Теперь, когда базовый случай установлен, мы должны понимать стек вызовов. Ваш первый вызов "фибоначчи" будет последним для решения в стеке (последовательность вызовов), поскольку они разрешают в обратном порядке, из которого они были называется. Последний метод называется разрешимым первым, затем последним, который нужно вызвать до этого и т.д....
Итак, все вызовы выполняются первыми, прежде чем что-либо "рассчитано" с этими результатами. При вводе 8 мы ожидаем выход 21 (см. Таблицу выше).
Фибоначчи (n - 1) продолжает вызываться до тех пор, пока не достигнет базового случая, тогда фибоначчи (n - 2) вызывается до тех пор, пока не достигнет базового варианта. Когда стек начинает суммировать результат в обратном порядке, результат будет таким же...
1 + 1 = 1 ---- last call of the stack (hits a base case).
2 + 1 = 3 ---- Next level of the stack (resolving backwards).
2 + 3 = 5 ---- Next level of the stack (continuing to resolve).
Они продолжают пузыряться (отступать назад) до тех пор, пока правильная сумма не возвращается к первому вызову в стеке и что вы получите ответ.
Сказав это, этот алгоритм очень неэффективен, потому что он вычисляет один и тот же результат для каждой ветки, в которую разбивается код. Гораздо лучший подход - это "снизу вверх", где не требуется Memoization (кэширование) или рекурсия (глубокий стек вызовов).
Так же...
static int BottomUpFib(int current)
{
if (current < 2) return current;
int fib = 1;
int last = 1;
for (int i = 2; i < current; i++)
{
int temp = fib;
fib += last;
last = temp;
}
return fib;
}
Большинство предлагаемых здесь решений работают в сложности O (2 ^ n). Пересчет идентичных узлов в рекурсивном дереве неэффективен и отнимает процессорные циклы.
Мы можем использовать memoization, чтобы функция fibonacci выполнялась в O (n) времени
public static int fibonacci(int n) {
return fibonacci(n, new int[n + 1]);
}
public static int fibonacci(int i, int[] memo) {
if (i == 0 || i == 1) {
return i;
}
if (memo[i] == 0) {
memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
}
return memo[i];
}
Если следовать алгоритму динамического программирования Bottom-Up, ниже код достаточно прост для вычисления фибоначчи:
public static int fibonacci1(int n) {
if (n == 0) {
return n;
} else if (n == 1) {
return n;
}
final int[] memo = new int[n];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i < n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n - 1] + memo[n - 2];
}
Каждый другой ответ:
(в сторону: ни одно из них фактически не эффективно, используйте формулу Binet, чтобы непосредственно рассчитать термин n th)
Вот рекурсивный подход, который позволяет избежать двойного рекурсивного вызова, передавая как предыдущий ответ, так и предыдущий.
private static final int FIB_0 = 0;
private static final int FIB_1 = 1;
private int calcFibonacci(final int target) {
if (target == 0) { return FIB_0; }
if (target == 1) { return FIB_1; }
return calcFibonacci(target, 1, FIB_1, FIB_0);
}
private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
final int current = previous + 1;
final int fibCurrent = fibPrevious + fibPreviousMinusOne;
// If you want, print here / memoize for future calls
if (target == current) { return fibCurrent; }
return calcFibonacci(target, current, fibCurrent, fibPrevious);
}
Это базовая последовательность, отображающая или получающая 1 1 2 3 5 8 это последовательность, в которой сумма предыдущего номера будет отображаться в текущем номере.
Попробуйте посмотреть ссылку ниже Учебник по последовательности рекурсивных фибоначчи Java
public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}
Нажмите здесь Посмотрите Java-рекурсивный учебник по последовательности фибоначчи для кормления ложкой
Я думаю, что это простой способ:
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
long a = 0;
long b = 1;
for(int i = 1; i<number;i++){
long c = a +b;
a=b;
b=c;
System.out.println(c);
}
}
}
Ответ RanRag (принятый) будет работать нормально, но это не оптимизированное решение до тех пор, пока оно не запомнится, как объяснено в ответе Анила.
Для рекурсивного подхода ниже подход, вызовы метода TestFibonacci минимальны
public class TestFibonacci {
public static void main(String[] args) {
int n = 10;
if (n == 1) {
System.out.println(1);
} else if (n == 2) {
System.out.println(1);
System.out.println(1);
} else {
System.out.println(1);
System.out.println(1);
int currentNo = 3;
calFibRec(n, 1, 1, currentNo);
}
}
public static void calFibRec(int n, int secondLast, int last,
int currentNo) {
if (currentNo <= n) {
int sum = secondLast + last;
System.out.println(sum);
calFibRec(n, last, sum, ++currentNo);
}
}
}
Используя внутреннюю ConcurrentHashMap, которая теоретически может позволить этой рекурсивной реализации корректно работать в многопоточной среде, я реализовал функцию fib, которая использует как BigInteger, так и Recursion. Принимает около 53 мс для расчета первых 100 номеров фиб.
private final Map<BigInteger,BigInteger> cacheBig
= new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
return a;
}
public BigInteger fibBigCache(BigInteger n) {
if ( n.compareTo(BigInteger.ONE ) <= 0 ){
return n;
} else if (cacheBig.containsKey(n)){
return cacheBig.get(n);
} else {
return
fibBigCache(n.subtract(BigInteger.ONE))
.add(fibBigCache(n.subtract(TWO)));
}
}
Код проверки:
@Test
public void testFibRecursiveBigIntegerCache() {
long start = System.currentTimeMillis();
FibonacciSeries fib = new FibonacciSeries();
IntStream.rangeClosed(0,100).forEach(p -&R {
BigInteger n = BigInteger.valueOf(p);
n = fib.fibRecursiveBigCache(n);
System.out.println(String.format("fib of %d is %d", p,n));
});
long end = System.currentTimeMillis();
System.out.println("elapsed:" +
(end - start) + "," +
((end - start)/1000));
}
and output from the test is:
.
.
.
.
.
fib of 93 is 12200160415121876738
fib of 94 is 19740274219868223167
fib of 95 is 31940434634990099905
fib of 96 is 51680708854858323072
fib of 97 is 83621143489848422977
fib of 98 is 135301852344706746049
fib of 99 is 218922995834555169026
fib of 100 is 354224848179261915075
elapsed:58,0
Вот одна строка febonacci рекурсивная:
public long fib( long n ) {
return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}
Просто чтобы дополнить, если вы хотите иметь возможность вычислять большие числа, вы должны использовать BigInteger.
Итеративный пример.
import java.math.BigInteger;
class Fibonacci{
public static void main(String args[]){
int n=10000;
BigInteger[] vec = new BigInteger[n];
vec[0]=BigInteger.ZERO;
vec[1]=BigInteger.ONE;
// calculating
for(int i = 2 ; i<n ; i++){
vec[i]=vec[i-1].add(vec[i-2]);
}
// printing
for(int i = vec.length-1 ; i>=0 ; i--){
System.out.println(vec[i]);
System.out.println("");
}
}
}
http://en.wikipedia.org/wiki/Fibonacci_number более подробно
public class Fibonacci {
public static long fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
for (int i = 1; i <= N; i++)
System.out.println(i + ": " + fib(i));
}
}
Сделайте так, чтобы при необходимости не нужно было использовать цикл while и другой цикл
public class febo
{
public static void main(String...a)
{
int x[]=new int[15];
x[0]=0;
x[1]=1;
for(int i=2;i<x.length;i++)
{
x[i]=x[i-1]+x[i-2];
}
for(int i=0;i<x.length;i++)
{
System.out.println(x[i]);
}
}
}
public class FibonacciSeries {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i <= N; i++) {
int result = fibonacciSeries(i);
System.out.println(result);
}
scanner.close();
}
private static int fibonacciSeries(int n) {
if (n < 0) {
return 1;
} else if (n > 0) {
return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
}
return 0;
}
}
Использовать while:
public int fib(int index) {
int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
while (tmp < index - 1) {
fibNumber = step1 + step2;
step1 = step2;
step2 = fibNumber;
tmp += 1;
};
return fibNumber;
}
Преимущество этого решения в том, что он легко читает код и понимает его, надеясь, что он поможет
Последовательность Fibbonacci - это сумма, которая суммирует результат числа, который мы добавили к предыдущему результату, мы должны начать с 1. Я пытался найти решение на основе алгоритма, поэтому я создаю рекурсивный код, заметив, что я сохраняю предыдущее число и я изменили позицию. Я ищу последовательность Фибоначчи от 1 до 15.
public static void main(String args[]) {
numbers(1,1,15);
}
public static int numbers(int a, int temp, int target)
{
if(target <= a)
{
return a;
}
System.out.print(a + " ");
a = temp + a;
return numbers(temp,a,target);
}
Попробуй это
private static int fibonacci(int n){
if(n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Для получения дополнительной информации ознакомьтесь с этим выходом серии Фибоначчи на Java - Посредственный код
Вот решение O (1):
private static long fibonacci(int n) {
double pha = pow(1 + sqrt(5), n);
double phb = pow(1 - sqrt(5), n);
double div = pow(2, n) * sqrt(5);
return (long) ((pha - phb) / div);
}
Формула числа Бинета Фибоначчи используется для приведенной выше реализации. Для больших входов long можно заменить на BigDecimal.
Серия Fibonacci - это один простой код, который показывает мощность динамического программирования. Все, что мы узнали из школьных дней, это запустить его с помощью итеративного или макс рекурсивного кода. Рекурсивный код работает нормально до 20 или около того, если вы укажете числа, большие, чем вы увидите, для вычисления требуется много времени. В динамическом программировании вы можете кодировать следующим образом, и для вычисления ответа требуется secs.
static double fib(int n) {
if (n < 2)
return n;
if (fib[n] != 0)
return fib[n];
fib[n] = fib(n - 1) + fib(n - 2);
return fib[n];
}
Вы сохраняете значения в массиве и переходите к новым вычислениям только тогда, когда массив не может предоставить вам ответ.
public static long fib(int n) {
long population = 0;
if ((n == 0) || (n == 1)) // base cases
{
return n;
} else // recursion step
{
population+=fib(n - 1) + fib(n - 2);
}
return population;
}
Простой Фибоначчи
public static void main(String[]args){
int i = 0;
int u = 1;
while(i<100){
System.out.println(i);
i = u+i;
System.out.println(u);
u = u+i;
}
}
}