Пожалуйста, объясните этот простой код:
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 этим метод. Пожалуйста, объясните подробно!
В последовательности Фибоначчи каждый элемент представляет собой сумму двух предыдущих. Итак, вы написали рекурсивный алгоритм.
So,
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;
}
2*fibonacci(n+1)-1, поэтому оно растет с той же сложностью, что и сами числа Фибоначчи, что составляет 1,618 ^ n вместо 2 ^ n.
- person Aemyl; 11.12.2017
В псевдокоде, где n = 5, имеет место следующее:
фибоначчи (4) + фибоначчи (3)
Это разбивается на:
(фибоначчи (3) + фибонначчи (2)) + (фибоначчи (2) + фибонначчи (1))
Это разбивается на:
(((фибоначчи (2) + фибоначчи (1)) + ((фибоначчи (1) + фибоначчи (0))) + (((фибоначчи (1) + фибоначчи (0)) + 1))
Это разбивается на:
((((фибоначчи (1) + фибоначчи (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))
Это разбивается на:
((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))
В результате получается: 5
Учитывая, что последовательность Фибонначчи равна 1 1 2 3 5 8 ..., 5-й элемент равен 5. Вы можете использовать ту же методологию для определения других итераций.
Вы также можете упростить свою функцию следующим образом:
public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Иногда бывает трудно понять рекурсию. Просто оцените это на листе бумаги за небольшое количество:
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 на самом деле это оценивает, но результат будет таким же.
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.
Большинство ответов хороши и объясняют, как работает рекурсия в фибоначчи.
Вот анализ трех техник, который также включает в себя рекурсию:
Вот мой код для проверки всех трех:
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
Следовательно, мы можем видеть, что мемоизация - лучший вариант времени, и цикл for точно соответствует.
Но рекурсия занимает больше всего времени, и, возможно, вам следует избегать ее в реальной жизни. Также, если вы используете рекурсию, убедитесь, что вы оптимизируете решение.
Это лучшее видео, которое я нашел, которое полностью объясняет рекурсию и последовательность Фибоначчи в 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;
}
Для рекурсивного решения Фибоначчи важно сохранять вывод меньших чисел Фибоначчи, извлекая при этом значение большего числа. Это называется «мемоизирование».
Вот код, который использует запоминание меньших значений Фибоначчи при извлечении большего числа Фибоначчи. Этот код эффективен и не выполняет несколько запросов одной и той же функции.
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;
}
}
}
в последовательности fibonacci первые два элемента равны 0 и 1, каждый другой элемент представляет собой сумму два предыдущих пункта. то есть:
0 1 1 2 3 5 8 ...
поэтому 5-й элемент - это сумма 4-го и 3-го элементов.
Майкл Гудрич и др. Предлагают действительно умный алгоритм в структурах данных и алгоритмах в 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].
Вот решение 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.
Последовательность Фиббоначи - это последовательность, которая суммирует результат числа, добавленного к предыдущему результату, начиная с 1.
so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
Как только мы поймем, что такое Фиббоначи, мы сможем начать разбирать код.
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
Первое условие if проверяет базовый случай, при котором цикл может разорваться. Приведенный ниже оператор else if делает то же самое, но его можно переписать так ...
public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Теперь, когда установлен базовый вариант, мы должны понять стек вызовов. Ваш первый вызов "fibonacci" будет последним, который будет разрешен в стеке (последовательность вызовов), поскольку они разрешаются в порядке, обратном тому, из которого они были вызваны. Сначала разрешается последний вызванный метод, затем последний вызывается перед этим и так далее ...
Итак, все вызовы выполняются в первую очередь до того, как что-либо будет «рассчитано» с этими результатами. При вводе 8 мы ожидаем на выходе 21 (см. Таблицу выше).
fibonacci (n - 1) продолжает вызываться, пока не достигнет базового случая, затем вызывается fibonacci (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).
Они продолжают пузыриться (разрешаются в обратном направлении) до тех пор, пока правильная сумма не будет возвращена первому вызову в стеке, и именно так вы получите свой ответ.
Сказав это, этот алгоритм очень неэффективен, потому что он вычисляет один и тот же результат для каждой ветви, на которую разбивается код. Намного лучший подход - это подход «снизу вверх», когда не требуется мемоизация (кеширование) или рекурсия (глубокий стек вызовов).
Вот так...
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). Пересчет идентичных узлов в рекурсивном дереве неэффективен и расходует циклы ЦП.
Мы можем использовать мемоизацию, чтобы функция Фибоначчи запускалась за время 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];
}
Если мы будем следовать маршруту динамического программирования снизу-вверх, приведенный ниже код будет достаточно простым, чтобы вычислить фибоначчи:
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];
}
Любой другой ответ тоже:
(кроме того: ни один из них на самом деле не эффективен; используйте формула Бине для прямого вычисления 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 Recursive Fibonacci sequence Tutorial.
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 (принятый) будет работать нормально, но это не оптимизированное решение до тех пор, пока оно не будет запомнено, как описано в ответе Anil.
Для рекурсивного подхода, рассмотренного ниже, вызовы метода 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. На вычисление первых 100 чисел Фиби уходит около 53 мсек.
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
Вот рекурсивная однострочная фебоначчи:
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 и других циклов
Используйте 1_:
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;
}
Преимущество этого решения в том, что код легко читать и понимать, надеясь, что это поможет.
Последовательность Фиббоначи - это последовательность, которая суммирует результат числа, которое мы добавили к предыдущему результату, мы должны начать с 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);
}
Простой Фибоначчи
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;
}
}
}
@chro на высоте, но он / она не показывает правильный способ сделать это рекурсивно. Вот решение:
class Fib {
static int count;
public static void main(String[] args) {
log(fibWrong(20)); // 6765
log("Count: " + count); // 21891
count = 0;
log(fibRight(20)); // 6765
log("Count: " + count); // 19
}
static long fibRight(long n) {
return calcFib(n-2, 1, 1);
}
static long fibWrong(long n) {
count++;
if (n == 0 || n == 1) {
return n;
} else if (n < 0) {
log("Overflow!");
System.exit(1);
return n;
} else {
return fibWrong(n-1) + fibWrong(n-2);
}
}
static long calcFib(long nth, long prev, long next) {
count++;
if (nth-- == 0)
return next;
if (prev+next < 0) {
log("Overflow with " + (nth+1)
+ " combinations remaining");
System.exit(1);
}
return calcFib(nth, next, prev+next);
}
static void log(Object o) {
System.out.println(o);
}
}
Ряд Фибоначчи - это простой код, демонстрирующий мощь динамического программирования. Все, что мы узнали в школьные годы, - это запускать его с помощью итеративного или максимально рекурсивного кода. Рекурсивный код работает нормально до 20 или около того, если вы дадите числа больше, чем это, вы увидите, что для вычисления требуется много времени. В динамическом программировании вы можете кодировать следующим образом, и вычисление ответа занимает секунды.
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 class Fibonaci{
static void fibonacci() {
int ptr1 = 1, ptr2 = 1, ptr3 = 0;
int temp = 0;
BufferedReader Data=new BufferedReader (new InputStreamReader(System.in));
try {
System.out.println("The Number Value's fib you required ? ");
ptr3 = Integer.parseInt(Data.readLine());
System.out.print(ptr1 + " " + ptr2 + " ");
for (int i = 0; i < ptr3; i++) {
System.out.print(ptr1 + ptr2 + " ");
temp = ptr1;
ptr1 = ptr2;
ptr2 = temp + ptr2;
}
} catch(IOException err) {
System.out.println("Error!" + err);
} catch(NumberFormatException err) {
System.out.println("Invald Input!");
}
}
public static void main(String[]args)throws Exception{
Fibonaci.fibonacci();
}
}
Вы можете это сделать.
Вместо того, чтобы использовать массив и делать какие-то причудливые вещи, просто два и два значения - пустая трата времени, я нашел эффективный способ отображения / печати знаменитой последовательности Фибоначчи.
public static void main(String args[]){
System.out.println("This program lists the Fibonacci sequence.");
int answer = 0;
int startValue = 1;
int sum = 0;
while (answer < 10000){
System.out.println(answer);
sum = add(answer,startValue);
startValue = answer;
answer = sum;
}
}
//This method return the sum of addition
private static int add(int A,int B){
return A+B;
}
Да, важно запоминать вычисленное возвращаемое значение из каждого вызова метода рекурсии, чтобы вы могли отображать серию в вызывающем методе.
В предоставленной реализации есть некоторые уточнения. Пожалуйста, найдите ниже реализацию, которая дает нам более правильный и универсальный вывод:
import java.util.HashMap;
import java.util.stream.Collectors;
public class Fibonacci {
private static HashMap<Long, Long> map;
public static void main(String[] args) {
long n = 50;
map = new HashMap<>();
findFibonacciValue(n);
System.out.println(map.values().stream().collect(Collectors.toList()));
}
public static long findFibonacciValue(long number) {
if (number <= 1) {
if (number == 0) {
map.put(number, 0L);
return 0L;
}
map.put(number, 1L);
return 1L;
} else if (map.containsKey(number)) {
return map.get(number);
} else {
long fibonacciValue = findFibonacciValue(number - 1L) + findFibonacciValue(number - 2L);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}
Вывод для числа 50:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]
