4-A1. Fibonatti Number

正の整数を受け取り、フィボナッチ数列の番目を出力しよう。

ただし、フィボナッチ数列は とします。

入力/出力例

例1

入力

4

出力

3

例2

入力

6

出力

8

ヒント

ヒント1

をfor文で計算しよう。

ヒント2

と を持つ変数latest、second_latestを作り、ループの中で漸化式を満たすように更新していこう。

ヒント3

latestとsecond_latestを同時に更新することはできないので、一時的な変数(nextなど)を使って保持しておこう。

解答例

解答例1

クリックして展開

for文を使うことでフィボナッチ数列の番目を求めることができる。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int second_latest = 0, latest = 1;
    for (int i = 2; i <= n; i++) {
        // i番目を計算
        int next = second_latest + latest;

        // 最新の値を更新
        second_latest = latest;
        latest = next;
    }
    cout << latest << endl;
}

解答例2

クリックして展開

.push_backを用いて、フィボナッチ数列の各値を配列に格納していく方法もあります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> fibonatti_sequence = {0, 1};
    for (int i = 2; i <= n; i++) {
        // i番目を計算
        int next = fibonatti_sequence[i-1] + fibonatti_sequence[i-2];
        fibonatti_sequence.push_back(next);
    }
    cout << fibonatti_sequence.back() << endl;
}