Рубрики

Сумма чисел Фибоначчи

Учитывая число положительное число n, найти значение f 0 + f 1 + f 2 +…. + f n, где f i указывает i- е число Фибоначчи. Помните, что f 0 = 0, f 1 = 1, f 2 = 1, f 3 = 2, f 4 = 3, f 5 = 5,…
Примеры :

Input  : n = 3
Output : 4
Explanation : 0 + 1 + 1 + 2  = 4

Input  :  n = 4
Output :  7
Explanation : 0 + 1 + 1 + 2 + 3  = 7

Метод 1 (O (n))
Подход грубой силы довольно прост, найдите все числа Фибоначчи до f (n) и затем сложите их.

C ++

// C ++ Программа для поиска суммы чисел Фибоначчи
#include<bits/stdc++.h>

using namespace std;

  
// Вычисляет значение первых чисел Фибоначчи

int calculateSum(int n)

{

    if (n <= 0)

       return 0;

  

    int fibo[n+1];

    fibo[0] = 0, fibo[1] = 1;

  

    // Инициализировать результат

    int sum = fibo[0] + fibo[1];

  

    // Добавить оставшиеся условия

    for (int i=2; i<=n; i++)

    {

        fibo[i] = fibo[i-1]+fibo[i-2];

        sum += fibo[i];

    }

  

    return sum;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int n = 4;

    cout << "Sum of Fibonacci numbers is : "

         << calculateSum(n) << endl;

    return 0;

}

Джава

// Java-программа для поиска
// сумма чисел Фибоначчи

  

import java.io.*;

  

class GFG {

      

    // вычисляет значение первого

    // числа Фибоначчи

    static int calculateSum(int n)

    {

        if (n <= 0)

           return 0;

       

        int fibo[]=new int[n+1];

        fibo[0] = 0; fibo[1] = 1;

       

        // Инициализировать результат

        int sum = fibo[0] + fibo[1];

       

        // Добавить оставшиеся условия

        for (int i=2; i<=n; i++)

        {

            fibo[i] = fibo[i-1]+fibo[i-2];

            sum += fibo[i];

        }

       

        return sum;

    }

       

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        int n = 4;

        System.out.println("Sum of Fibonacci"

        " numbers is : "+ calculateSum(n));

    }

}

  
// Этот код предоставлен Никитой Тивари.

python3

# Python 3 Программа для поиска
# сумма чисел Фибоначчи

  

  
# Вычисляет значение первого
# числа Фибоначчи

def calculateSum(n) :

    if (n <= 0) :

        return 0

   

    fibo =[0] * (n+1)

    fibo[1] = 1

   

    # Инициализировать результат

    sm = fibo[0] + fibo[1]

   

    # Добавить оставшиеся условия

    for i in range(2,n+1) :

        fibo[i] = fibo[i-1] + fibo[i-2]

        sm = sm + fibo[i]

          

    return sm

  

  
# Драйвер программы для тестирования
# выше функция

n = 4

print("Sum of Fibonacci numbers is : " ,

      calculateSum(n))

  
# Этот код добавлен
# Никита Тивари.

C #

// C # Программа для поиска
// сумма чисел Фибоначчи

using System;

  

class GFG 

{

      

    // вычисляет значение первого

    // числа Фибоначчи

    static int calculateSum(int n)

    {

        if (n <= 0)

        return 0;

      

        int []fibo = new int[n + 1];

        fibo[0] = 0; fibo[1] = 1;

      

        // Инициализировать результат

        int sum = fibo[0] + fibo[1];

      

        // Добавить оставшиеся условия

        for (int i = 2; i <= n; i++)

        {

            fibo[i] = fibo[i - 1] + fibo[i - 2];

            sum += fibo[i];

        }

      

        return sum;

    }

      

    // Код драйвера

    static void Main()

    {

        int n = 4;

        Console.WriteLine( "Sum of Fibonacci"

                              " numbers is : "

                              calculateSum(n));

    }

}

  
// Этот код предоставлен Anuj_67

PHP

<?php
// PHP программа для поиска суммы
// чисел Фибоначчи

  
// вычисляет значение первого
// числа Фибоначчи

function calculateSum($n)

