TamedFox 2019-08-05 13:04 采纳率: 100%
浏览 506
已采纳

fibonacci算法使用数组实现

为什么要使用数组,数组在每次调用方法递归时都会重新实例化一个新的数组,数组中元素也是默认的,那么递归条件
数组的意义在哪里,以及fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];这条语句的作用是什么,
为什么要返回一个数组而不是直接返回一个递归结束的结果数值呢?

public class Fibonacci {
    public static long[] F(int N) {
        long[] fibonacci = new long[N + 1];
        if (N == 0) {
            return fibonacci;
        }
        fibonacci[1] = 1;
        if (N == 1) {
            return fibonacci;
        }
        for (int i = 2; i <= N; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }
        return fibonacci;
    }

    public static void main(String[] args) {
        long[] fibonacci = F(99);
        for (int N = 0; N < fibonacci.length; N++) {
            StdOut.println(N + " " + fibonacci[N]);
        }
    }
}
  • 写回答

1条回答 默认 最新

  • CCCCCCCYYY_ 2019-08-05 13:53
    关注

    上面的fibonacci的实现是dynamic programming动态规划算法,并不是递归实现的。
    下面这个才是递归实现的fibonacci

    long int Fibonacci_0( unsigned int n)
    {
        if(n<=2)
         return 1;
         else
         return Fibonacci_0(n-1) + Fibonacci_0(n-2);
    };
    

    这个递归算法就是直接返回值,而动态规划算法简单来说就是把之前求出来的值记录下来保存在数组中,在计算下个值需要用到已知值的时候拿出来,而不是重新计算

    所以动态规划可以节省非常多的计算时间
    比如:
    1. 递归计算fibonacci(4) = fibonacci(3) + fibonacci(2);
    1. 先计算前面的fibonacci(3);
    1. 接下来要计算fibonacci(3) = fibonacci(2) + fibonacci(1);
    1. 然后是fibonacci(2) = fibonacci(1) + fibonacci(0);
    1. 再计算后面的fibonacci(2);
    1. fibonacci(2) = fibonacci(1) + fibonacci(0);

    可以发现里面的重复计算非常多,数字越大所花的开销和重复计算的次数越多。
    在此基础上,动态规划用数组保存了之前计算过的值:如你提出的:

    • fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 gki vendor hook
  • ¥15 centos7中sudo命令无法使用
  • ¥15 灰狼算法和蚁群算法如何结合
  • ¥15 这是一个利用ESP32自带按键和LED控制的录像代码,编译过程出现问题,请解决并且指出错误,指导如何处理 ,协助完成代码并上传代码
  • ¥20 stm32f103,hal库 hal_usart_receive函数接收不到数据。
  • ¥20 求结果和代码,sas利用OPTEX程序和D-efficiency生成正交集
  • ¥50 adb连接不到手机是怎么回事?
  • ¥20 抓取数据时发生错误: get_mooncake_data() missing 1 required positional argument: 'driver'的问题,怎么改出正确的爬虫代码?
  • ¥15 vs2022无法联网
  • ¥15 TCP的客户端和服务器的互联