第106回【JavaScript】3項間漸化式 1、【漸化式】 3項間漸化式 2
現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
JavaScript をゼロから勉強してみよう、のコーナー 106 回目です。
明け方、違和感で目を覚ますと、右半身が酷く痺れて動けませんでした。恐怖でした。まぁ、ルナちゃんが右太ももに乗っかって寝ていて、レオくんが右腕に乗っかって寝ていたからなんですが。
それでは、今日も頑張ってみようと思います。
3項間漸化式 1 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_recursive_...整数 k が与えられます。
次のように定められた数列の k 項目の値を出力してください。
ちなみに、これはフィボナッチ数列と呼ばれる有名な数列です。
・ a_1 = 1
・ a_2 = 1
・ a_n = a_{n-2} + a_{n-1} (n ≧ 3)(ヒント)
漸化式に登場する項の数が2つから3つへ増えましたが、やはりやることはこれまでと同じです。
入力される値
k入力値最終行の末尾に改行が１つ入ります。
期待する出力
数列の k 項目の値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ k ≦ 40
入力例
7出力例
13フィボナッチさんは定番です。LunaSaki（嫁）が授業でやった記憶がないと言うんですが、必修ではなかったでしたっけ？
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
const k = Number(lines[0]);
const a = Array(41);
a.fill(1);
for (let i = 3; i < 41; i++) {
a[i] = a[i-2] + a[i-1];
}
console.log(a[k]);
});Python
A = [1] * 41
for i in range(3,41):
A[i] = A[i-2] + A[i-1]
print(A[int(input())])【漸化式】 3項間漸化式 2 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_recursive_...整数 Q と Q 個の整数 k_1, k_2, … , k_Q が与えられます。
次のように定められた数列の k_i 項目の値を順に出力してください。
ちなみに、これはフィボナッチ数列と呼ばれる有名な数列です。
・ a_1 = 1
・ a_2 = 1
・ a_n = a_{n-2} + a_{n-1} (n ≧ 3)入力される値
Q
k_1
k_2
...
k_Q・ 1行目では、2行目以降で与えられる入力の行数 Q が与えられます。
・ 続く Q 行のうち i 行目では、k_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
Q 行出力してください。
i 行目には、数列の k_i 項目の値を出力してください。
a_{k_1}
a_{k_2}
...
a_{k_Q}また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ Q ≦ 100
・ 1 ≦ k_i ≦ 40 (1 ≦ i ≦ Q)
入力例
5
1
2
3
4
3出力例
1
1
2
3
2高々 40 までなので、最大 100 回、頭の中で計算すれば解ける問題。出来たら凄いなぁ。
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
reader.on('line', (line) => {
lines.push(line);
});
reader.on('close', () => {
const a = Array(41);
a.fill(1);
for (let i = 3; i < 41; i++) {
a[i] = a[i-2] + a[i-1];
}
const Q = Number(lines[0]);
for (let i = 1; i <= Q; i++) {
console.log(a[Number(lines[i])]);
}
});Python
A = [1] * 41
for i in range(3,41):
A[i] = A[i-2] + A[i-1]
Q = int(input())
for _ in range(Q):
print(A[int(input())])最後に
1 回 1 回計算していると、計算量が大変なことになるので、最初に解答となる配列を用意してから解く。とても単純なことだけれど、初心者は見落としがちなところなのかもしれない。（以前、若手がいちいち 1 回ずつ計算させるような関数を作って解いているのを見たので・・・）
フィボナッチさんの螺旋を見ていると、心が落ち着くときもあれば、心がざわつくときもある。深層心理が反映されて見る人に異なる印象を与えるんじゃないだろうか、って勝手に思っています。
引き続き、よろしくお願いいたします！