{

    if ($n <= 0)

    return 0;

  

    $fibo[0] = 0;

    $fibo[1] = 1;

  

    // Инициализировать результат

    $sum = $fibo[0] + $fibo[1];

  

    // Добавить оставшиеся условия

    for($i = 2; $i <= $n; $i++)

    {

        $fibo[$i] = $fibo[$i - 1] + 

                    $fibo[$i - 2];

        $sum += $fibo[$i];

    }

  

    return $sum;

}

  

    // Код драйвера

    $n = 4;

    echo "Sum of Fibonacci numbers is : ",

          calculateSum($n),"\n";

  
// Этот код предоставлен aj_36
?>

Выход :

Sum of Fibonacci numbers is : 7

Метод 2 (O (Log n))
Идея состоит в том, чтобы найти взаимосвязь между суммой чисел Фибоначчи и n-м числом Фибоначчи.

F (i) относится к i -му числу Фибоначчи.
S (i) относится к сумме чисел Фибоначчи до F (i),

We can rewrite the relation F(n+1) = F(n) + F(n-1) as below
F(n-1)    = F(n+1)  -  F(n)

Similarly,
F(n-2)    = F(n)    -  F(n-1)
.          .           .
.          .             .
.          .             .
F(0)      = F(2)    -  F(1)
-------------------------------

Сложив все уравнения, с левой стороны получим
F (0) + F (1) +… F (n-1), то есть S (n-1).

Следовательно,
S (n-1) = F (n + 1) — F (1)
S (n-1) = F (n + 1) — 1
S (n) = F (n + 2) — 1 — (1)

Чтобы найти S (n), просто вычислите (n + 2) -ое число Фибоначчи и вычтите 1 из результата.

F (n) можно оценить за O (log n), используя метод 5 или метод 6 из этой статьи (см. Методы 5 и 6).

Ниже приведена реализация, основанная на способе 6 этого

C ++

// C ++ Программа для поиска суммы чисел Фибоначчи в
// O (Log n) время.
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000;

  
// Создать массив для запоминания

int f[MAX] = {0};

  
// Возвращает n-е число Фибоначчи, используя таблицу f []

int fib(int n)

{

    // Базовые случаи

    if (n == 0)

        return 0;

    if (n == 1 || n == 2)

        return (f[n] = 1);

  

    // Если fib (n) уже вычислен

    if (f[n])

        return f[n];

  

    int k = (n & 1)? (n+1)/2 : n/2;

  

    // Применяем вышеприведенную формулу [Примечание: значение n & 1 равно 1

    // если n нечетно, иначе 0].

    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))

           : (2*fib(k-1) + fib(k))*fib(k);

  

    return f[n];

}

  
// Вычисляет значение первых чисел Фибоначчи

int calculateSum(int n)

{

    return fib(n+2) - 1;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int n = 4;

    cout << "Sum of Fibonacci numbers is : "

         << calculateSum(n) << endl;

    return 0;

}

Джава

// Java-программа для поиска суммы
// чисел Фибоначчи в
// O (Log n) время.

import java.io.*;

import java.util.*;

  

class GFG {

    static int MAX = 1000;

  

    // Создать массив для запоминания

    static int f[] = new int[MAX];

      

    // Возвращает n-й Фибоначчи

    // номер с использованием таблицы f []

    static int fib(int n)

    {

        Arrays.fill(f, 0);

        // Базовые случаи

        if (n == 0)

            return 0;

        if (n == 1 || n == 2)

            return (f[n] = 1);

      

        // Если fib (n) уже вычислен

        if (f[n] == 1)

            return f[n];

            int k;

        if((n & 1) == 1

            k = (n + 1) / 2 ;

        else

            k = n / 2;

      

        // Применяем вышеприведенную формулу

        // [Примечание значение n & 1 равно 1

        // если n нечетно, иначе 0].

        if((n & 1) == 1

            f[n] = (fib(k) * fib(k) +

            fib(k - 1) * fib(k - 1));

        else

            f[n] = (2 * fib(k - 1) + fib(k)) * fib(k);

      

        return f[n];

    }

      

    // вычисляет значение первого

    // числа Фибоначчи

    static int calculateSum(int n)

    {

        return fib(n + 2) - 1;

    }

      

    // Драйвер программы

    public static void main(String args[])

    {

        int n = 4;

        System.out.println( "Sum of Fibonacci numbers is : "

                          + calculateSum(n));

          

    }

}

  

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Python 3 Программа для поиска суммы
Число Фибоначчи в O (Log n) времени.

  

MAX = 1000

  
# Создать массив для запоминания

f = [0] * MAX

  
# Возвращает n-е число Фибоначчи
# используя таблицу f []

def fib(n):

      

    n = int(n)

  

    # Базовые случаи

    if (n == 0):

        return 0

    if (n == 1 or n == 2):

        return (1

  

    # Если fib (n) уже вычислен

    if (f[n] == True):

        return f[n] 

  

    k = (n+1)/2 if (n & 1) else n/2

  

    # Применяя приведенную выше формулу [Примечание значение n & 1

    # равно 1, если n нечетно, иначе 0].

    f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1)) if (n & 1) else (2 * fib(k-1) + fib(k)) * fib(k)

