24

次の再帰関係のプログラムを書いています。

An = 5An-1 - 2An-2  - An-3 + An-4

出力は、答えの係数 10^9 + 7 である必要があります。次のように、これに対するブルート フォース アプローチを作成しました...

long long int t1=5, t2=9, t3=11, t4=13, sum;
while(i--)
{
    sum=((5*t4) - 2*t3 - t2 +t1)%MOD;
    t1=t2;
    t2=t3;
    t3=t4;
    t4=sum;
}
printf("%lld\n", sum);

ここで、MOD= 10^9 +7 すべてが正しいように見えます..しかし、いくつかの値に対して否定的な答えが返されます..そして、この問題のために、正しい解決策を見つけることができません.Modulus

4

5 に答える 5

41

問題は、% 演算子が「モジュロ演算子」ではなく、次の等号を持つ「除算剰余」演算子であるということです。

(a/b)*b + a%b == a    (for b!=0)

したがって、整数除算がゼロに向かって丸められる場合 (これは C99 および C++11 以降で義務付けられていると思います)、-5/4 は -1 になり、次のようになります。

(-5/4)*4 + -5%4 == -5
  -1  *4    -1  == -5

(モジュロ演算で) 正の結果を得るには、剰余が負の場合に除数を追加するか、次のようにする必要があります。

long mod(long a, long b)
{ return (a%b+b)%b; }
于 2012-09-05T08:18:59.693 に答える
11

%@sellibitze と @liquidblueocean の回答で 2 回目の使用は、1 回の減算またはゼロのいずれかに要約されるため、一般的に傾向があるほど遅くはないでしょ%うb。実際、ちょっと確認させてください...

int main(int argc, char **argv) {
    int a = argc;    //Various tricks to prevent the
    int b = 7;       //compiler from optimising things out.
    int c[10];       //Using g++ 4.8.1
    for (int i = 0; i < 1000111000; ++i)
        c[a % b] = 3;
        //c[a < b ? a : a-b] = 3;
    return a;
}

%あるいは、または他の行にコメントを付けると、次のようになります。

  • あり%：14秒

  • あり?：7秒

だから%私が思ったほど最適化されていません。おそらく、その最適化によりオーバーヘッドが追加されるためです。

したがって、%パフォーマンス上の理由から、2 回使用しないことをお勧めします。

代わりに、この回答が示唆および説明しているように、次のようにします。

int mod(int k, int n) {
    return ((k %= n) < 0) ? k+n : k;
}

ネガティブでも適切に機能させたい場合nは、もう少し作業が必要ですが、それはほとんど必要ありません。

于 2014-04-22T08:22:07.893 に答える
5

%負の値を処理する関数に置き換えるだけです。

long long int mod(long long int a, long long int b) {
    long long int ret = a % b;
    if (ret < 0)
        ret += b;
    return ret;
}

編集: データ型を に変更しましたlong long int。

于 2012-09-05T07:44:52.033 に答える
3

abs(a) > b. これまたは類似のものを使用します。

int modulo (int a, int b) { return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b; }
于 2014-01-31T00:17:53.133 に答える
1

他の人が言ったよう%に、 ではなく単なる剰余演算子ですmod。ただし、mod/remainder 操作は、このような再帰関係を通じて正しく分配されるため、このように最終解が正になるように調整すると、

if (sum < 0) { sum = sum + MOD; }

そうすれば、正しい答えが得られるはずです。この方法の利点は、ループの反復ごとに関数呼び出しや分岐が 1 つ少なくなることです。（コンパイラがどれほど賢いかによって、問題になる場合とそうでない場合があります）。

于 2012-09-05T08:33:45.303 に答える