Comment comprendre ce code dans la réponse d'OJ ?

Question

Description du problème

Une séquence de nombres est définie comme suit :

f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7.

Étant donné A, B et n, vous devez calculer la valeur de f(n).

Entrée

L'entrée se compose de plusieurs cas de test. Chaque cas de test
contient 3 entiers A, B et n sur une seule ligne (1 <= A, B <= 1000, 1
<= n <= 100 000 000). Trois zéros signalent la fin de la saisie et ce
cas de test ne doit pas être traité.

Sortie

Pour chaque cas de test, imprimez la valeur de f(n) sur une seule ligne.

Exemple d'entrée

1 1 3

1 2 10

0 0 0

Exemple de sortie

2

5

#include <iostream>
using namespace std;
int f[54] = {0, 1, 1};
int main()
{
    int A, B, n, q = 1;
    while (cin >> A >> B >> n && A && B && n)
    {
        for (int i = 3; i < 54; ++i)
        {
            f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;   //这里
            if (i > 4)
            {    if (f[i - 1] == f[3] && f[i] == f[4])
                {
                    q = i - 4; //特别是这个地方

                }
            }
        }
        cout << f[n % q] << endl;  //这里

    }

    return 0;
}

Answer 1

N’existe-t-il pas de rapports de résolution de problèmes en ligne ? Cette question recherche des modèles. Le q dans cette question recherche la période T. Quant à savoir pourquoi nous recherchons uniquement les 54 premiers, cela nécessite un raisonnement mathématique rigoureux. Je l'ai testé et j'ai trouvé que 53 est OK, mais pas en dessous de 52.

--------------Digression------------------

Pour ce genre de question, à première vue, c’est comme faire un tableau ou chercher des motifs.

En partant du principe que cette question n'est pas une mauvaise question, il existe certainement deux façons de résoudre ce genre de question : la création violente de tables ou la recherche de modèles. La première signifie que cette question est une grande question, et la seconde signifie que cette question. est une question de raisonnement, n'est-ce pas ? L'eau dépend de la difficulté de raisonnement, mais en ce qui concerne cette question, c'est un gros problème d'eau. Il suffit de regarder les rapports de résolution de problèmes sur Internet. Certaines personnes ouvrent directement le tableau. 1000 jusqu'à ce qu'ils trouvent le point et sautent.

Answer 2

Les discussions suivantes sont restreintesi>=1 :

• Évidemmentf(i) in { 0 .. 6}

• Donc<f(i-2), f(i-1)>cet espace d'état est limité, le maximum ne dépasse pas 49

• Donc f(i) a ses règles, et 49 est une période

• Ensuite, énumérez tout le cycle et trouvez le nombref(n)

  qui se trouve à la même position dans le cycle que

Ajouté :

• q dans votre code n'est pas la période la plus courte. En fait, vous pouvez arrêter lorsque vous trouvez la première période

.

• Il doit être renvoyé lorsque n est un multiple de 49f[0]=0 C'est peut-être un bug