フィボナッチ数列の性質①

2 secs 1024 MB
Aozora_Kotori_A's icon Aozora_Kotori_A

フィボナッチ数列とは,前2項の和を並べた数列である。 すなわち,フィボナッチ数列をFnF_nnn は自然数)とすると,

Fn={1(n=1, 2)Fn1+Fn2(n3)F_n=\begin{cases}1& (n=1,\ 2) \\F_{n-1} + F_{n-2} & (n \geqq 3)\end{cases}

であり,書き並べると “1, 1, 2, 3, 5, 8, 13, 21,1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ldots”となる。第3項は第1項と第2項の和で,1+1=21+1=2である。第4項は第2項と第3項の和で,1+2=31+2=3である。

問題文

次の問いに答えよ。

  1. 自然数 nn に対して,フィボナッチ数列の第 nn 項を出力する関数 Fibonacci を作成せよ。
  2. 与えられた自然数 nn に対して,フィボナッチ数列の第 nnFnF_n とフィボナッチ数列の第1項から第 nn 項までの和 SnS_n を出力せよ。ただし,n45n\geqq 45 では SnS_n がオーバーフローする可能性があるので,SnS_n を出力する部分は error と出力せよ。

一般に

k=1nFk=Fn+21\displaystyle\sum_{k=1}^n F_k= \underline{\phantom{F_{n+2}-1}}

であることが知られている。(下線部は何が入るか考えてみよう)

制約

  • 入力はすべて自然数
  • 1n461\leqq n\leqq 46

 

入力

入力は以下の形式で標準入力から与えられます。

標準入力

nn

出力

Fn, SnF_n,\ S_n を以下の形式で出力してください。

  • 1n441\leqq n\leqq 44のとき
標準出力

FnF_n

SnS_n

  • 45n4645\leqq n\leqq 46のとき
標準出力

FnF_n

error

 

サンプル1

入力
8
出力
21
54

F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21F_1=1,\ F_2=1,\ F_3=2,\ F_4=3,\ F_5=5,\ F_6=8,\ F_7=13,\ F_8=21なので, S8=1+1+2+3+5+8+13+21=54S_8=1+1+2+3+5+8+13+21=54 です。

 

サンプル2

入力
46
出力
1836311903
error

45n4645\leqq n\leqq 46 を満たすので,SnS_n の部分は error となっています。

Submit


Go (1.21)