算法来求解F（N）= 2 *（F（N-1）+ F（N-2））模1000000007

-1

可能重复：
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…?算法来求解F（N）= 2 *（F（N-1）+ F（N-2））模1000000007

我有一个递归关系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; 
}

来源

2012-07-05 jigsawmnc

告诉我们你有什么试过的。什么是基本情况？ – Mark

每次有人在评论中发布代码 - 抛出异常... – alfasin

srry！...这是一个错误！我不是故意的，加上互联网在这里吸取 – jigsawmnc

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

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

这就给了你，假设模（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-05 08:09:38

首先你必须定义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-05 08:12:57

算法来求解F（N）= 2 *（F（N-1）+ F（N-2））模1000000007

回答

相关问题