-1

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

我有一个递归关系 f(n) = 2 * (f(n-1) + f(n-2))。我必须求解 f(k) mod 1000000007，其中 k 是输入。k 的范围是 1 <= k <= 1000000000?。我尝试通过简单的递归函数来实现它，但显然它会导致大 k 溢出，因此我遇到了运行时错误。我是算法和东西的新手，所以需要知道是否存在解决此类问题的具体有效方法？

#include<stdio.h>
#define M 1000000007
long long unsigned res(long long unsigned n){
  if(n==1)
    return 1;
  else {
    if(n==2)
      return 3;
    else return (2*(res(n-1)%M+res(n-2)%M));
  }
}
int main(){
  int test;
  scanf("%d",&test);
  while(test--){
    long long unsigned n;
    scanf("%llu",&n);
    printf("%llu\n",res(n));
  }
  getch();
  return 0;
}
4

2 回答 2

0

您可以使用以下两个身份：

mod(a * b, p) = mod(mod(a, p) * mod(b, p), p)
mod(a + b, p) = mod(mod(a, p) + mod(b, p), p)

这给了你，假设 mod(2, p) = 2：

mod(f(n), p) = mod(2 * mod(mod(f(n - 1), p) + mod(f(n - 2), p), p), p)

或更简单：

mod(f(n), p) = mod(mod(2 * f(n - 1), p) + mod(2 * f(n - 2), p), p)

从那里应该很容易计算 f(k)。而且不需要递归，可以做一个线性解析（这只是斐波那契数列的一种变体）。

提示：尝试同时保留f(n - 1)和f(n - 2)在本地，f(n)从中计算，然后更新您的本地并迭代。

于 2012-07-05T08:09:38.410 回答
0

首先，您必须定义 f(0) 和 f(1) 会发生什么，因为在某些时候您会到达它们。然后你可以向前而不是向后解决它。从 2 开始并继续前进，直到您以这种方式到达 k：

f(k) {
    a = F0; // F0 is the predefined value f(0)
    b = F1; // F1 is the predefined value f(1)
    if ( k == 0 ) {
       return a;
    }
    else if ( k == 1 ) {
       returb b;
    }
    else {
       n = 2;
       while ( n < k ) {
          c=2*(a+b);
          a=b;
          b=c;
          n = n+1;
       }
       return c;
    }
}

如果你多次调用它，你应该考虑将所有的 c 保存在某个地方，这样你就不必每次都重新计算它。我希望我足够清楚。不然再问我

于 2012-07-05T08:12:57.923 回答