は、採用テストプラットフォームで整数列

Question

の非再帰的なアルゴリズムを最適化し、私はスタックオーバーフローを避けるために、再帰関数せずにそれを解決するため、次の整数のシーケンスに問題があった：

ここで、問題の簡単な説明です：

マークがあり、各段階で前後に移動します。 ステージ0ではポジション0（ステップなし） ステージ1では1ステップ進みます（+1ステップ）=>ポジション1 ステージ2では2ステップ後方（-2ステップ）=>ポジション-1 ステージn：前のステージで取ったステップの数から2番目の最後のステージで取ったステップの数を引いたもので、ステージ3では3ステップ後方（-2 - 1）にする必要があります。 =>位置-4 など...

目的は、指定されたステージの位置を返すために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型の例最大値は、プロセスをタイムアウトし、テストプラットフォームは、私の解決策は、いくつかのケースを処理するのに十分に最適化されていないと述べました。

私は「登録」のキーワードを試してみましたが、それは効果がありません...

私は本当に好奇心旺盛だと私は私が（どのように？）アルゴリズムを変更する最適化機能.Shouldの書き方を知りたいですかいくつかのコンパイラチューニングを使用しますか？

Answer 1

我々は...我々は、ステップ6で0、ステップ1 =ステップ7、ステップ2 =ステップ7のステップに等しいことが確認でき

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 

を最初の段階を書き込みますだから、答えXステップのためのステップは、本当にAMAだあなたは

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