優化整數序列

Question

在招募測試平臺的非遞歸算法，我有我解決這個問題沒有一個遞歸函數來避免堆棧溢出以下的整數序列問題：

這裏有一個問題的簡短描述：

我們有一個標誌，在每個階段我們會前進或後退。 在階段0中，我們處於位置0（無步驟） 在階段1中，我們向前邁進一步（+1步驟）=>位置1 對於階段2，我們向後兩步（-2步）=>位置-1 對於階段n：我們在前一階段採取的步驟數量減去了我們在第二階段採取的步驟數量，所以在階段3中，我們將不得不向後退步（-2 - 1）3個步驟。 => position -4 etc ...

目標是編寫函數int getPos（int stage）以返回指定階段的位置。

用筆和紙我發現這個公式：

位置（N）=步驟（N-1） - 步驟（N-2）+位（n-1）

adnd這裏的我的解決方案

#include <iostream> 

using namespace std; 

int getPos(int stage) 
{ 
    if (stage < 2) 
     return stage; 

    if (stage == 2) 
     return -1; 

    int stepNMinus1 = -2; 
    int stepNMinus2 = 1; 
    int stepN = 0; 
    int posNMinus1 = -1; 
    int Res = 0; 

    while (stage-- > 2) 
    { 
     stepN = stepNMinus1 - stepNMinus2; 
     Res = stepN + posNMinus1; 
     stepNMinus2 = stepNMinus1; 
     stepNMinus1 = stepN; 
     posNMinus1 = Res; 
    } 

    return Res; 
} 

int main() 
{ 
    cout << "Pos at stage -1 = " << getPos(-1) << endl; // -1 
    cout << "Pos at stage 0 = " << getPos(0) << endl; // 0 
    cout << "Pos at stage 1 = " << getPos(1) << endl; // 1 
    cout << "Pos at stage 2 = " << getPos(2) << endl; //-1 
    cout << "Pos at stage 3 = " << getPos(3) << endl; // -4 
    cout << "Pos at stage 4 = " << getPos(4) << endl; // -5 
    cout << "Pos at stage 5 = " << getPos(5) << endl; // -3 
    cout << "Pos at stage 100000 = " << getPos(100000) << endl; // -5 
    cout << "Pos at stage 2147483647 = " << getPos(2147483647) << endl; // 1 
} 

通過平臺的測試執行測試程序後，一個int案件的最大值超時過程和測試平臺，說我的解決方案是不足夠的優化，來處理一些案件。

我嘗試了「註冊」關鍵字，但它沒有任何效果...

我真的很好奇，我想知道如何編寫一個函數優化我。應該改變算法（如何？）或使用一些編譯器調音？

Answer 1

我們將寫在第一階段

Stage | Step | Position 
0  | 0  | 0 
1.  | 1  |1 
2  |-2  | -1 
3  |-3  |-4 
4  |-1  |-5 
5  |2  |-3 
6  |3  |0 
7  |1  |1 
8  |-2  |-1 

我們可以看到，在第6步中是等於0的步驟，步驟1 =步驟7，步驟2 =步驟7中，...

因此，對於步驟x答案是步驟（x％6）

你可以做

cout << "Pos at stage x = " << getPos((x%6)) << endl;