33,010
社区成员
发帖
与我相关
我的任务
分享今晚网易有道编程挑战赛的练习题
定义一种数列 命名为"辛波那切数列", 它是这样定义的：
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的值。
求s（x），谁有什么好算法呢？
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的值。
求s（x），谁有什么好算法呢？
...全文
请发表友善的回复…
发表回复
fanster28_ 2010-05-27
- 打赏
- 举报
这题当时确实这样过的，不过对IPSC 2001 - Problem F是不能这样做的
这个都推错了，那
s(x)=F(2n+1) 0<=x0<1
s(x)=F(2n+2) 1<=x0<3.14
这个公式是不对的，
另外一个问题是要实现log(n)的算法时如何保证精度问题？
这个是无理数的n次方如何保证计算的精度，尤其是IPSC那题本身就要大数高精度的。
值 范围 对应斐波那契的项
0 x<0
1 [0,3.14) 2
2 [3.14,4.14) 3
3 [4.14,6.28) 4
5 [6.28,7.28) 5
.....
这个都推错了，那
s(x)=F(2n+1) 0<=x0<1
s(x)=F(2n+2) 1<=x0<3.14
这个公式是不对的，
另外一个问题是要实现log(n)的算法时如何保证精度问题？
这个是无理数的n次方如何保证计算的精度，尤其是IPSC那题本身就要大数高精度的。
qiuzhenguang 2010-05-26
- 打赏
- 举报
顶6L和17L
ithiker 2010-05-26
- 打赏
- 举报
值 范围 对应斐波那契的项
0 x<0
1 [0,3.14) 2
2 [3.14,4.14) 3
3 [4.14,6.28) 4
5 [6.28,7.28) 5
.....ithiker 2010-05-26
- 打赏
- 举报
是个斐波那契数列的问题
斐波那契数列：1 1 2 3 5....
值 范围 对应斐波那契的项
0 x<0
1 [0,3.14) 2
2 [3.14,4.14) 3
3 [4.14,6.28) 4
5 [6.28,7.28) 5
.....
关键是怎么建立从第二列到第三列的映射问题
我做的时候涉及到小数的精度问题，比如计算机中3.14*100居然等于313
斐波那契数列：1 1 2 3 5....
值 范围 对应斐波那契的项
0 x<0
1 [0,3.14) 2
2 [3.14,4.14) 3
3 [4.14,6.28) 4
5 [6.28,7.28) 5
.....
关键是怎么建立从第二列到第三列的映射问题
我做的时候涉及到小数的精度问题，比如计算机中3.14*100居然等于313
qiuzhenguang 2010-05-26
- 打赏
- 举报
牛人真多啊，学习了，这题我当时也没做出来。
HelloGameProgramer 2010-05-26
- 打赏
- 举报
27楼 的 同 学请给一个证明
showjim 2010-05-26
- 打赏
- 举报
[Quote=引用 27 楼 fire_woods 的回复:]
给出通项式.
假设已知斐波那契数列
F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)
令n = [x/3.14], x0=x-n*3.14
即n为x除以3.14的整数项,x0为余数.
s(x)=F(2n+1) 0<=x0<1
s(x)=F(2n+2) 1<=x0<3.14
所以问题就简化为求斐波那契数列,是log(n)时间复杂度的算法.
[/Quote]
应该不是斐波那契数列:
s(<0)=0
s(<3.14)=1
s(<4.14)=2
s(<5.14)=3
s(<6.14)=4
给出通项式.
假设已知斐波那契数列
F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)
令n = [x/3.14], x0=x-n*3.14
即n为x除以3.14的整数项,x0为余数.
s(x)=F(2n+1) 0<=x0<1
s(x)=F(2n+2) 1<=x0<3.14
所以问题就简化为求斐波那契数列,是log(n)时间复杂度的算法.
[/Quote]
应该不是斐波那契数列:
s(<0)=0
s(<3.14)=1
s(<4.14)=2
s(<5.14)=3
s(<6.14)=4
fire_woods 2010-05-26
- 打赏
- 举报
归纳法对1<=x0<3.14的结果的推导有问题, 所以那个通项式是不对的.抱歉
AAA20090987 2010-05-25
- 打赏
- 举报
菜鸟来学习一下。
knate 2010-05-25
- 打赏
- 举报
int check1(double val){
if(val < 0)
return 0;
if(val < 3.14)
return 1;
if(val > 10000000)
return 0;//无效数据
val *= 100;
int x = (int) val;
if(val > x)//这个值得商榷,实际上整个3.14值得商榷.居然使用double这种非精确数据进行测试.
++ x;
vector<int> v;
v.resize(314,1);
v.resize(x + 1);
for(int i = 314;i <= x;++ i){
v[i] = (v[i - 100] + v[i - 314]) % 1000000007;
//Test ++;
}
return v[x];
}
int _tmain(int argc, _TCHAR* argv[])
{
double x ;
x = 1000;
time_t t = clock();
Test = 0;
t = clock();
cout<<check1(x)<<endl;
t = clock() - t;
cout<<t<<endl;
//cout<<Test<<endl;
return 0;
}
绿色夹克衫 2010-05-25
- 打赏
- 举报
这个范围用备忘录就可以，都不需要生成函数了。
并且直接递归也不会栈溢出。
并且直接递归也不会栈溢出。
using System;
using System.Collections.Generic;
namespace CSharpTest
{
class Program
{
static Dictionary<double, int> dict = new Dictionary<double, int>();
public static void Main()
{
Console.WriteLine(F(1000));
}
static int F(double n)
{
if (n < 0)
return 0;
if (n < 1)
return 1;
if (!dict.ContainsKey(n))
{
int result = (F(n - 1) + F(n - 3.14)) % 1000000007;
dict.Add(n, result);
}
return dict[n];
}
}
}
Justmeh 2010-05-25
- 打赏
- 举报
-1000<=x<=1000;
用递归的话，x=50就得用差不多10秒钟了，x=100的时候，我等了40分钟还没出结果，而且运算时间似乎是以2的幂来增长，
如果取1000的话，不知道会不会跑到下个月。
用递归的话，x=50就得用差不多10秒钟了，x=100的时候，我等了40分钟还没出结果，而且运算时间似乎是以2的幂来增长，
如果取1000的话，不知道会不会跑到下个月。
showjim 2010-05-25
- 打赏
- 举报
如果x<1000的话，开个1000*100的数组缓存结果就行了。
如果x是不限大小的实数类型，可以将某个数(比如这里可以用B=100*314/2=15700)分解成314个积和，然后以2的幂(B^2,B^4,...)推出所有阶的314个积和，时间代价为314*log(n)，空间代价为314*log(n)。这样所有数都可以在log(n)的时间之内推到B之内。如果B内的所有数作缓存，空间代价为B，那么每次的查询代价为314+log(n)。
如果x是不限大小的实数类型，可以将某个数(比如这里可以用B=100*314/2=15700)分解成314个积和，然后以2的幂(B^2,B^4,...)推出所有阶的314个积和，时间代价为314*log(n)，空间代价为314*log(n)。这样所有数都可以在log(n)的时间之内推到B之内。如果B内的所有数作缓存，空间代价为B，那么每次的查询代价为314+log(n)。
AndyZhang 2010-05-25
- 打赏
- 举报
有没有递归过得，感觉可以啊
fanster28_ 2010-05-25
- 打赏
- 举报
这个其实是IPSC 2001 - Problem F的简化版本
首先这个把精度减得很小了，其次这个求模不涉及大数处理
IPSC 2001 - Problem F这题是相当有难度的，当时只有5组人做出来了。
fire_woods你的
s(x)=F(2n+1) 0<=x0<1
s(x)=F(2n+2) 1<=x0<3.14
怎么退出来的，能仔细解释一下么？
首先这个把精度减得很小了，其次这个求模不涉及大数处理
IPSC 2001 - Problem F这题是相当有难度的，当时只有5组人做出来了。
fire_woods你的
s(x)=F(2n+1) 0<=x0<1
s(x)=F(2n+2) 1<=x0<3.14
怎么退出来的，能仔细解释一下么？
woshishabi1984 2010-05-25
- 打赏
- 举报
又看了一遍6L和17L的。。很好。。。在下自叹不如。。。思路总是往直接求通项或者直接算答案上面。。。想过用递推但是没想过可以乘100之后递推。。。惭愧。。。要学的还太多
绿色夹克衫 2010-05-25
- 打赏
- 举报
恩，确实是转为整数比较好。6楼knate的方法比我给出的要好，尤其是同时测试多个例子的时候。
不过还有log(n)的方法，暂时不想了。
不过还有log(n)的方法，暂时不想了。
woshishabi1984 2010-05-25
- 打赏
- 举报
不能直接用递归，一是时间长，二是体现不出技巧。
6L同学应该是对的。
另外14L同学的方法有问题，主要是精度的问题，有误差，而且如果算SUM的话会溢出，一开始我用的就是这个思路，结果错了，还是6L和17L的方法好。。当然这个SUM是可以直接算的，算了半天SUM结果还是WRONG ANSWER,一看不仅误差而且UNSIGNED INT放不下。。。乖乖。。。组合数公式也得自己写。
“从坐标轴的x处向远点方向走，每步走1或3.14，走到[1,0)区域有多少种走法？”
这个问题就是假设某种走法可以走K1步1，走K2步3.14，则一共有C(K1+K2, K1)种走法，遍历算一遍就可以了（当然一般情况下算组合数精度不够了还会溢出），所以说了半天这方法不可行，直接上6L或者17L的办法。。
顺便说一句，有高人10几分钟就做出来这题了，差距啊差距。。。
以下直接算SUM，当然没过。。。大于UINT的范围必错
6L同学应该是对的。
另外14L同学的方法有问题，主要是精度的问题，有误差，而且如果算SUM的话会溢出，一开始我用的就是这个思路，结果错了，还是6L和17L的方法好。。当然这个SUM是可以直接算的，算了半天SUM结果还是WRONG ANSWER,一看不仅误差而且UNSIGNED INT放不下。。。乖乖。。。组合数公式也得自己写。
“从坐标轴的x处向远点方向走，每步走1或3.14，走到[1,0)区域有多少种走法？”
这个问题就是假设某种走法可以走K1步1，走K2步3.14，则一共有C(K1+K2, K1)种走法，遍历算一遍就可以了（当然一般情况下算组合数精度不够了还会溢出），所以说了半天这方法不可行，直接上6L或者17L的办法。。
顺便说一句，有高人10几分钟就做出来这题了，差距啊差距。。。
以下直接算SUM，当然没过。。。大于UINT的范围必错
typedef unsigned int UINT;
double C(double n, double m)
{
double ret = 0;
if (m > n/2)
m = n-m;
for (double i = m+1; i <= n; ++i)
ret += log(i);
for (double i = 2; i <= n-m; ++i)
ret -= log(i);
return exp(ret);
}
double getSibonacci(double x)
{
if (x < 0)
return 0;
else
{
double ret = 1;
for (double i = 1; ; ++i)
{
int temp = x - 3.14*i;
if (temp > 0)
ret += C((double)(temp+i), (double)temp);
else
break;
}
return ret;
}
}
小楫轻舟 2010-05-25
- 打赏
- 举报
17楼的好方法，
danjiewu 2010-05-25
- 打赏
- 举报
我的代码
#include<iostream>
using namespace std;
int main(){
int m[100001];
for(int i=0;i<100001;i++){
if(i<314)m[i]=1;
else m[i]=(m[i-100]+m[i-314])%1000000007;
}
int n;
cin>>n;
while(n-->0){
double a;
cin>>a;
if(a<0)cout<<0<<endl;
else{
int b = (int)(a*100+0.000001);
cout<<m[b]<<endl;
}
}
}加载更多回复（18）
