ЧЕТНА СУМА НА ЧИСЛАТА НА ФИБОНАЧИ

Опитайте в GfG Practice ' title=

#practiceLinkDiv { display: none !important; }

При дадено ограничение намерете сумата от всички членове с четни стойности в редицата на Фибоначи под даденото ограничение.
Първите няколко термина на Числата на Фибоначи са 11 2 3 5 8 13 21 34 55 89 144 233 ... (Четните числа са осветени).
Примери:

Input : limit = 8 Output : 10 Explanation : 2 + 8 = 10 Input : limit = 400; Output : 188. Explanation : 2 + 8 + 34 + 144 = 188.

Препоръчителна практика Четна сума на числата на Фибоначи Опитайте!

Едно просто решение е да преминете през всички числа на Фибоначи, докато следващото число е по-малко или равно на дадения лимит. За всяко число проверете дали е четно. Ако числото е четно, добавете го към резултата.
Едно ефективно решение се основава на следното рекурсивна формула за четни числа на Фибоначи

Recurrence for Even Fibonacci sequence is: EFn = 4EFn-1 + EFn-2 with seed values EF0 = 0 and EF1 = 2.   EFn   represents n'th term in Even Fibonacci sequence.

Реф това повече подробности за горната формула.
Така че докато итерираме числата на Фибоначи, ние генерираме само четни числа на Фибоначи.

C++

// Find the sum of all the even-valued terms in // the Fibonacci sequence which do not exceed // given limit. #include   using namespace std; // Returns sum of even Fibonacci numbers which are // less than or equal to given limit. int evenFibSum(int limit) {  if (limit < 2)  return 0;  // Initialize first two even Fibonacci numbers  // and their sum  long long int ef1 = 0 ef2 = 2;  long long int sum = ef1 + ef2;  // calculating sum of even Fibonacci value  while (ef2 <= limit)  {  // get next even value of Fibonacci sequence  long long int ef3 = 4*ef2 + ef1;  // If we go beyond limit we break loop  if (ef3 > limit)  break;  // Move to next even number and update sum  ef1 = ef2;  ef2 = ef3;  sum += ef2;  }  return sum; } // Driver code int main() {  int limit = 400;  cout << evenFibSum(limit);  return 0; }

Java

// Find the sum of all the even-valued terms in // the Fibonacci sequence which do not exceed // given limit. import java.io.*; class GFG  {  // Returns sum of even Fibonacci numbers which are  // less than or equal to given limit.  static int evenFibSum(int limit)  {  if (limit < 2)  return 0;    // Initialize first two even Fibonacci numbers  // and their sum  long ef1 = 0 ef2 = 2;  long sum = ef1 + ef2;    // calculating sum of even Fibonacci value  while (ef2 <= limit)  {  // get next even value of Fibonacci sequence  long ef3 = 4 * ef2 + ef1;    // If we go beyond limit we break loop  if (ef3 > limit)  break;    // Move to next even number and update sum  ef1 = ef2;  ef2 = ef3;  sum += ef2;  }    return(int) sum;  }    // Driver code  public static void main (String[] args)   {  int limit = 400;  System.out.println(evenFibSum(limit));    } } // This code is contributed by vt_m.

Python3

# Find the sum of all the even-valued  # terms in the Fibonacci sequence which  # do not exceed given limit. # Returns sum of even Fibonacci numbers which # are less than or equal to given limit. def evenFibSum(limit) : if (limit < 2) : return 0 # Initialize first two even Fibonacci numbers # and their sum ef1 = 0 ef2 = 2 sm= ef1 + ef2 # calculating sum of even Fibonacci value while (ef2 <= limit) : # get next even value of Fibonacci  # sequence ef3 = 4 * ef2 + ef1 # If we go beyond limit we break loop if (ef3 > limit) : break # Move to next even number and update # sum ef1 = ef2 ef2 = ef3 sm = sm + ef2 return sm # Driver code limit = 400 print(evenFibSum(limit)) # This code is contributed by Nikita Tiwari.

// C# program to Find the sum of all // the even-valued terms in the  // Fibonacci sequence which do not // exceed given limit.given limit. using System; class GFG {    // Returns sum of even Fibonacci   // numbers which are less than or  // equal to given limit.  static int evenFibSum(int limit)  {  if (limit < 2)  return 0;    // Initialize first two even  // Fibonacci numbers and their sum  long ef1 = 0 ef2 = 2;  long sum = ef1 + ef2;    // calculating sum of even   // Fibonacci value  while (ef2 <= limit)  {    // get next even value of   // Fibonacci sequence  long ef3 = 4 * ef2 + ef1;    // If we go beyond limit  // we break loop  if (ef3 > limit)  break;    // Move to next even number  // and update sum  ef1 = ef2;  ef2 = ef3;  sum += ef2;  }    return(int) sum;  }    // Driver code  public static void Main ()   {  int limit = 400;  Console.Write(evenFibSum(limit));    } } // This code is contributed by Nitin Mittal.

PHP

 // Find the sum of all the  // even-valued terms in the  // Fibonacci sequence which  // do not exceed given limit. // Returns sum of even Fibonacci // numbers which are less than or  // equal to given limit. function evenFibSum($limit) { if ($limit < 2) return 0; // Initialize first two even  // Fibonacci numbers and their sum $ef1 = 0; $ef2 = 2; $sum = $ef1 + $ef2; // calculating sum of // even Fibonacci value while ($ef2 <= $limit) { // get next even value of // Fibonacci sequence $ef3 = 4 * $ef2 + $ef1; // If we go beyond limit // we break loop if ($ef3 > $limit) break; // Move to next even number // and update sum $ef1 = $ef2; $ef2 = $ef3; $sum += $ef2; } return $sum; } // Driver code $limit = 400; echo(evenFibSum($limit)); // This code is contributed by Ajit. ?>

JavaScript

<script> // Javascript program to find the sum of all the even-valued terms in // the Fibonacci sequence which do not exceed // given limit.  // Returns sum of even Fibonacci numbers which are  // less than or equal to given limit.  function evenFibSum(limit)  {  if (limit < 2)  return 0;    // Initialize first two even Fibonacci numbers  // and their sum  let ef1 = 0 ef2 = 2;  let sum = ef1 + ef2;    // calculating sum of even Fibonacci value  while (ef2 <= limit)  {  // get next even value of Fibonacci sequence  let ef3 = 4 * ef2 + ef1;    // If we go beyond limit we break loop  if (ef3 > limit)  break;    // Move to next even number and update sum  ef1 = ef2;  ef2 = ef3;  sum += ef2;  }    return sum;  }   // Function call    let limit = 400;  document.write(evenFibSum(limit));   </script>

Изход:

Времева сложност: O(n)

Помощно пространство: О(1)

хеширане в структурата на данните