第104回【JavaScript】2項間漸化式 1、2項間漸化式 2
現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
JavaScript をゼロから勉強してみよう、のコーナー 104 回目です。
久しぶりにレオくんが脱走しました。しかし、玄関を開けてしばらく待っていると帰ってきました。年に 1 回くらい脱走しますが（お客さんが玄関を開けっぱなしで立ち話を始めてしまったときくらい）、臆病な子なので、長くても 2 時間、目の届く範囲より外へ出ることはありません。わっしゃわっしゃと洗って、ピカピカにしておきました。
それでは、今日も頑張ってみようと思います。
2項間漸化式 1 (paizaランク C 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_recursive_...(はじめに)
このメニューでは、動的計画法 (Dynamic Programming, 以下 DP と表記します) について扱います。
DP は、一言でいうと「問題を部分問題に分割し、部分問題の答えを記録しながら、それらを利用することによって元の問題の答えを得る手法」です。
問題をどのように分割するか、部分問題の答えをどのように利用するかなどは問題により異なります。このメニューを通してさまざまなDPの問題に触れ、そのノウハウを身につけていきましょう。
まずは、早速問題を見てみましょう。
(問題)
整数 x, d, k が与えられます。
次のように定められた数列の k 項目の値を出力してください。
・ a_1 = x
・ a_n = a_{n-1} + d (n ≧ 2)(ヒント)
等差数列の公式を使えばDPを使わずとも答えを求めることができますが、練習だと思ってDPで解いてみましょう。
DPを考える際には、まず漸化式を考えるとよいです。漸化式は、数列の各項をその前の項を用いて記述した式です。問題で与えられている a_n = a_{n-1} + d という式がこの問題における漸化式となっています。
では、実際にこの問題を解いてみましょう。最終的に求めたいのは a_k です。a_1 ~ a_{k-1} がわかっているとして、a_k がどうなるかを考えてみましょう (a_1 ~ a_{k-1} が、「はじめに」の部分で述べた"部分問題"に相当しています) 。a_{k-1} がわかっているので、a_k = a_{k-1} + d とすればよいですね。今回は a_1 が x であることがわかっているので、順に a_2, a_3, a_4, … を計算していけば a_k が求まることがわかるかと思います。
以下の疑似コードを参考にして、あなたの得意な言語で実装してみましょう。
a[1] <- x
for i = 2 to k
a[i] <- a[i-1] + d
print a[k]入力される値
x d k入力値最終行の末尾に改行が１つ入ります。
期待する出力
数列の k 項目の値を出力してください。
a_kまた、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ -1,000 ≦ x ≦ 1,000
・ -1,000 ≦ d ≦ 1,000
・ 1 ≦ k ≦ 1,000
入力例
0 7 9出力例
56JavaScript で漸化式を使うことってあるのだろうか。まぁ、面白そうだから書いてみる。
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 [x,d,k] = lines[0].split(/\s/).map(Number);
const a = [];
a[1] = x;
for (let i = 2; i<= k; i++) {
a[i] = a[i-1] + d;
}
console.log(a[k]);
});Python
x,d,k = map(int,input().split())
A = [x]*(k+1)
for i in range(2,k+1):
A[i] = A[i-1] + d
print(A[k])2項間漸化式 2 (paizaランク C 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_recursive_...整数 x, d, Q と Q 個の整数 k_1, k_2, … , k_Q が与えられます。
次のように定められた数列の k_i 項目の値を順に出力してください。
・ a_1 = x
・ a_n = a_{n-1} + d (n ≧ 2)入力される値
x d
Q
k_1
k_2
...
k_Q・ 1行目では、数列の初項 x と公差 d が半角スペース区切りで与えられます。
・ 2行目では、3行目以降で与えられる入力の行数 Q が与えられます。
・ 続く Q 行のうち i 行目では、k_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
Q 行出力してください。
i 行目には、数列の k_i 項目の値を出力してください。
a_{k_1}
a_{k_2}
...
a_{k_Q}また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ -1,000 ≦ x ≦ 1,000
・ -1,000 ≦ d ≦ 1,000
・ 1 ≦ Q ≦ 1,000
・ 1 ≦ k_i ≦ 1,000 (1 ≦ i ≦ Q)
入力例
0 7
5
1
2
3
4
5出力例
0
7
14
21
28こちらも、書かれている通りのことをやってみる。
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 [x,d] = lines[0].split(/\s/).map(Number);
const Q = Number(lines[1]);
const a = Array(1001);
a.fill(x);
for (let i = 2; i <= 1001; i++) {
a[i] = a[i-1] + d;
}
for (let i = 2; i <= Q + 1; i++) {
const k = Number(lines[i]);
console.log(a[k]);
}
});Python
x,d = map(int,input().split())
Q = int(input())
A = [x]*(1001)
for i in range(2,1001):
A[i] = A[i-1] + d
for _ in range(Q):
print(A[int(input())])最後に
高々 1000 なので、これで十分解けるけれども。上限が大きくなったら JavaScript だとどんな風に書くことができるのか、今から楽しみです。
またもや模範解答がなかったので、これがベストかどうかはわからないですが、分かりやすく書くことが出来ているんじゃないかなぁとは思います。
引き続き、よろしくお願いいたします！
