1347: 又是斐波那契数列
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 592 Solved: 203
Description
在数学中斐波那契数列F是这样定义的:F(n)=F(n-1)+F(n-2),F(0)=1,F(1)=1。现在我有另外一个序列G,G(n)=G(n-1)+G(n-2),G(0)=1,G(1)=t(t>=1)。
你的任务对于给定的i,G(i)和j输出G(j)。
Input
多组测试数据,对于每组测试数据包含三个正整数i,G(i),j。1 <= i,j <=20, G(i)<100000。
Output
对于每组数据，如果t存在输出对应的G(j)的值，否则输出-1。
Sample Input
1 1 2
3 5 4
3 4 6
12 17801 19
Sample Output
2
8
-1
516847
题解：之前看到这样的题目是一点也不想做的感觉，规律其实很好找。把题目给的数据带进去算一下就能发现下表。不过建议不要用斐波那契数列作为系数，会导致后来的分类讨论比较麻烦。
找出公式g[i]=f(i-1)*t+f(i-2);
t=1.0*(g[i]-f(i-2))/f(i-1));
根据题目讲的输入为三个正整数可知，g[i]为正整数，而t属于g[i]，那么判断条件就是如果t不是整数，输出-1.(这里卡了我好久QQ)。
关于判断t是否为整数的办法：判断被除数%除数是否为0，如果为0，说明整除。（昨晚肯定是傻了这里也卡了）。
hz同学告诉我说用（int)t==t这种判断方法并不好，精度问题。
还有一种判断方法也不行，就是*10之后取整再%10，如果t=1.01则不行。
但是题目交了一遍又一遍，之前是runtime error(没有判断i不等于1的时候j如果等于1的情况，输入5 8 1 没有输出)，后来是WA，测试数据（输入1 0 1 输出-1）坑了我QQ
代码：
#includelong long f(long long n) //斐波那契数列
{
if(n==0)
return 1;
if(n==1)
return 1;
return f(n-1)+f(n-2);
}
int main()
{
int i,g,j;
double t;
while(~scanf("%d%d%d",&i,&g,&j))
{
if(i<1||i>20||j<1||j>20||g>100000)
break;
if(i==1)
{
t=g;
if(j==1 && t>=1) //需要判断t>=1
{
printf("%d\n",g);
}
else if(t>=1)
printf("%.f\n",f(j-1)*t+f(j-2));
else
printf("-1\n");
//continue; 某学长说要吃bazhang?
}
else
{
t=1.0*(g-f(i-2))/f(i-1);
//long long flag=(long long)(t*10);
//flag%=10;
//printf("t is %.2f\n",t);
//printf("flag is %d\n",flag);
// int flag=0;
// if((int)t!=t)
// flag=1;
if(((g-f(i-2))%f(i-1)==0)&&t>=1)//说明t是整数
{
if(j==1) //忘记考虑的情况
{
printf("%.f\n",t);
}
else
printf("%.f\n",f(j-1)*t+f(j-2));
}
else
{
printf("-1\n");
}
}
}
return 0;
}
网友评论