算盤の書
题意翻译
斐波那契数列,指得是这样一个数列:数列的第一个数为1,第二个数为2,接下来每个数都等于前面2个数之和,即:1, 2, 3, 5, 8, 13……现给出一个非负整数N(也可能为0),求斐波那契数列中第N项是多少?
感谢@陆麟瑞666 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/tenka1-2012-qualA/tasks/tenka1_2012_qualA_1
ある数学者は次の問題を考案したという。
- $ 1 $ つがいの兎は、産まれて $ 2 $ か月後から毎月 $ 1 $ つがいずつの兎を産む。
- 兎が死ぬことはない。
- この条件のもとで、産まれたばかりの $ 1 $ つがいの兎は $ 1 $ 年の間に何つがいの兎になるか?
※つがい:オスとメスの一組
この問題は上の問題をもとにした問題です。
今、 $ 1 $ つがいの産まれたばかりの兎がいるとします。
上の問題の条件と同様に兎が増えるとすると、 $ n $ ヶ月後に何つがいの兎がいるでしょう?
このとき、 $ n $ ヶ月後ちょうどに産まれた兎のつがいも数に含めます。
入力は以下の形式で標準入力から与えられる。 > $ n $
- 何ヶ月後かを表す整数 $ n $ ($ 0\ \leq\ n\ \leq\ 45 $) が $ 1 $ 行で与えられる。
$ n $ ヶ月後の兎のつがいの数を標準出力に $ 1 $ 行で出力せよ。
なお、行の終端には改行が必要である。 ```
输入输出格式
输入格式
输出格式
输入输出样例
输入样例 #1
0
输出样例 #1
1
输入样例 #2
5
输出样例 #2
8
输入样例 #3
45
输出样例 #3
1836311903
说明
样例 2:
$ 2 $ ヶ月後に $ 1 $ つがい、 $ 3 $ ヶ月後に $ 1 $ つがい、
$ 4 $ ヶ月後に $ 2 $ つがい、 $ 5 $ ヶ月後に $ 3 $ つがいが産まれ、
初めにいた $ 1 $ つがいと合わせて、合計 $ 8 $ つがいとなる。