#113. 斐波那契数列的第k项

斐波那契数列的第k项

题目描述

斐波那契数列是满足如下性质的一个数列:

  • f(1)=1f(1) = 1
  • f(2)=1f(2) = 1
  • f(n)=f(n1)+f(n2)f(n) = f(n-1) + f(n-2) ( n3n \ge 3nn 为整数 )

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为 11,接下来每个数都等于前面 22 个数之和。

给出一个正整数 kk,要求菲波那契数列中第 kk 个数是多少。

输入格式

一个非负整数,kk

输出格式

斐波那契数列第 kk 项的值。

样例

样例输入

4

样例输出

3

数据范围与提示

n90 n \leq 90

有一种小兔子,出生后一个月就可以长大成熟,然后再过一个月一对成熟的兔子就可以生育成一对小兔子,且以后每个月都能生育一对。 现在,我们有一对刚出生的小兔子,那么,10个月以后会有多少对这样子的兔子呢?假设所有兔子都不会死亡。