算法來求解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

回答

相關問題