以相反的順序打印斐波那契數


難度級別 容易獎學金
經常問 埃森哲 空氣質量 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),因為我們使用了一個數組來存儲斐波那契數的值,所以空間複雜度是線性的。