pg-basic text

Appearance

On this page

4-xx. Fibonatti Number ​

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

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

Hint 1

をfor文で計算しよう。

Hint 2

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

Hint 3

latestとsecond_latestを同時に更新することはできないので、一時的な変数nextも使おう。

Answer

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

cpp
#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;
}

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

cpp
#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;
}