计算斐波那契数(java)

前端之家收集整理的这篇文章主要介绍了计算斐波那契数(java)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

计算斐波那契数

【lintcode】366
描述
 查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指:
  前2个数是 0 和 1 。
  第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是:
  0,1,2,3,5,8,13,21,34 ...


以下是用java代码解决的几种方式实现

  1. package com.recursive;
  2. import java.text.SimpleDateFormat;
  3. import java.util.Date;
  4. import java.util.Scanner;
  5. /**
  6. * 计算斐波那契数
  7. * 数列:0 1 1 2 3 5 8 13 21 34 55 89。。。。。
  8. * 下标:0 1 2 3 4 5 6 7 8 9 10 11.。。。。
  9. * 下标:1 2 3 4 5 6 7 8 9 10 11 12
  10. * <p>
  11. * fib(0) = 0
  12. * fib(1) = 1
  13. * fib(n) = fib(n-2) + fib(n-1) n>=2
  14. */
  15. public class ComputerFibonacci {
  16. public static void main(String[] args) {
  17. int n = 44;
  18. // Scanner input = new Scanner(System.in);
  19. // System.out.println("请输入要计算的斐波那契数的下标值(从0开始):");
  20. // int n = input.nextInt();
  21. long startTime = System.currentTimeMillis();
  22. System.out.println("递归方法输入的斐波那契数的下标值: " + n + ",对应的斐波那契数为 : " + fibonacciRecursive(n));
  23. long endTime = System.currentTimeMillis();
  24. long time = endTime - startTime;
  25. System.out.println("程序运行时间:" + time / 60 + "s");
  26. long startTime2 = System.currentTimeMillis();
  27. System.out.println("迭代方法输入的斐波那契数的下标值: " + n + ",对应的斐波那契数为 : " + fibonacciIteration(n));
  28. long endTime2 = System.currentTimeMillis();
  29. long time2 = endTime2 - startTime2;
  30. System.out.println("程序运行时间:" + time2 / 60 + "s");
  31. long startTime3 = System.currentTimeMillis();
  32. System.out.println("for循环方法输入的斐波那契数的下标值: " + n + ",对应的斐波那契数为 : " + fibonacciFor(n));
  33. long endTime3 = System.currentTimeMillis();
  34. long time3 = endTime3 - startTime3;
  35. System.out.println("程序运行时间:" + time3 / 60 + "s");
  36. long startTime4 = System.currentTimeMillis();
  37. System.out.println("尾递归方法输入的斐波那契数的下标值: " + n + ",对应的斐波那契数为 : " + fibonacciRecursive2(n));
  38. long endTime4 = System.currentTimeMillis();
  39. long time4 = endTime4 - startTime4;
  40. System.out.println("程序运行时间:" + time4 / 60 + "s");
  41. }
  42. /**
  43. * 使用递归
  44. *
  45. * @param n
  46. * @return
  47. */
  48. public static int fibonacciRecursive(int n) {
  49. if (n == 1) {
  50. return 0;
  51. } else if (n == 2) {
  52. return 1;
  53. } else {
  54. return fibonacciRecursive(n - 2) + fibonacciRecursive(n - 1);
  55. }
  56. }
  57. /**
  58. * 迭代 for
  59. * @param n
  60. * @return
  61. */
  62. public static int fibonacciIteration(int n) {
  63. int f0 = 0,f1 = 1,currentFib = 0;
  64. if(n == 1) {
  65. return 0;
  66. }
  67. if (n == 2) {
  68. return 1;
  69. }
  70. for (int i = 3; i <= n; i++) {
  71. currentFib = f0 + f1;
  72. f0 = f1;
  73. f1 = currentFib;
  74. }
  75. return currentFib;
  76. }
  77. /**
  78. * for循环
  79. *
  80. * @param n
  81. * @return
  82. */
  83. public static int fibonacciFor(int n) {
  84. int a = 0;
  85. int b = 1;
  86. int c = 0;
  87. int ni = Integer.valueOf(n).toString().length();
  88. if (n == 1) {
  89. c = 0;
  90. } else if (n == 2) {
  91. c = 1;
  92. } else if (n >= 3 && ni <= 32) {
  93. for (int i = 3; i <= n; i++) {
  94. c = a + b;
  95. a = b;
  96. b = c;
  97. }
  98. }
  99. return c;
  100. }
  101. /**
  102. * 尾递归
  103. * @param n
  104. * @return
  105. */
  106. public static int fibonacciRecursive2(int n){
  107. return fib(n,1);
  108. }
  109. private static int fib(int n,int a,int b){
  110. if(n==1) {
  111. return a;
  112. }
  113. if(n==2) {
  114. return b;
  115. }
  116. return fib(n-1,b,a+b);
  117. }
  118. }

计算结果:

递归算法参考:

https://www.cnblogs.com/huan-guo/p/8489905.html

猜你在找的算法相关文章