今回から新シリーズ「Kボナッチ数列」を解いていきましょう。
6-1 「K ボナッチ数列」を解くために:part1
まずは一般的なフィボナッチ数列について考えてみましょう。
「フィボナッチ数列」とは、1, 2 項目を 1 とし、 3 項目以降は前項 2 項の和となる数列です。 具体的には、1, 1, 2, 3, 5, 8, ... となります。
フィボナッチ数列の N 項目を 10000 で割ったあまりを求めてください。
| 入力例 | 出力例 | |
| 1000 | 8875 |
まずは一般に言われているフィポナッチ数列です。
問題文のとおりに作成すれば容易に作成できます。
A = []
N = int(input())
A.append(1)
A.append(1)
a=0
for i in range(1,N-1):
a = A[i-1] + A[i]
A.append(a)
print(A[-1] % 10000)
6-2 「K ボナッチ数列」を解くために:part2
元の問題の「K ボナッチ数列」を考えます。
1, 2, ..., K 項目を 1 とし、 K + 1 項目以降は前項 K 項の和となる数列のことを、「K ボナッチ数列」と呼ぶことにします。
整数 K と N が与えられるので、 K ボナッチ数列の N 項目を 10000 で割ったあまりを求めてください。
今回の問題では N, K の値が小さいことが保証されるため、各項を求めるときに毎回前項 K 項の和を計算しても実行時間制限に間に合います
| 入力例 | 出力例 | |
| 3 | 105 | |
| 10 |
さて、「Kボナッチ数列」なるものは何か？
確かに問題文の通りですが、イメージがわきずらくはありませんか。
例でいけば、K=3です。
[1, 1, 1, 3, 5, 9, 17, 31, 57, 105]
K=3ですので、3 = [0] + [1] + [2] = 1+1+1
5 = [1] + [2] + [3] = 1+1+3 という具合に配列が作成されます
定義がわかれば、前回のプログラムを修正することでプログラムは容易に作成できます。
A = []
K = int(input())
N = int(input())
for i in range(K):
A.append(1)
for i in range(N-K):
a = sum(A[i:i+K])
A.append(a)
print(A[-1] % 10000)