この回答の "q = i - 4;"のコードを理解するにはどうすればよいですか？

Question

問題が説明

数列次のように定義される：

A、Bを考える

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

、およびnは、F（n）の値を計算することです。

入力

入力は、複数のテストケースから構成されています。各テストケースには、1行に3つの整数A、B、およびnが含まれています（1 < = A、B < = 1000、1 < = n < = 100,000,000）。 3つのゼロは入力の終わりを知らせ、このテストケースは処理されません。

各テストケースに対する出力

、単一ライン上のF（n）の値を印刷します。

サンプル入力

1 1 3 
1 2 10 
0 0 0 

サンプル出力

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]) //here too 
       { 
        q = i - 4; //I can't catch the point 
       } 
      } 
     } 
     cout << f[n % q] << endl; 

    } 
    return 0; 
} 

Answer 1

はい、この種の問題はOnlineJudge（OJ）の問題です。あなたはACMのために新しいかもしれませんか？

吹いたが私の答えです：

答えがこれだけ問題がループし、0、1、2、3、4、5、6だから、可能性を意味するのでmod 7、解決策は機能しなかった理由すべてのことですそれだけで3から54までです。 f [n]はf [n-1]とf [n-2]の前の2つの値でのみ決定されるため、f [n-1] n-2]となる。

f [n-1]とf [n-2]がf [4]とf [3]に等しい場合、49以上のループがあれば、以下の値が循環します。

2つ目の例を見てみましょう。

f[1] = 1 
f[2] = 1 
A = 1 
B = 2 
n = 10 // or set n larger. 

我々はf[9] == f[3]とf[10] == f[4]など

f[3] = 3 
f[4] = 5 
f[5] = 4 
f[6] = 0 
f[7] = 1 
f[8] = 1 
f[9] = 3 
f[10] = 5 
f[11] = 4 

を取得します、それは数字で、その後の後に循環、4, 0, 1, 1, 3, 5、

なりますのでq = i - 4は、最初の4つの数字を除去し、それn%qなどは循環順序におけるn番目の数の位置です。

私は答えを明確に述べているのだろうか、これがあなたに役立つことを願っています。

Answer 2

f(n)が完全f(n - 1)とf(n - 2)によって決定され、任意f(x)は0から6の整数であることを考えると、f(n - 1)とf(n - 2)のみ7×7 = 49の組み合わせが存在します。つまり、f(x)は期間が最大49で定期的です。期間がわかるとf(n)はf(0)..f(48)と計算されているので、f(n % period)と同じくらい簡単です。正確な期間はAとBに依存し、計算する必要があります。期間を計算するには、単に2つの連続する値の繰り返しを見つける必要があります。fすなわち、f(x) == f(y) && f(x + 1) == f(y + 1)の場合、|y - x|は、fの期間またはその整数倍です。 f(n) == f(n % (k*period))はf(n) == f(n % period)と同様に機能します。だから、問題のコードでqは、fの周期かそれの整数倍です。

コードはf(0)..f(48)ではなく、f(0)..f(53)を事前計算するのはなぜですか？私はそれが過度だと思う。なぜなら、最大期間を超えて2つの余分な要素が十分であるからである。

問題のコードに関するもう1つの問題は、nがqの倍数である場合に返される可能性のある偽の値であるということです。それは潜在的にバグです。それが起こらないように、私はfのインデックスをf(1) == 1 && f(2) == 1ではなくf(0) == 1 && f(1) == 1とすることで1つずつシフトします。