by Computing the sum of Fibonacci numbers at even indexes up to N terms is an intriguing variation on generating the Fibonacci sequence. The Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, 21,…… where each number is the sum of the two preceding ones. When asked to sum the numbers at even indexes, we’re looking at positions 0,2, 4, 6,… in the sequence, keeping in mind that indexing starts from 0.
Before delving into the specifics of writing a C++ program to solve this problem, it’s crucial to understand the approach and the logic behind the algorithm. This task combines understanding the Fibonacci sequence, iterating through the sequence efficiently, and aggregating the values at even positions.
Understanding the Problem
In the Fibonacci sequence:
- The 0th term is 0, the 1st term is 1, and every subsequent term is the sum of the previous two.
- An even index implies positions like 0,2,4,6… in the sequence.
Our goal is to calculate the sum of the Fibonacci numbers located at these even indexes up to N terms in the sequence.
Efficient Approach
An efficient approach avoids calculating the entire sequence up to N terms or using separate storage for the sequence. Since only even-indexed terms are of interest, we focus on generating and summing these terms directly.
Implementation in C++
Let’s write a C++ program that accomplishes this task, keeping efficiency in mind:
#include <iostream>
using namespace std;
// Function to calculate the sum of Fibonacci numbers at even indexes up to N terms
long long sumEvenFibonacci(int N) {
if (N <= 0) return 0;
if (N == 1) return 0; // The 0th Fibonacci number is 0
if (N == 2) return 1; // Only the 0th and 1st Fibonacci numbers are considered, sum is still 0
// Starting with the first two terms of the Fibonacci sequence
long long previous = 0, current = 1, sum = 0;
// Since we start counting from 0, the 2nd term is at an even index and is the first to be added
for (int i = 2; i < N; i += 2) {
// Calculate the next Fibonacci number
long long next = previous + current;
// Update the previous two terms for the next iteration
previous = current;
current = next;
// Calculate the next Fibonacci number (to reach the next even index)
next = previous + current;
// Summing up the Fibonacci numbers at even indexes
sum += next;
// Update the previous and current terms to the next values for subsequent iterations
previous = current;
current = next;
}
return sum;
}
int main() {
int N;
cout << “Enter the number of terms: “;
cin >> N;
cout << “Sum of Fibonacci numbers at even indexes up to ” << N << ” terms is: ” << sumEvenFibonacci(N) << endl;
return 0;
}
Explanation
-
Base Cases:
The function sumEvenFibonacci initially handles base cases where N is 0, 1, or 2, returning 0 since either there are no even-index terms or the only such term doesn’t contribute to the sum.
-
Fibonacci Sequence Generation and Summation:
The core of the function lies in iterating through the Fibonacci sequence, focusing on even-index terms. Since the even-index terms are every other term in the sequence, we calculate two steps in each iteration of the loop: first to get to the next term (which is odd-indexed and thus not added to the sum) and a second time to reach the next even-indexed term, which is added to the sum.
- Optimization:
The loop iterates in steps of 2, effectively skipping the calculation of the odd-indexed terms’ contribution to the sum. This approach directly calculates and sums the even-indexed Fibonacci numbers without explicitly checking if an index is even.
