优化整数序列的非递归算法

Question

在招聘测试平台上，我有以下整数序列问题，我没有使用递归函数来解决它以避免 Stack Overflow :

这里是问题的简短描述：

我们有一个标记，在每个阶段我们都会前进或后退。在第 0 阶段，我们处于位置 0（没有步骤）在第 1 阶段，我们向前迈出一步（+1 步）=> 位置 1 对于第 2 阶段，我们向后退两步（-2 步）=> 位置 -1 对于阶段 n ：我们在前一阶段采取的步数减去我们在倒数第二阶段采取的步数，因此在阶段 3 中，我们将不得不向后采取 3 步 (-2 - 1)。 =>位置-4 等...

目标是将函数 int getPos(int stage) 写入指定阶段的 return 位置。

我用笔和纸找到了这个公式：

位置（n）=步数（n-1）-步数（n-2）+位置（n-1）

这是我的解决方案

#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 case的最大值超时，测试平台说我的解决方案优化不够，无法处理某些情况。

我尝试了 "register" 关键字，但没有效果...

我真的很好奇，我想知道如何编写优化函数。我应该更改算法（如何更改？）还是使用一些编译器调优？

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;

优化整数序列的非递归算法

optimizing a non recursive algorithm of an integer sequence

c++

algorithm

recursion

compiler-optimization

non-recursive