l'optimisation d'un algorithme non récurrent d'une séquence entière

Question

Dans une plate-forme de test de recrutement, j'ai eu le problème de la séquence entière suivante que je résous sans fonction récursive pour éviter débordement de la pile:

Voici une brève description du problème:

Nous avons une marque et à chaque étape nous allons avancer ou reculer. Dans l'étape 0 nous sommes en position 0 (pas d'étapes) Dans l'étape 1, nous faisons un pas en avant (+1 pas) => position 1 Pour l'étape 2, nous faisons deux pas en arrière (-2 pas) => position -1 Pour l'étape n: le nombre de pas que nous avons pris sur l'étape précédente moins le nombre de pas que nous avons pris sur l'avant-dernière étape, donc sur l'étape 3, nous devrons reculer de 3 pas (-2 - 1). => position -4 etc ...

Le but est d'écrire la fonction int getPos (int stage) pour renvoyer la position à l'étape indiquée.

avec un stylo et un papier je trouve cette formule:

la position (n) = étapes (n-1) - les étapes (n-2) + poste (n-1)

ADND voici ma solution

#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 
} 

Après l'exécution du programme de test par l'intermédiaire du test de plate-forme, la valeur maximale d'un cas d'int a expiré le processus et la plate-forme de test dit que ma solution n'a pas été optimisée suffisante pour gérer certains cas.

J'ai essayé le mot-clé « enregistrer », mais il n'a pas d'effet ...

Je suis vraiment curieux et je veux savoir comment écrire une fonction optimisée .Should-je changer l'algorithme (comment?) Ou utiliser des ajustements de compilateur?

Answer 1

Nous allons écrire les premières étapes

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 

On peut voir que, dans l'étape 6 est égale à l'étape 0, étape 1 = étape 7, étape 2 = étape 7, ...

Donc, pour l'étape x la réponse est l'étape (x% 6)

Vous pouvez faire

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