Javarecursion斐波那契数列
请解释这个代码（这很简单，但请耐心等待，因为我仍然是一个noob：P）：
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）会被调用，但是我不明白这个algorithm是如何通过这个计算索引5的值的方法。 请解释很多细节！
在斐波那契数列中，每一项都是前两项的总和。 所以，你写了一个recursionalgorithm。
所以，
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....序列0,1,1,2,3,5,8,13,21....我们可以看到， 5th element斐波那契数列返回5 。
请参阅recursion教程 。
你的代码有两个问题：
- 结果存储在int，它只能处理前48个斐波那契数，然后整数填充减一位，结果是错误的。
- 但你永远不能运行斐波纳契（50）。
代码
fibonacci(n - 1) + fibonacci(n - 2)
是非常错误的。
问题是，它叫斐波那契不是50倍，但更多。
起初它叫fibonacci（49）+ fibonacci（48），
接下来的斐波纳契（48）+斐波纳契（47）和斐波纳契（47）+斐波纳契（46）
每次它变得更糟。
非recursion代码的方法：
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，发生以下情况：
斐波纳契（4）+斐波纳契（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
鉴于fibonnacci序列是1 1 2 3 5 8 … ，第五个元素是5.您可以使用相同的方法来找出其他迭代。
recursion可能有时难以掌握。 只需要在一张小纸上评估一下：
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)
要注意的重点是这个algorithm是指数的，因为它不存储以前计算的数字的结果。 例如F（n-3）被称为3次。
有关更多详细信息，请参阅dasgupta章节0.2中的algorithm
这是我发现的最好的video，完全解释了Java中的recursion和斐波那契数列。
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; }
对于斐波那契recursion解决scheme，重要的是保存较小斐波那契数字的输出，同时检索更大数字的值。 这就是所谓的“记忆”。
这是一个代码，使用memoising较小的斐波那契数值，同时检索较大的斐波那契数。 此代码是有效的，并不会使同一function的多个请求。
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; } } }
大部分的答案都很好，解释了斐波那契recursion的工作原理。
下面是对recursion的三种技术的分析：
- For Loop
- recursion
- 记忆化
这是我的代码来testing所有三个：
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是最好的时间明智和循环匹配密切。
但recursion花费时间最长，可能是你应该避免在现实生活中。 此外，如果您使用recursion确保您优化解决scheme。
在斐波那契数列中，前两项是0和1，每一项都是前两项的和。 即：
0 1 1 2 3 5 8 …
所以第五项是第四项和第三项的总和。
Michael Goodrich等人在Java的数据结构和algorithm中提供了一个非常聪明的algorithm，用于通过返回一个[fib（n），fib（n-1）]数组来在线性时间内recursion地求解斐波纳契。
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]。
您还可以简化您的function，如下所示：
public int fibonacci(int n) { if (n < 2) return n; return fibonacci(n - 1) + fibonacci(n - 2); }
这里提供的大多数解决scheme的运行复杂度为O（2 ^ n）。 在recursion树中重新计算相同的节点是效率低下并浪费CPU周期。
我们可以使用memoization使得斐波纳契函数在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]; }
如果我们遵循自下而上的dynamic规划路线，下面的代码很简单，可以计算斐波那契数列：
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]; }
我认为这是一个简单的方法：
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（接受）的答案将正常工作，但这并不是优化的解决scheme，除非它被记住，如阿尼尔答案解释。
对于recursion考虑下面的方法， 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); } } }
为什么这个答案是不同的
其他答案都是：
- 打印而不是退货
- 每次迭代进行2次recursion调用
- 通过使用循环忽略问题
（除此之外，其中没有一个实际上是有效的;使用Binet公式直接计算第n项）
尾recursionFib
这是一个recursion方法，通过传递前一个答案和前一个答案来避免双recursion调用。
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的输出的基本序列是下一个显示当前数字的前一个数字之和的序列。
尝试观看Javarecursion斐波那契数列教程下面的链接
public static long getFibonacci(int number){ if(number<=1) return number; else return getFibonacci(number-1) + getFibonacci(number-2); }
点击这里观看Javarecursion斐波那契序列教程勺喂养
只是为了补充，如果你想能够计算更大的数字，你应该使用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; } }
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; }
斐波那契数列是一个简单的代码，显示了dynamic编程的力量。 我们从上学的日子里学到的东西就是通过迭代或最大recursion代码来运行它。 recursion代码工作正常，直到20左右，如果你给的数字比你会看到它需要大量的时间来计算。 在dynamic编程中，您可以按如下方式进行编码，计算答案需要几秒钟。
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 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; } } }
import java.util.*; /* @ Author 12CSE54 @ Date 28.10.14 */ public class cfibonacci { public void print(int p) { int a=0,b=1,c; int q[]=new int[30]; q[0]=a; q[1]=b; for(int i=2;i<p;i++) { c=a+b; q[i]=c; a=b; b=c; } System.out.println("elements are....\n"); for(int i=0;i<q.length;i++) System.out.println(q[i]); } public static void main(String ar[])throws Exception { Scanner s=new Scanner(System.in); int n; System.out.println("Enter the number of elements\n"); n=sc.nextInt(); cfibonacci c=new cfibonacci(); c.printf(n); } }
@chro是现货，但是他/她没有显示recursion地执行此操作的正确方法。 这是解决scheme：
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); } }
而不是使用一个数组，并做一些奇特的事情只是增加两个值是浪费时间，我已经find了一个有效的方式来显示/打印着名的斐波那契数列。
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; }
public long getFibonacci( int number) { if ( number <=2) { return 1; } long lRet = 0; lRet = getFibonacci( number -1) + getFibonacci( number -2); return lRet; }
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(); } }
你可以这样做。
