描述
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数k,要求菲波那契数列中第k个数是多少。
输入
输入一行,包含一个正整数k。(1 <= k <= 46)
输出
输出一行,包含一个正整数,表示菲波那契数列中第k个数的大小
样例输入
19
样例输出
4181
Code:
解法一:递归1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int Fib(int n){
if(n==1||n==2)
return 1;
else
return Fib(n-2)+Fib(n-1);
}
int Fibonac(int a,int b,int n)
{
if(n > 2)
{
return Fibonac(a+b,a,n-1);
}
return a;
}
int main(int argc, char *argv[]) {
int k;//第几个斐波那契数列
scanf("%d",&k);
// printf("%d\n",Fib(k));
int a = 1; //斐波那契数列的第一项
int b = 1; //第二项
printf("%d\n",Fibonac(a,b,k));//优化后的递归 ;
return 0;
}
解法二:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(int argc, char *argv[]) {
int k;
int a1=1,a2=1,i;
scanf("%d",&k);
if(k==1||k==2)
printf("1\n");
else{
int sum;
for(i=0;i<k-2;i++){
sum=a1+a2;
a1=a2;
a2=sum;
}
printf("%d\n",a2);
}
return 0;
}