Нахождение суммы чисел Фибоначчи

Question

Какой самый эффективный способ вычислить сумму чисел Фибоначчи от F(n) до F(m), где F(n) и F(m) - n-е и м-е числа Фибоначчи соответственно и 0 = 9 (с F (0) = 0, F (1) = 1).

Например, если n=0, m=3, нам нужно найти F(0)+F(1)+F(2)+F(3).

Просто грубой силой потребуется много времени для упомянутого диапазона n и m. Если это можно сделать с помощью матричного возведения в степень, то как?

Answer 1

Первые два ответа (самые старые) кажутся неверными для меня. Согласно этой дискуссии , которая уже упоминалась в одном из ответов, сумма первых n чисел Фибоначчи определяется как:

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

Теперь давайте определим SumFib(m, n) как сумму чисел Фибоначчи от m до n включительно (согласно требованиям OP) (см. Сноску). Итак:

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

Обратите внимание на второй член. Это так, потому что SumFib(m) включает F[m], но мы хотим сумму от 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)

* 1 028 * Пример:

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

---

Бонус:
Когда m и n велики, вам нужны эффективные алгоритмы для генерации чисел Фибоначчи. Вот очень хорошая статья , которая объясняет один из способов сделать это.

---

Сноска: В вопросе m и n ОП удовлетворяют этому диапазону: 0 =< n <= m, но в моем ответе диапазон немного изменен, он 0 =< m <= n.

Answer 2

Учитывая, что «сумма первых n чисел Фибоначчи является (n + 2) -ым числом Фибоначчи минус 1». (спасибо, Википедия ), вы можете рассчитать F(m + 2) - F(n + 2) (не должно было быть -2, см. ответ Snađошƒаӽ за то, что я пропустил ). Используйте числовую формулу Фибоначчи Бине для быстрого вычисления F(m + 2) и F(n + 2). Кажется довольно эффективным для меня.

Обновление: найдено старое сообщение SO, "n-е число Фибоначчи в сублинейном времени" и (из-за точности, как указали mjv и Джим Льюис в комментариях), вы не можете избежать O(n) решения для расчета F(n).

Answer 3

F(m+2) - F(n+2) - 2 ( обсуждение )

Буквально сумма вашей верхней границы m, минус сумма вашей нижней границы n.

Answer 4

Ответ:

f(m+2)-f(n+1)

Пример:

for n = 3 to m = 8

Ans1 = f(m+2) = f(10) = 55

Ans2 = f(n+1) = f(4) = 3 

Answer = 55 - 3 = 52

Теперь для вычисления N-го Фибоначчи в O (logN) вы можете использовать матричный метод возведения в степень

Ссылка: - http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

Answer 5

Алгоритм с помощью объяснения свойства матрицы найден здесь и здесь

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();
    }
}