算法来求解F（N）= 2 *（F（N-1）+ F（N-2））模1000000007 [英] Algorithm to solve for f(n) = 2*( f(n-1) + f(n-2) ) mod 1000000007

问题描述

  

可能重复：
  <一href="http://stackoverflow.com/questions/11301992/i-want-to-generate-the-nth-term-of-the-sequence-1-3-8-22-60-164-in-order1-or">I要生成序列1,3,8,22,60，164的订单（1）第n项（nlogn）或订单
  <一href="http://stackoverflow.com/questions/11308621/calculate-the-nth-term-of-the-sequence-1-3-8-22-60-164-448-1224">Calculate序列的第n项1,3,8,22,60,164,448,1224＆hellip ;? 的

我有一个递推关系F（N）= 2 *（F（N-1）+ F（N-2））。我已经解决对于f（k）的模1000000007其中k是输入。 k的范围是1所述; = K＆其中; =十亿?.我曾尝试通过简单的递归函数实现它，但显然它会导致溢出的大k和因此我遇到一个运行时错误。我是新来的算法之类的东西，所以需要知道是否存在具体和有效的方法来解决这样的问题？

 ＃包括＆LT; stdio.h中＆GT;
＃定义中号1000000007
很长很长的无符号RES（很长很长的无符号N）{
  如果（正== 1）
    返回1;
  其他 {
    如果（N == 2）
      返回3;
    否则返回（2 *（水库（正 -  1）％M +水库（N-2）％M））;
  }
}
诠释的main（）{
  INT测试;
  scanf函数（％d个，和放大器;测试）;
  而（试验 - ）{
    很长很长的无符号N;
    scanf函数（％LLU，和放大器; N）;
    的printf（％LLU \ N，RES（N））;
  }
  残培（）;
  返回0;
}
 

解决方案

首先，你必须定义什么发生在f（0）和f（1），因为在某些时候，你会找到他们。 然后，你可以解决它移动落后向前来代替。开始从2和前进，直到到达K的这种方式：

  F（K）{
    A = F0; // F0是predefined值f（0）
    B = F1; // F1是predefined值f（1）
    如果（K == 0）{
       返回;
    }
    否则，如果（K == 1）{
       returb B：
    }
    其他 {
       N = 2;
       而（N＆LT; K）{
          C = 2 *（A + B）;
          A = B;
          B = C;
          N = N + 1;
       }
       返回℃;
    }
}
 

如果你调用了很多次，你应该考虑保存所有的C的地方，所以你不必每次都重新计算。 我希望我是清楚。否则再问我

Possible Duplicate:
I want to generate the nth term of the sequence 1,3,8,22,60 ,164 in Order(1) or order of (nlogn)
Calculate the nth term of the sequence 1,3,8,22,60,164,448,1224…?

I have a recurrence relation f(n) = 2 * (f(n-1) + f(n-2)). I have to solve for f(k) mod 1000000007 where k is the input. The range of k is 1 <= k <= 1000000000?. I have tried implementing it through simple recursive function, but apparently it causes overflow for large k and hence I encounter a runtime error. I am new to algorithms and stuff, so need to know whether there exists concrete and efficient ways to solve such problems?

#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;
} 

解决方案

First of all you have to define what happen for f(0) and f(1), because at some point you will reach them. Then you can solve it moving forward instead of backward. Start from the 2 and move forward until you reach k in that way:

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;
    }
}

If you call it many times, you should consider save all the c somewhere, so you don't have to recalculate it every time. I hope I was clear enough. Otherwise ask me again

这篇关于算法来求解F（N）= 2 *（F（N-1）+ F（N-2））模1000000007的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！