0

可能重复：
我想以 Order(1) 或 (nlogn) 的顺序生成序列 1,3,8,22,60 ,164 的第 n 项

我正在尝试生成一个序列 1,3,8,22,60... 基本上是 a[n]=2*(a[n-1]+a[n-2]); 请在此处参考我的问题我想以 Order(1) 或 (nlogn) 的顺序生成序列 1,3,8,22,60 ,164 的第 n 项

这是我在 c++ 中的实现。但我认为它太慢了。代码在最坏的情况下运行大约 5 秒，而我希望它在不到 1 秒的时间内运行。该方法是 log n 的顺序。所以 10^9 只需要 29 步。这是我的代码。请提出加快速度的方法或我正在做的任何错误

#include <iostream>
#define big long long unsigned int
#include<vector>
#include<stdio.h>
#define _SECURE_SCL 0
big m =1000000007;
using namespace std;
vector <vector <big> > vectin(vector<vector <big> > a)
{
    for(int i=0;i<2;i++)
    {
        vector <big> t;
        for(int j=0;j<2;j++)
        {
            t.push_back(0);
        }
        a.push_back(t);
    }
    return a;
}
vector <vector <big> > unit(vector<vector <big> > a)
{
    for(int i=0;i<2;i++)
    {
        vector <big> t;
        for(int j=0;j<2;j++)
        {   if(i!=j)
            t.push_back(0);
            else
            t.push_back(1);
        }
        a.push_back(t);
    }
    return a;
}
vector<vector <big> > multi(vector<vector <big> > a,vector<vector <big> >b )
{
    vector<vector <big> > c;
    c=vectin(c);
    for(big i=0;i<2;i++){

    for(big j=0;j<2;j++)
    {
        for(big k=0;k<2;k++)
            {
                c[i][j]+=((a[i][k])*(b[k][j]))%m;
            }
    }
}
return c;
}

big modexp_rl(big a,big b, big n)
{
    big r = 1;
    while (1){
        if (b&1)
            r = ((r )*(a) ) % n;
        b /= 2;
        if (!b )
            break;
        a = ((a )* (a) )% n;
    }
    return r;
}

vector <vector <big> > modexs (big b,vector <vector <big> > a )
{
    vector < vector <big > > r;
    r=unit(r);
    while(1)
    {  // cout<<b<<endl;
        if(b&1)
        r=multi(r,a);
        b/=2;

        if(!b)
        break;
        a=multi(a,a);
    }
    return r;
}

void displayvector(vector < vector <big> > s)
{
    for(big i=0;i<2;i++)
    {
        for(big j=0;j<2;j++)
        {
            cout<<s[i][j]<<"\t";
        }
    cout<<endl;
    }

}

vector <big> mul2( vector < vector <big> > a)
{
    vector <big> d;
    d.push_back(3*a[0][0]+1*a[0][1]);
    d.push_back(3*a[1][0]+1*a[1][1]);
return d;
}
int main()
{

  vector < vector <big> > a;
  vector <big> t1,t2;
  t1.push_back(2);
  t1.push_back(2);
  a.push_back(t1);
  t2.push_back(1);
  t2.push_back(0);
  a.push_back(t2);
  //dv(a);
  vector < vector <big> > ans;
  big t,n;
  //cin>>t;
  //scanf("%lld,&t);
  t=10000;
  while(t--){
  //cin>>n;
  //scanf("%lld",&n);
  n=1000000000;
  ans=modexs(n-1,a);
  vector <big> p;
  p=mul2(ans);
  //cout<<p[1]<<endl;
  printf("%lld\n",p[1]);
  //dv(ans);
  }
    return 0;
}
4

3 回答 3

3

如果你知道有多少元素进入你的a向量，你应该在运行算法之前为这些元素保留空间。这是为了避免在向量进行动态调整大小时复制数据。

于 2012-07-04T07:51:58.393 回答
0

如果没有办法增强功能，可以尝试研究多核编程，学习如何实现。以此为参考。它将提高处理性能。但是，它会消耗资源。希望这可以帮助。

于 2012-07-04T07:37:16.000 回答
0

我将级数的生成函数插入 Wolfram Alpha，看起来第 n项是：

[ (1 + Q)^(1+n) - (1 - Q)^(1+n) ] / (4Q) ,

哪里Q = sqrt(3)。

您可能会观察到1 - Q绝对值小于 1，因此对于大 ，整个项呈指数级小n。这意味着对于大的n你可以只计算第一项并取下一个最大的整数。

于 2012-07-04T19:26:21.783 回答