第104回【Python】2項間漸化式 1、2項間漸化式 2

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 104 回目です。

今回からは「DP メニュー」に挑戦します。LeoSaki（旦那）は好きですが、躓く人が多い部分。そして、これをわかりやすく説明できる自信はない！ まぁ、いつも説明なんて書いてないんですけれど。

それでは、今日も頑張ってみようと思います。

2項間漸化式 1

整数 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_{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]

すべてのテストケースにおいて、以下の条件をみたします。

・ -1,000 ≦ x ≦ 1,000
・ -1,000 ≦ d ≦ 1,000
・ 1 ≦ k ≦ 1,000

入力例

0 7 9

出力例

56

疑似コード通りに解いていけばいい問題。これは簡単な疑似コードだけれど、基本情報とかで見る疑似コードはわかりにくいのが多いと思いませんか？

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])
VBA
xdk = Split(Cells(1, 1), " ")
x = Val(xdk(0))
d = Val(xdk(1))
k = Val(xdk(2))
Dim A() As Long
ReDim A(k)
A(1) = x
For i = 2 To k
    A(i) = A(i - 1) + d
Next
Debug.Print A(k)

2項間漸化式 2

整数 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 が与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・ -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

これも解き方は最初の問題と同じ。条件で最大が 1000 と決められているので、それだけのリストを作成してしまう。

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())])
VBA
xd = Split(Cells(1, 1), " ")
x = Val(xd(0))
d = Val(xd(1))
Dim A(1000) As Long
A(1) = x
For i = 2 To 1000
    A(i) = A(i - 1) + d
Next
Q = Cells(2, 1)
For i = 1 To Q
    k = Cells(i + 2, 1)
    Debug.Print A(k)
Next

最後に

これはまだまだ序の口。簡単な問題でした。そもそも、等差数列の公式を求めればもっと簡単に解けてしまうわけで、それならば中学生でもできるはず、です。わざわざ漸化式にしているのだから、しっかり身に付けて次の問題に備えましょう、と paiza が訴えている？

というわけで、さくさくと次の問題に挑戦してみたいと思っています。

引き続き、よろしくお願いいたします！

Pythonpaiza,学習,Python

Posted by LeoSaki