以相反的顺序打印斐波那契数


难度级别 易得奖学金
经常问 Accenture 空气质量 o9解决方案 UHG Optum
动态编程 序列

问题陈述

给定数字n,以相反的顺序打印斐波那契数字。

使用案列

n = 5
3 2 1 1 0

说明:斐波那契数为0、1、1、2、3(按其顺序排列)。 但是由于我们需要以相反的顺序打印。

n = 7
8 5 3 2 1 1 0

以相反的顺序打印斐波那契数

该图表示斐波那契数如何取决于最后两个斐波那契数的结果。

算法

  1. 输入要打印的元素数。
  2. 声明一个大小为给定输入的数组。
  3. 使用0和1初始化第0和第1个数组索引。
  4. 我们从i = 2开始运行一个循环,直到i的值小于n,同时将i的值递增XNUMX。
    1. 继续存储最后一个索引元素和最后一个到最后一个索引元素的相加。
  5. 现在以相反的顺序打印此数组。

途径

一直以来,天真的方法来打印斐波那契数字 递归。 每当我们被告知递归时,我们通常被告知的第一件事就是斐波那契数。 因此,使用递归可以找到斐波那契数。 然后简单地以相反的顺序打印它们。 但这需要大量的计算,因此我们需要考虑一种替代方法,而不是这样做。

另一种方法是 动态编程,我们在其中存储解决问题时经常需要的数据。 我们还讨论了使用以下方法找到斐波那契数 动态编程 在以前 发表.

代码

C ++代码以相反顺序打印斐波那契数字

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;cin>>n;
    int fib[n];
    if(n>=1)
    fib[0] = 0;
    if(n>=2)
    fib[1] = 1;
    for(int i=2;i<n;i++)
        fib[i] = fib[i-1] + fib[i-2];
    for(int i=n-1;i>=0;i--)
        cout<<fib[i]<<" ";
}
4
2 1 1 0

Java代码以相反的顺序打印斐波那契数字

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int fib[] = new int[n];
    	if(n>=0)
    		fib[0] = 0;
    	if(n>=1)
    		fib[1] = 1;
    	for(int i=2;i<n;i++)
    		fib[i] = fib[i-1] + fib[i-2];
    	for(int i=n-1;i>=0;i--)
    		System.out.print(fib[i]+" ");
  	}
}
4
2 1 1 0

复杂度分析

时间复杂度

O(N),这一次需要计算斐波那契数。 因为我们只运行一个循环即可找到斐波那契数列。 时间复杂度是线性的。

空间复杂度

O(N),因为我们使用了一个数组来存储斐波那契数的值,所以空间复杂度是线性的。