Найти сумму первых n чисел Фибоначчи

Question

Задание: для натурального числа n (в данном случае это 8 и 11) найти значение результата равного первым n чисел Фибоначчи. Я пытался сделать по такому коду, но оно вместо этого выводит 32 и 143. Второй результат правильный но первый почему-то нет:

    int n0 = 0;
    int n1 = 1;
    int n2 = 1;
    int result = n;

for(int i=2; i<n; i++) {
    result = n1 + n0 + n1;
    n0 = n1;
    n1= n2;
    n2 = result+1;
}


    return result;

Answer 1

Имхо, проще пробежаться по числам Фибоначчи и вычислить их сумму. Пример на C#

int getFibSum(int n)
{
    if (n == 1) return 0;
    if (n == 2) return 1;

    int n1 = 0;
    int n2 = 1;
    int ret = 1;

    for (int i = 3; i <= n; i++)
    {
        var n3 = n1 + n2;
        ret += n3;
        n1 = n2;
        n2 = n3;
    }

    return ret;
}

Проверка

Console.WriteLine(getFibSum(8));
Console.WriteLine(getFibSum(11));

Вывод

33
143

Answer 2

Как известно, сумма N чисел Фибоначчи от F(1) до F(N) равна F(N + 2) - 1, поэтому для её вычисления достаточно вызвать метод для вычисления обычного числа Фибоначчи.

public static long sumF(long n) {
    return fib(n + 2) - 1; // или fibRec(n + 2) - 1
}

// рекурсивное вычисление
public static long fibRec(long n) {
    if (n < 2) return n;
    return fibRec(n - 1) + fibRec(n - 2);
}

// итеративное вычисление
public static long fib(long n) {
    if (n < 2) return n;
    long a = 0, b = 1, f = 1;
    for (int i = 1; i < n; i++) {
        f = a + b;
        a = b;
        b = f;
    }
    return f;
}

Тест:

System.out.println(sumFib(8));  // -> 54 
System.out.println(sumFib(11)); // -> 232

Для вычисления суммы N чисел, начиная с F(0) = 0, достаточно изменить формулу на F(N + 1) - 1:

public static long sumFfrom0(long n) {
    return fib(n + 1) - 1; // или fibRec(n + 1) - 1
}

Answer 3

Давайте посчитаем сумму первых чисел Фибоначчи.

У ряда есть два варианта, оба встречаются часто, поэтому мы можем выбрать любой. Первый ряд начинается с 0, 1, 1, 2...; второй — с 1, 1, 2, 3...

Пусть у нас будет первый ряд.

n	Fib(n)	Sum(Fib(n))
0	0	0
1	1	1
2	1	2
3	2	4
4	3	7
5	5	12
6	8	20
7	13	33
8	21	54
9	34	88

Мы видим формулу, про которую сказано в соседнем ответе: Sum(Fib(n)) = Fib(n + 2) - 1. Я заинтересовался, откуда это известно.

Мне показалось что её легко вывести по индукции.

Предположим, что Sum(Fib(n)) = Fib(n + 2) - 1 для какого то n.

Тогда Sum(Fib(n + 1)) = Sum(Fib(n)) + Fib(n + 1). Если верно первое равенство, то второе равенство равно Fib(n + 2) - 1 + Fib(n + 1). Но Fib(n + 1) + Fib(n + 2) = Fib(n + 3), следовательно, второе равенство это Fin(n + 3) - 1. Следовательно, Sum(Fib(n + 1)) = Fib(n + 3) - 1. Обозначив n + 1 = m, можем записать его как Sum(Fib(m)) = Fib(m + 2) - 1.

Шаг индукции мы доказали. Убедимся, что Sum(Fib(n)) = Fib(n + 2) - 1 для n = 0, 1, 2, 3... Из таблицы выдим, что это так.

Так что да, простейший способ это формула, доказанная по индукции. Либо можете посчитать сумму вручную:

public class MyClass {
    static final int N = 9;
    
    public static void main(String args[]) {
        int a = 0;
        int b = 1;
        int sum = a + b;
        for (int i = 2; i <= N; i++) {
            int t = a;
            a = b;
            b = t + b;
            sum += b;
        }
        
        System.out.format("Sum(Fib(%d)) = %d", N, sum); // => 88
    }
}

Всё, как в таблице.

БЛОГ НА HUSL

Найти сумму первых n чисел Фибоначчи

Ответы (3 шт):