「K ボナッチ数列」を解くために:part1 フィボナッチ数列

今回は paiza の「「K ボナッチ数列」を解くために:part1」の問題に挑戦！

問題概要

• このステップでは、一般的なフィボナッチ数列を扱う
• フィボナッチ数列は次の規則で定義される数列である
  • 1 項目 = 1
  • 2 項目 = 1
  • 3 項目以降 = 直前の 2 項の和
• 数列の例
  • 1, 1, 2, 3, 5, 8, ...

求めるもの

• フィボナッチ数列の N 項目の値を求める
• ただし、その値を 10000 で割ったあまりを出力する

入力

• 入力は 1 行
• 与えられるのは整数 N
  • N はフィボナッチ数列の項番号

出力

• フィボナッチ数列の N 項目を 10000 で割ったあまり を1行で出力する

条件

• 1 ≤ N ≤ 1000

入力例:

5

出力例:

5

❌NG例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const N = Number(lines[0]);
    const MOD = 10000;
    
    // FB[i] = フィボナッチ数列の i 項目
    // FB[0] には適当な値を入れておく
    const FB = [0, 1, 1]; 
    
    for (let i = 3; i <= N; i++) {
        FB[i] = FB[i-1] + FB[i-2];
    }
    
    console.log(FB[N] % MOD);
});

問題点①：数が巨大になる

フィボナッチ数列は指数的に増える。

• FB[1000] は 200桁以上
• JavaScript の Number は 正確に扱えるのは 2^53 – 1 まで

👉 途中で 桁落ち・誤差 が発生する。

問題点②：最後に % MOD しても遅い

数学的には

(a + b) % MOD === ((a % MOD) + (b % MOD)) % MOD

が成り立つので、

• 毎回 mod を取る
• 最後だけ mod を取る

は理論上同じだけど、
プログラム上は数値の限界があるので同じにならない。

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const N = Number(lines[0]);
    const MOD = 10000;
    
    // FB[i] = フィボナッチ数列の i 項目
    // FB[0] には適当な値を入れておく
    const FB = [0, 1, 1]; 
    
    for (let i = 3; i <= N; i++) {
        FB[i] = (FB[i-1] + FB[i-2]) % MOD;
    }
    
    console.log(FB[N]);
});

ポイント

• 毎回 mod を取る
• 常に 0 ～ 9999 の範囲に収まる
• 数値が大きくならない
• JS の Number でも安全

👉 オーバーフローも精度問題も起きない

📝まとめ

❌「最後に % MOD すればいい」
✅「途中計算もすべて % MOD する」

フィボナッチ数列

フィボナッチ数列とは：
最初の 2 項を 1 とし、3 項目以降は直前の 2 項の和で定まる数列

数式で書くと：

• F(1) = 1
• F(2) = 1
• F(n) = F(n−1) + F(n−2)（n ≥ 3）

実際に並べると：
1, 1, 2, 3, 5, 8, 13, 21, 34, ...