求帮忙看一道c题，跟斐波那契有点像
f(x)=0 (x<0)
f(x)=1 (0<=x<1)
f(x)=f(x-1)+f(x-3.14) (x>=1)
Your work is to tell me the result of f(x), is the answer is too large, divide it by 1000000007 and give me the remainder.
Be careful the number x can be an integer or not.
Input
In the first line there is an Integer T(0<T<10000) which means the number of test cases in the input file.
Then followed T different lines, each contains a number x(-1000<x<1000).
Output
For each case of the input file, just output the result, one for each line.
Time Limit: 1 Sec Memory Limit: 64 MB
直接把题贴在这里啦，大家看看
递归的做法会超时啊T T想不到好的方法，来求助大家~ C
[解决办法]
优化下
1，用数组把中间已经求得的f(x)保存，每次算的时候先检测是否有保存，有保存直接读，没保存在算
数组2000不超空间
2，每次求出f(x)时都对1000000007 取模，保存也保存取模后的值
[解决办法]
把 x * 100 , 然后就不需要浮点运算了, 然后把 0 <= x <= 1000 * 100 范围全计算出来, 最后就读输入, 查表, 输出就行了...
[解决办法]
事实上最坑爹的是x的定义吧，x可以为单精度，也可以为双精度，一旦涉及到浮点数来比较大小，就难免需要用eps。更坑爹的是这些题特喜欢考eps，各种临界值。
[解决办法]
赶项目 要加班啊 据说还要封闭开发 做开发一年都不到就… 苦逼啊
采用3楼的方法 直接用整数，另外注意，对题中值太大的越界不做检查，仅测试算法速度
先上个递归的，方便测试
int Caculate(int s)
{
if (s < 0)
return 0;
if (s < 100)
return 1;
return Caculate(s - 100) + Caculate(s - 314);
}
int Caculate2(int s)
{
std::map<int, int> mapValues1;
std::map<int, int> mapValues2;
mapValues1[s] = 1;
bool bChanged = true;
int count = 0;
std::map<int, int>* p1;
std::map<int, int>* p2;
while (true)
{
p1 = bChanged ? &mapValues1 : &mapValues2;
p2 = bChanged ? &mapValues2 : &mapValues1;
if (p1->empty())
break;
p2->clear();
for (std::map<int, int>::iterator i = p1->begin(), e = p1->end(); i != e; ++i)
{
if (i->first < 0)
continue;
if (i->first <100)
{
count += i->second;
continue;
}
p2->operator [](i->first - 100) += i->second;
p2->operator [](i->first - 314) += i->second;
}
bChanged ^= true;
}
return count;
}
int Caculate3(int s)
{
int x = s / 100 + 1;
int iCount = 0;
for (int i = 1; i <= x; ++i)
{
//对于第i层，有i个数字
int m = s - 100 * (i - 1);
for (int j = 0; j < i; ++j)
{
int r = m - 214 * j; // x = s - (314 * j + 100 * (i - j))
if (r < 0)
break;
if (r < 100)
{
//先计算Ca^b
int a = i - 1;
int b = j;
if (2 * b > a)
b = a - b;
int sum = 1;
int c = 0;
for (int k = a; c < b; --k, ++c)
{
sum *= k;
}
c = 0;
for (int k = 2; c < b - 1; ++k, ++c)
{
sum /= k;
}
iCount += sum;//Ci-1 j
}
}
}
return iCount;
}
