描述
现在我们根据这个规则定义另一种数列 命名为"辛波那切数列", 它是这样定义的：
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的值。
3 -1 0.667 3.15
0 1 2
不知道对不对，没来得及提交
C++版
1 #include "iostream.h"
2 #include <map>
3 #include<time.h>
4 using namespace std;
5
6 map<double,int> haTable;
7 int Sibonacci(double n)
8 {
9 if(n<0)return 0;
10 else if(n<3.14)return 1;
11 else {
12 int a = 0;
13 int b = 0;
14 map<double,int>::iterator iter;
15 iter = haTable.find(n-1);
16 if(iter!=haTable.end())
17 a = (int)iter->second;
18 else a = Sibonacci(n-1);
19
20 iter = haTable.find(n-3.14);
21 if(iter!=haTable.end())
22 b = (int)iter->second;
23 else b = Sibonacci(n-3.14);
24
25 int temp = (a+b)%1000000007;
26 haTable.insert(map<double,int>::value_type(n,temp));
27 return temp;
28 }
29 }
30 int main()
31 {
32 clock_t start,finish;
33 start=clock();
34 cout<<Sibonacci(1000)<<endl;
35 finish=clock();
36 cout<<finish-start/CLOCKS_PER_SEC;
37 }
JAVA版
代码
public static void main(String[] args) {
// TODO Auto-generated method stub
long startTime=System.currentTimeMillis();
Integer temp = Sibonacci(1000);
long endTime=System.currentTimeMillis(); //获取结束时间
System.out.println(temp);
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
}
public static Hashtable<Double,Integer> haTable = new Hashtable<Double,Integer>();
public static Integer Sibonacci(double n)
{
if(n<0)return 0;
else if(n<3.14)return 1;
else {
Integer a = 0;
Integer b = 0;
if(haTable.containsKey(n-1))
a = haTable.get(n-1);
else a = Sibonacci(n-1);
if(haTable.containsKey(n-3.14))
b = haTable.get(n-3.14);
else b = Sibonacci(n-3.14);
Integer temp = (a+b)%1000000007;
haTable.put(n,temp);
return temp;
}
}
}
前者要用时4937ms
后者要用时2875ms
莫非是java中的hashtable性能要强于STL中的map。
权当是抛砖引玉，希望高手指点。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。