今回は paiza のDPで「【漸化式】 3項間漸化式 2」に挑戦！
漸化式の問題はこれで最後！
ちなみに漸化式とは、数列の各項が、それ以前の項の値を使って表される関係式のこと。つまり、ある項の値が分かれば、それを使って次の項の値を計算できる、という規則を表す式である！
問題概要
🔸 問題の目的
「数列の中で、指定された項の値を求めて出力」する。
🔢 数列 a_n は以下のように定義される：
a_1 = 1
a_2 = 1
a_n = a_{n-1} + a_{n-2} （n ≥ 3）
つまり、3項目以降は「前の2つを足す」ことで作られる数列。
例）1, 1, 2, 3, 5, 8, 13, 21, …
📥 入力形式
Q ← クエリの数（出力したい項の個数）
k_1 ← 出力したいフィボナッチ数列の項番号（1〜40）
k_2
...
k_Q
※ Q 行ぶんの k_i が与えられる
📤 出力形式
- 各 k_i に対応する a_{k_i} を 1行ずつ 出力
- 余計な文字や空行は禁止
※条件
- 1 ≦ Q ≦ 100（クエリは最大100個）
- 1 ≦ k_i ≦ 40（項番号は最大40まで）
→ よって、最大でも a₄₀ までを求められればよい
入力例：
5
1
2
3
4
3
出力例：
1
1
2
3
2
✅OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const Q = Number(lines[0]);
const queries = lines.slice(1).map(Number);
const a = [];
a[1] = 1;
a[2] = 1;
for(let i = 3; i <= 40; i++){
a[i] = a[i-1] + a[i-2];
}
for(const k of queries){
console.log(a[k]);
}
});
🔍変数ver
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
lines.slice(1).map(Number).forEach(k => {
if (k === 1 || k === 2) {
console.log(1);
}
else {
let prev2 = 1;
let prev1 = 1;
let current;
for(let i = 3; i <= k; i++){
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
console.log(current);
}
})
});
📝めも
-
フィボナッチ数列は、漸化式（前の項との関係）で作る代表例。
-
項の番号が最大40と小さいので、先に全部計算しておく配列方式（DP）が速くて簡単。
-
再計算を避ける：同じ値を何度も求めるなら、一度保存して使いまわせると効率が良い。
-
変数だけで回す方法（省メモリ）もある。長さを気にしないなら配列の方が見やすい。※しかし複数クエリを処理するなら不適。