学步园

菲波那切数列可以用下列的式子表示:
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2) (n>=3)

现在我们根据这个规则定义另一种数列 命名为"辛波那切数列", 它是这样定义的：
s(x)=0 (x<0)
s(x)=1 (0<=x<1)
s(x)=s(x-1)+s(x-3.14) (x>=1)

现在需要计算出s(x) MOD 1000000007的值。

第一行有一个正整数T表示有T组测试数据。
接下来T行,每行包含一个数x。
其中 T<=10000, -1000.0<=x<=1000.0

有T行，依次输出每组数据的结果。

我的分析

      采用简单的递归的方法在做这题时间上肯定会超时，因而只有分析下，有没有其它的办法。

      经过分析，看能否转换为fibonacci数的问题：

      当x<-[1,3.14)时，s(x)=s(x-1)=...=1,s(x-3.14)=0;--------s(x)=1;

      当x<-[3.14,4.14)时，x-1<-[2.14,3.14),s(x-1) = 1,s(x-3.14)=1-------s(x)=2;

      当x<-[4.14,5.14)时，x-1<-[3.14,4.14) ,s(x-1) =2 ,x-3.14<-[1,2),s(x-3.14)=1;------s(x)=3;

      当x<-[5.14,6.14)时，x-1<-[4.14,5.14),s(x-1)=3,x-3.14<-[2,3),s(x-3.14)=1;---------s(x)=4;

      当x<-[6.14,7.14)时，x-1<-[5.14,6.14),s(x-1)=4,x-3.14<-[3,4),...此时s(x-3.14)的值不定，分析就此截止

     说明x-1与x-3.14不是正好落在分别前两个区间，故其函数值也不能用前两个区间的函数值之和来计算；美好的想法只能落空。

网友的分析

以下引用http://topic.csdn.net/u/20100524/22/c3ff1e6d-8d2d-42f4-a982-cddf7ab77528.html网友的分析和代码

12楼：danjiewu

条件-1000.0<=x<=1000.0很关键，其实要把3.14当作整数来看待，也就是s(x)=s(x-100)+s(x-314)，-100000<=x<=100000，这样就好办了，直接把所有结果都计算出来就可以了。当然还要考虑到精度损失的问题，这个倒卡了好久。

danjiewu的代码：

#include<iostream><br /> using namespace std;</p> <p>int main(){<br /> int m[100001];<br /> for(int i=0;i<100001;i++){<br /> if(i<314)m[i]=1;<br /> else m[i]=(m[i-100]+m[i-314])%1000000007;<br /> }<br /> int n;<br /> cin>>n;<br /> while(n-->0){<br /> double a;<br /> cin>>a;<br /> if(a<0)cout<<0<<endl;<br /> else{<br /> int b = (int)(a*100+0.000001);<br /> cout<<m[b]<<endl;<br /> }<br /> }<br /> }

6楼knate

int check1(double val){<br /> if(val < 0)<br /> return 0;<br /> if(val < 3.14)<br /> return 1;<br /> if(val > 10000000)<br /> return 0;//无效数据</p> <p> val *= 100;<br /> int x = (int) val;<br /> if(val > x)//这个值得商榷,实际上整个3.14值得商榷.居然使用double这种非精确数据进行测试.<br /> ++ x;<br /> vector<int> v;<br /> v.resize(314,1);<br /> v.resize(x + 1);<br /> for(int i = 314;i <= x;++ i){<br /> v[i] = (v[i - 100] + v[i - 314]) % 1000000007;<br /> //Test ++;<br /> }<br /> return v[x];<br /> }</p> <p>int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> double x ;<br /> x = 1000;<br /> time_t t = clock();</p> <p> Test = 0;<br /> t = clock();<br /> cout<<check1(x)<<endl;<br /> t = clock() - t;<br /> cout<<t<<endl;<br /> //cout<<Test<<endl;<br /> return 0;<br /> }<br />