优化整数序列

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;