2

次の形式の収束級数を考えてみましょう。

sum(((-1)^n)*something)

ここnで、は反復のインデックスです（nから1へinfinity）。

式を直接実装する場合、std::pow(-1, n)それはありますが、それを実装するためのより「迅速な」アルゴリズムのトリックはありますか？

4

5 に答える 5

13

n偶数か奇数かを確認し、

(n % 2 == 0) ? 1 : -1;

それをします。分岐を避けたい場合は、

1 - 2*(n & 1)
于 2013-01-05T23:36:35.927 に答える
6

sum(((-1)^n)*something)これは擬似コードであり、nsumによってバインドされる変数であると想定しています。

その表記をに拡張してみましょうsum(n <- [0,1,2,3..], ((-1)^n)*f(n))。おそらく、最初にこれを2つの合計に分割し、それらを合計するのが最善の選択肢です。

sum(n <- [0,2..], ((-1)^n)*f(n)) + sum(n <- [1,3..], ((-1)^n)*f(n))

最初の項では、nは常に偶数であるため、(-1)^n常にになります+1。同様に、第2項では、常にになります-1。これで、これを次のように書き直すことができます。

sum(n <- [0,2..], f(n)) + sum(n <- [1,3..], -f(n))

2番目の合計のすべての項に定数が乗算されるため、その定数を合計から移動できます。

sum(n <- [0,2..], f(n)) - sum(n <- [1,3..], f(n))

2*mここで、これらの合計が同じインデックスシーケンスを取り、と2*m+1をn次のように置き換えていることを確認しましょう。

sum(m <- [0,1..], f(2*m)) - sum(m <- [0,1..], f(2*m+1))

これで、これらの合計を再び結合できます。

sum(m <- [0,1..], f(2*m) - f(2*m+1))

または、疑似Cが必要な場合：

T result = 0;
for(m = 0; m < limit; m+=2) {
    result += f(m);
    result -= f(m+1);
}

これにより、ほとんどの人がここで示唆しているように、+1またはによる乗算を節約できます。-1シーケンスは収束しているので、余分な項をとっても、答えの正しさに悪影響を与えることはありません。

于 2013-01-06T00:03:06.460 に答える
1

ええ、魔法のトリックがあります：偶数の(-1)^n == 1場合に限りn、そして奇数の(-1)^n == -1場合にのみn。したがって：

int p = (n % 2 == 0) ? 1 : -1;
sum(p*something)
于 2013-01-05T23:38:22.840 に答える
1

この用語は、奇数または偶数の場合に((-1)^n)*something評価されます。-somethingnsomethingn

n & 1 ? -something : something

somethingが定数値の場合、の最後の値が奇数のとき、または偶数の被加数に対してsum(((-1)^n)*something)評価されます。-somethingn0

n & 1 ? -something : 0

この場合、シリーズは収束しません。

于 2013-01-05T23:39:48.050 に答える
1

これをループで実行している場合は、次のようにすることができます。

x = 1;   // Assuming we start on n = 0
for(...)    // or while(...)
{
   sum += x * something;

   x = -x;
}

これは、nのチェックを実行するよりもはるかに高速である可能性があります。もちろん、n個の値すべてが繰り返されることを前提としており、あちこちでいくつかスキップすることはありません...

于 2013-01-05T23:46:12.493 に答える