1347: 又是斐波那契數(shù)列
Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?592??Solved:?203
Description
在數(shù)學(xué)中斐波那契數(shù)列F是這樣定義的:F(n)=F(n-1)+F(n-2),F(0)=1,F(1)=1?，F(xiàn)在我有另外一個序列G,G(n)=G(n-1)+G(n-2),G(0)=1,G(1)=t(t>=1)。
你的任務(wù)對于給定的i,G(i)和j輸出G(j)。
Input
多組測試數(shù)據(jù),對于每組測試數(shù)據(jù)包含三個正整數(shù)i,G(i),j。1 <= i,j <=20, G(i)<100000。
Output
對于每組數(shù)據(jù)，如果t存在輸出對應(yīng)的G(j)的值，否則輸出-1。
Sample Input
1 1 2
3 5 4
3 4 6
12 17801 19
Sample Output
2
8
-1
516847
題解：之前看到這樣的題目是一點也不想做的感覺，規(guī)律其實很好找。把題目給的數(shù)據(jù)帶進(jìn)去算一下就能發(fā)現(xiàn)下表。不過建議不要用斐波那契數(shù)列作為系數(shù)，會導(dǎo)致后來的分類討論比較麻煩。
找出公式g[i]=f(i-1)*t+f(i-2);
t=1.0*(g[i]-f(i-2))/f(i-1));
根據(jù)題目講的輸入為三個正整數(shù)可知，g[i]為正整數(shù)，而t屬于g[i]，那么判斷條件就是如果t不是整數(shù)，輸出-1.(這里卡了我好久QQ)。
關(guān)于判斷t是否為整數(shù)的辦法：判斷被除數(shù)%除數(shù)是否為0，如果為0，說明整除。（昨晚肯定是傻了這里也卡了）。
hz同學(xué)告訴我說用（int)t==t這種判斷方法并不好，精度問題。
還有一種判斷方法也不行，就是*10之后取整再%10，如果t=1.01則不行。
但是題目交了一遍又一遍，之前是runtime error(沒有判斷i不等于1的時候j如果等于1的情況，輸入5 8 1 沒有輸出)，后來是WA，測試數(shù)據(jù)（輸入1 0 1? 輸出-1）坑了我QQ
代碼：
#includelong long f(long long n) //斐波那契數(shù)列
{
? ? 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;? 某學(xué)長說要吃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是整數(shù)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(j==1)? ? //忘記考慮的情況
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? printf("%.f\n",t);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? printf("%.f\n",f(j-1)*t+f(j-2));
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? printf("-1\n");
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return 0;
}
