9

F(n)からまでF(m)のフィボナッチ数の合計を計算する最も効率的な方法F(n)とF(m)は、n 番目と m 番目のフィボナッチ数であり、0 =< n <= m <10 9 (F(0)=0、F(1)= の場合) 1)。

たとえば、 の場合n=0、m=3を見つける必要がありますF(0)+F(1)+F(2)+F(3)。

力ずくで と の範囲に到達するには長い時間がかかりnますm。行列累乗を介して実行できる場合、どうすればよいですか?

4

5 に答える 5

22

最初の 2 つの回答 (最も古いもの) は、私には間違っているようです。回答の1つですでに引用されているこの議論によると、最初のnフィボナッチ数の合計は次のようになります。

SumFib(n) = F[n+2] - 1                          (1)

ここで、 からまでのフィボナッチSumFib(m, n)数の合計として定義します(OP で必要な場合) (脚注を参照)。そう：mn 

SumFib(m, n) = SumFib(n) - SumFib(m-1)

2 番目の項に注意してください。SumFib(m)を含むからそうなるのですが、 からを含む までF[m]の合計が必要です。したがって、 sum up toから sum up to を引きます。簡単な幼稚園の算数ですね。F[m]F[n] F[m-1]F[n]:-)

SumFib(m, n) = SumFib(n) - SumFib(m-1)
             = (F[n+2] - 1) - (F[m-1 + 2] - 1)    [using eq(1)]
             = F[n+2] - 1 - F[m+1] + 1
             = F[n+2] - F[m+1]

Therefore, SumFib(m, n) = F[n+2] - F[m+1]                    (2)

例：

m = 3, n = 7
Sum = F[3] + F[4] + F[5] + F[6] + F[7]
    = 2 + 3 + 5 + 8 + 13
    = 31

そして、(2)上記の派生を使用して：

SumFib(3, 7) = F[7+2] - F[3+1]
             = F[9] - F[4]
             = 34 - 3
             = 31

おまけ:とが大きい
場合、フィボナッチ数を生成する効率的なアルゴリズムが必要になります。これは、それを行う1つの方法を説明する非常に優れた記事です。mn

脚注：OPの質問mでnは、この範囲を満たしています：0 =< n <= m、しかし私の答えでは、範囲は少し変更されています0 =< m <= n.

于 2016-12-02T10:35:43.420 に答える
13

「最初の n 個のフィボナッチ数の合計は、(n + 2) 番目のフィボナッチ数から 1 を引いた値である」と仮定します。（おかげで、ウィキペディア）、計算できますF(m + 2) - F(n + 2)（持っているべきではありませんでした。私が見落としていたものについては、Sнаđошƒаӽの回答を-2参照してください）。Binet のフィボナッチ数公式を使用して、 とをすばやく計算します。私にはかなり効率的です。F(m + 2)F(n + 2)

更新: 古い SO の投稿"nth fibonacci number in sublinear time" が見つかりました ( mjvとJim Lewisがコメントで指摘した正確さのため)を計算するための解を実際にエスケープすることはできませんO(n)F(n)。

于 2010-12-05T03:54:17.217 に答える
7

F(m+2) - F(n+2) - 2(協議)

文字通り、上限 m の合計から下限 n の合計を引いたものです。

于 2010-12-05T03:53:13.523 に答える
1

こことここにあるマトリックスプロパティの説明によるアルゴリズム

class Program
{
    static int FibMatrix(int n, int i, int h, int j, int k)
    {
        int t = 0;

        while (n > 0)
        {
            if (n % 2 == 1)
            {
                t = j * h;
                j = i * h + j * k + t;
                i = i * k + t;
            }
            t = h * h;
            h = 2 * k * h + t;
            k = k * k + t;
            n = n / 2;
        }

        return j;            
    }

    static int FibSum(int n, int m)
    {
        int sum = Program.FibMatrix(n, 1, 1, 0, 0);

        while (n + 1 <= m)
        {
            sum += Program.FibMatrix(n + 1, 1, 1, 0, 0);
            n++;
        }

        return sum;
    }

    static void Main(string[] args)
    {
        // Output : 4
        Console.WriteLine(Program.FibSum(0, 4).ToString());

        Console.ReadLine();
    }
}
于 2013-08-07T05:47:20.037 に答える