-2

在招聘测试平台中，我遇到了以下整数序列问题，我在没有递归函数的情况下解决了它以避免堆栈溢出：

这是问题的简短描述：

我们有一个标记，在每个阶段我们都会向前或向后移动。在第 0 阶段，我们处于位置 0（无步骤） 在第 1 阶段，我们向前走一步（+1 步）=> 位置 1 对于第 2 阶段，我们向后走两步（-2 步）=> 位置 -1 对于第 n 阶段：我们在前一个阶段采取的步数减去我们在倒数第二个阶段采取的步数，所以在第 3 阶段，我们将不得不向后退 3 步（-2 - 1）。=>位置-4等...

目标是编写函数 int getPos(int stage) 以返回指定阶段的位置。

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

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

我尝试了“注册”关键字，但它没有效果......

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

4

1 回答 1

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;
于 2017-03-03T13:54:16.543 回答