    return f[n] 

  
# Вычисляет значение первых чисел Фибоначчи

def calculateSum(n):

  

    return fib(n+2) - 1

  
# Программа драйвера для проверки вышеуказанной функции

n = 4

print("Sum of Fibonacci numbers is :", calculateSum(n)) 

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # Программа для поиска суммы
// чисел Фибоначчи в
// O (Log n) время.

using System;

  

class GFG {

    static int MAX = 1000;

  

    // Создать массив для запоминания

    static int []f = new int[MAX];

      

    // Возвращает n-й Фибоначчи

    // номер с использованием таблицы f []

    static int fib(int n)

    {

        for(int i = 0;i < MAX;i++)

        f[i] = 0;

          

        //Arrays.fill(f, 0);

        // Базовые случаи

        if (n == 0)

            return 0;

        if (n == 1 || n == 2)

            return (f[n] = 1);

      

        // Если fib (n)

        // уже вычислено

        if (f[n] == 1)

            return f[n];

            int k;

        if((n & 1) == 1) 

            k = (n + 1) / 2 ;

        else

            k = n / 2;

      

        // Применяем вышеприведенную формулу

        // [Примечание значение n & 1 равно 1

        // если n нечетно, иначе 0].

        if((n & 1) == 1) 

            f[n] = (fib(k) * fib(k) + fib(k - 1)

                                   * fib(k - 1));

        else

            f[n] = (2 * fib(k - 1) + fib(k)) *

                                       fib(k);

      

        return f[n];

    }

      

    // вычисляет значение первого

    // числа Фибоначчи

    static int calculateSum(int n)

    {

        return fib(n + 2) - 1;

    }

      

    // Код драйвера

    public static void Main()

    {

        int n = 4;

        Console.Write( "Sum of Fibonacci numbers is : "

                                    + calculateSum(n));

          

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска суммы Фибоначчи
// числа в O (Log n) времени.

$MAX = 1000;

  
// Создать массив для запоминания

$f = array_fill(0, $MAX, 0);

  
// Возвращает n-е число Фибоначчи
// используя таблицу f []

function fib($n)

{

    global $f;

      

    // Базовые случаи

    if ($n == 0)

        return 0;

    if ($n == 1 || $n == 2)

        return ($f[$n] = 1);

  

    // Если fib (n) уже вычислен

    if ($f[$n])

        return $f[$n];

  

    $k = ($n & 1) ? ($n + 1) / 2 : $n / 2;

  

    // Применяем вышеприведенную формулу [Примечание значение n & 1

    // равен 1, если n нечетно, иначе 0].

    $f[$n] = ($n & 1) ? 

             (fib($k) * fib($k) + fib($k - 1) * fib($k - 1)) : 

                  (2 * fib($k - 1) + fib($k)) * fib($k);

  

    return $f[$n];

}

  
// Вычисляет значение первых чисел Фибоначчи

function calculateSum($n)

{

    return fib($n + 2) - 1;

}

  
// Код драйвера

$n = 4;

print("Sum of Fibonacci numbers is : "

                      calculateSum($n));

  
// Этот код предоставлен mits
?>

Выход :

Sum of Fibonacci numbers is : 7

Эта статья предоставлена Чирагом Агарвалом . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Сумма чисел Фибоначчи

0.00 (0%) 0 votes