2つの変数を使用してフィボナッチ数列を出力します


難易度 簡単に
よく聞かれる Amazon (アマゾン) デリーベリー ファクトセット フォーカイテス ハイキング MAQ o9ソリューション PayU
動的計画法 フィボナッチ シーケンス

問題文

「2つの変数を使用してフィボナッチ数列を印刷する」という問題は、フィボナッチ数列を印刷する必要があると述べていますが、2つの変数のみを使用するという制限があります。

2つの変数を使用してフィボナッチ数列を出力します

n = 5
0 1 1 2 3 5

説明

出力シーケンスには、フィボナッチ数列の最初のXNUMXつの要素が含まれています。

アプローチ

入力として単一の要素が提供されます。これは、フィボナッチ数列から生成する必要のある要素の数を示します。 したがって、フィボナッチ数列を印刷するための素朴なアプローチは 再帰。 次に、再帰関数を呼び出すループを使用して、各フィボナッチ数を計算できます。 しかし、このアプローチには指数関数的な時間が必要であるため、より効率的なものが必要です。

私たちは考えることができます 動的計画法/問題のメモ化。 このアプローチにより、時間の複雑さが確実に軽減されます。 指数関数的な時間計算量は、線形時間計算量に削減されます。 しかし、このアプローチでは、線形空間の複雑さが必要です。 このスペースの複雑さをさらに減らす必要があります。 私たちにできることは、最適化を試みることです 動的計画法 アプローチで回避できます。

再帰式を見ると、F(n)= F(n-1)+ F(n-2)です。 私たちは最後の1つのフィボナッチ数にのみ依存しています。 したがって、現在の数を見つけるために最後のXNUMXつのフィボナッチ数のみを格納できます。これにより、アルゴリズムはO(XNUMX)空間の複雑さで実行されます。

コード

2つの変数を使用してフィボナッチ数列を出力するC ++コード

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

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

2つの変数を使用してフィボナッチ数列を出力するJavaコード

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

複雑さの分析

時間の複雑さ

オン)、 印刷する必要のある要素の数までしかトラバースしていないためです。 最初に、再帰を使用して問題を解決することを考えましたが、それは時間的に指数関数的でした。 次に、使用したときに時間の複雑さを軽減しました 動的計画法。 そのため、線形時間で問題を解決することができました。

スペースの複雑さ

O(1)、  XNUMXつの変数のみを使用したため、一定のスペースの複雑さの問題を解決しました。