降低c 中類似斐波那契函式的遞回時間復雜度

我一直在嘗試用c 撰寫一個問題的解決方案。

這個問題必須只用遞回來解決。 modulo 10000000007并不是問題，有/沒有modulo，代碼都要花費更多的時間

問題是：在使用modulo的情況下，代碼需要更長的時間。

這個問題。 戴維斯喜歡在每個樓梯上一次爬1、2或3步。

給定n個樓梯各自的高度，找出并列印他能爬上每個樓梯的次數，以10^10 7為模數

示例

例證 對于n=5

該樓梯有5個臺階。戴維斯可以踏上以下的臺階序列：

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1

2 1 1 1

2 1 1 1

1 2 2

2 2 1

2 1 2

1 1 3

1 3 1

3 1 1

2 3

3 2

他有13種可能的方式可以采取這5個步驟，13個modulo 10000000007=13

int ways（int n） {
    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;
    return (ways(n-3) ways(n-2） ways（n-1））%10000000007。
}

這段代碼作業得很好，但在大的計算中花費的時間太長了。 如果有什么方法可以優化它，請分享。 越簡單的解決方案越好。 謝謝。

uj5u.com熱心網友回復：

你可以開始添加記憶化，以避免大部分的遞回呼叫。

long long ways(long long n)
{
    // Memoization需要存盤之前的計算值。
    static std::map<long long, long long> mem{
        {1, 1}, {2, 2}, {3, 4}.
    };

    // I'm using std::map, but I don't want to use operator[], nor find... 
    //https://en.cppreference.com/w/cpp/container/map/operator_at
    //https://en.cppreference.com/w/cpp/container/map/find
    //https://en.cppreference.com/w/cpp/container/map/lower_bound
    auto it = mem.lower_bound（n）。

    //如果它已經被計算過了，回傳存盤的值。
    if ( it != mem.cend() and it-> first == n )
        return it->second;

    //否則評估新值（遞回）并存盤它。
    //注意，我可以使用迭代器作為插入的提示。
    //https://en.cppreference.com/w/cpp/container/map/emplace_hint
    return mem.emplace_hint(
        it, n,
        (途徑(n-3)   途徑(n-2)   ways(n-1) ) % 10000000007)
    )->第二。
}

如果這還不夠，你將不得不尋找一些數學技巧，或者干脆完全避免遞回，使用一個簡單的回圈。

uj5u.com熱心網友回復：

該演算法計算一個自定義的Tribonacci序列模數10000000007。這可以在O(log n)時間和O(1)空間的基礎上非常有效地計算，就像Fibonacci序列的矩陣表示。更多資訊請參見這篇文章和這個答案。

這種方法對于大的輸入來說是非常快的（比使用記憶化快得多），而且非常節省記憶體。

然而，有一個問題：該實作需要計算兩個 64 位整數與一個 64 位整數的乘法（除非模子可以裝入一個 32 位整數）。大多數平臺不支持128位整數，但可以使用boost::multiprecision。更多資訊請參見這篇文章。

下面是一個實作。

下面是一個實作：

int64_t int128_mulMod(int64_t a。int64_t b, int64_t mod) 
{
    return int64_t（（int128_t(a) * int128_t(b)) % int128_t(mod)）。)
}

//計算a * b的矩陣乘法，并將結果放入a。
void matMulMod(int64_t a[3][3] 。int64_t b[3][3], int64_t mod）
{
    int64_t res[3][3] = {};

    for(int i=0 ; i<3;   i)
        for(int j=0; j<3;   j)
            for(int k=0; k<3;   k)
                res[i][j]  = int128_mulMod（a[i][k], b[k][j], mod）。

    for(int i=0 ; i<3;   i)
        for(int j=0; j<3;   j)
            a[i][j] = res[i][j]。
}

//計算矩陣指數化a^n，并將結果放入a中。
void matPowMod(int64_t a[3][3] 。int64_t n, int64_t mod) 
{
    if(n == 0 || n == 1)
        return;

    int64_t m[3][3] = {{ 1, 1, 1 },
                       { 1, 0, 0 },
                       { 0, 1, 0 } }。

    //使用遞回來有效地對矩陣進行平方。
    matPowMod(a, n / 2, mod) 。

    //對矩陣進行平方處理。
    matMulMod（a, a, mod）。

    //剩余情況
    if(n % 2)
        matMulMod（a, m, mod）。

    //在每個項上應用模數以防止溢位。
    for(int i=0 ; i<3;   i)
        for(int j=0; j<3;   j)
            a[i][j] %= mod。
}

int64_t ways_fast（int64_t n）
{
    int64_t a[3][3] = {{ 1, 1, 1 },
                       { 1, 0, 0 },
                       { 0, 1, 0 } }。

    if(n==1) return 1;
    if(n==2) return 2;
    if(n==3) return 4;

    matPowMod（a, n, 10000000007ll）。
    return a[0][0]; // Tribonacci序列的結果。
}

例如，在我的機器上，ways_fast(30'000)比@Bob__提供的基于備忘錄的方法計算快100倍。此外，當計算ways(60'000)時，記憶化演算法崩潰了，而ways_fast(200'000)卻能正常作業。

更多資訊，請閱讀：

標籤：

上一篇：如何計算一個圍繞中心旋轉的矩形的邊界盒？

下一篇：尋找到達給定坐標所需的最小速度？