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

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

はじめに

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

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

Windows の仮想デスクトップをよく利用しています。監視用の画面のみを並べておいて、それ以外の作業は別のデスクトップで実施する、とか。複数の端末、複数のモニターを利用していても作業スペースは足らないのです。

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

3項間漸化式 1

整数 k が与えられます。
次のように定められた数列の k 項目の値を出力してください。
ちなみに、これはフィボナッチ数列と呼ばれる有名な数列です。

・ a_1 = 1 
・ a_2 = 1 
・ a_n = a_{n-2} + a_{n-1} (n ≧ 3)
k

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

・ 1 ≦ k ≦ 40

入力例

7

出力例

13

フィボナッチさんはとっても有名ですね。授業で 30 くらいまで手計算で書かされて記憶があるんだけれど、どの学校でもやるんだろうか。

Python
A = [1] * 41
for i in range(3,41):
    A[i] = A[i-2] + A[i-1]
print(A[int(input())])
VBA
Dim A(40) As Long
A(1) = 1
A(2) = 1
For i = 3 To 4
0
    A(i) = A(i - 2) + A(i - 1)
Next
Debug.Print A(Cells(1, 1))

【漸化式】 3項間漸化式 2

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

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

・ 1 ≦ Q ≦ 100
・ 1 ≦ k_i ≦ 40 (1 ≦ i ≦ Q)

入力例

5
1
2
3
4
3

出力例

1
1
2
3
2

40 まで手計算でやって、表を作れば解けるよ。そんなことしないけど。

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())])
VBA
Dim A(40) As Long
A(1) = 1
A(2) = 1
For i = 3 To 40
    A(i) = A(i - 2) + A(i - 1)
Next
Q = Cells(1, 1)
For i = 1 To Q
    k = Cells(i + 1, 1)
    Debug.Print A(k)
Next

最後に

なんでフィボナッチ数は自然界で数多く出現するのだろう。ということを論じる場所ではないけれど、同じ世界、空間で同じ時の流れの中で過ごしていたら、自然と一定の法則の内に収束するんじゃないかと思っている。その値が、フィボナッチ数なんじゃないかなぁ。

となると、フィボナッチ数に収束していないものは、なんらかの別の要因が邪魔をしちゃっているのかと。ストレスがかけられた何かは、フィボナッチ数に収束しない形になっちゃってるとか。

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

Python学習,Python,paiza

Posted by LeoSaki