Maison > Questions et réponses > le corps du texte
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;
}
给我你的怀抱2017-06-24 09:44:59
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.
曾经蜡笔没有小新2017-06-24 09:44:59
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)
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