The Geek-onacci Number sequence is a modified version of the Fibonacci sequence, commonly presented in programming challenges. This series starts with three initial terms given, and every following term is determined by adding the three terms that came before it. This sequence is beneficial for delving into concepts like recursion, iteration, and dynamic programming.
Explanation:
The initial values of the Geek-onacci sequence are explicitly provided, usually as input values. These specific numbers are commonly referred to as G1, G2, and G3.
For each value Gn in the series with n greater than 3, it is determined by the formula:
- G(n) = G(n-1) + G(n-2) + G(n-3)
This implies that every term is the result of adding the three preceding terms together.
Example: Suppose the first three terms are:
- G1=1
- G2=2
- G3=3
The sequence will be:
- G4=G3+G2+G1=3+2+1=6
- G5=G4+G3+G2=6+3+2=11
- G6=G5+G4+G3=11+6+3=20
Approach 1: Simple Approach
Program:
#include <iostream>
using namespace std;
// Function to calculate the Geek-onacci number
int geekonacci(int G1, int G2, int G3, int N) {
// If N is 1, 2, or 3, return the respective initial value
if (N == 1) return G1;
if (N == 2) return G2;
if (N == 3) return G3;
// Initialize variables for the first three terms
int term1 = G1, term2 = G2, term3 = G3, current;
// Calculate terms iteratively
for (int i = 4; i <= N; ++i) {
current = term1 + term2 + term3;
term1 = term2;
term2 = term3;
term3 = current;
}
return term3;
}
int main() {
int G1, G2, G3, N;
// Input first three terms and the position N
cout << "Enter G1, G2, G3: ";
cin >> G1 >> G2 >> G3;
cout << "Enter the value of N: ";
cin >> N;
// Calculate and display the Nth Geek-onacci number
int result = geekonacci(G1, G2, G3, N);
cout << "The " << N << "th Geek-onacci number is: " << result << endl;
return 0;
}
Output:
Enter G1, G2, G3: 1 2 3
Enter the value of N: 5
The 5th Geek-onacci number is: 11
Explanation:
- Purpose of the Code
- The goal of the code is to calculate the Geek-onacci number at a specific position N in the sequence. The Geek-onacci sequence is a variation of Fibonacci, where every number is the sum of the last three numbers.
- Input Explanation
The program takes four inputs:
- The first three terms of the sequence: G1, G2, and G3.
- The position N for which we want to find the Geek-onacci number.
- Handle Simple Cases First
The program checks if N is 1, 2, or 3:
- If N=1, the result is G1 (the first term).
- If N=2, the result is G2 (the second term).
- If N=3, the result is G3 (the third term).
This is because these values are provided as input and do not require computation.
- Iterative Computation for N>3
If the value of N exceeds 3, the software employs an iterative process to compute the elements starting from the 4th position all the way up to N.
Steps in the Loop:
Initialize the Initial Three Values:
- The software maintains a record of the preceding three values through variables term1, term2, and term3, which are originally assigned as G1, G2, and G3.
Calculate the Next Term:
- For each position i (starting from 4), the next term in the sequence is calculated as:
- current=term1+term2+term3
- This adds the last three terms to get the next term.
Shift the Terms:
After calculating the new term, the program updates the values of the last three terms:
- term1 is replaced by term2.
- term2 is replaced by term3.
- term3 is replaced by current (the newly calculated term).
- This ensures the program always has the latest three terms for the next calculation.
Repeat Until N:
The iteration persists until it computes the value at index N.
Output the Result
Once the iteration is complete, the variable term3 stores the Geek-onacci number located at the Nth position. Subsequently, the software displays this outcome.
- Illustrative Demonstration
Let's consider a scenario where G1 equals 1, G2 equals 2, G3 equals 3, and N is equal to 6.
Initial terms: term1 = 1, term2 = 2, term3 = 3.
Start the loop from i=4:
Step 1: The current value is the sum of 1, 2, and 3, which results in 6.
- Revision: term1 is now 2, term2 is now 3, and term3 is now 6.
Step 2: the total of the current values is equal to 11.
- Revision: term1 equals 3, term2 equals 6, and term3 equals 11.
Step 3: The current value is calculated by adding 3, 6, and 11, resulting in a total of 20.
- Update: term1 equals 6, term2 equals 11, and term3 equals 20.
Following the iteration, the value of term3 = 20 represents the Geek-onacci number at the 6th position denoted as N.
Complexity Analysis:
Time Complexity
The time complexity of the program is O(N).
- The program iterates from position 4 to N, calculating one term at a time.
- Each iteration involves a constant amount of work (a simple addition of three numbers and variable updates).
- Therefore, the number of operations is proportional to N.
Space Complexity
The space complexity of the program is O(1).
- The program uses only a fixed number of variables (term1, term2, term3, and current) to calculate the Geek-onacci numbers.
- It does not require any extra space like an array or recursion stack.
- Regardless of the value of N, the space usage remains constant.
Approach 2: Dynamic Programming with a Sliding Window Technique
This technique saves the final three terms in a data structure and refreshes them in a sequential manner. Although it bears resemblance to the prior method, it organizes the computation in an alternative manner to enhance clarity and flexibility.
Program:
#include <iostream>
using namespace std;
// Function to calculate the Geek-onacci number using a sliding window
int geekonacci(int G1, int G2, int G3, int N) {
// If N is 1, 2, or 3, return the respective initial value
if (N == 1) return G1;
if (N == 2) return G2;
if (N == 3) return G3;
// Array to store the last three terms
int terms[3] = {G1, G2, G3};
// Calculate terms from the 4th to the Nth position
for (int i = 4; i <= N; ++i) {
int current = terms[0] + terms[1] + terms[2]; // Sum of the last three terms
terms[0] = terms[1]; // Shift left: second becomes first
terms[1] = terms[2]; // Shift left: third becomes second
terms[2] = current; // New term becomes third
}
// The Nth Geek-onacci number is now in terms[2]
return terms[2];
}
int main() {
int G1, G2, G3, N;
// Input first three terms and the position N
cout << "Enter G1, G2, G3: ";
cin >> G1 >> G2 >> G3;
cout << "Enter the value of N: ";
cin >> N;
// Calculate and display the Nth Geek-onacci number
int result = geekonacci(G1, G2, G3, N);
cout << "The " << N << "th Geek-onacci number is: " << result << endl;
return 0;
}
Output:
Enter G1, G2, G3: 1 2 3
Enter the value of N: 6
The 6th Geek-onacci number is: 20
Explanation:
- Purpose of the Code
This software computes the Geek-onacci value at index N within the sequence. The Geek-onacci series, akin to the Fibonacci sequence, determines the subsequent number by summing the last three numbers.
- Program Inputs
The program asks for four inputs:
- G1: The first term of the sequence.
- G2: The second term of the sequence.
- G3: The third term of the sequence.
- N: The position in the sequence for which the Geek-onacci number is needed.
- Handling Simple Cases First
If N is 1, 2, or 3, the answer is directly one of the initial terms:
- If N=1, the result is G1.
- If N=2, the result is G2.
- If N=3, the result is G3.
The software outputs these values directly without needing to execute additional computations as the necessary data is already available.
Storing Terms in an Array
For positions greater than 3, the program uses an array called terms of size 3:
- This array holds the last three numbers of the sequence.
- Initially, it is set as:
- terms[0] = G1
- terms[1] = G2
- terms[2] = G3
- Loop to Calculate Terms
The program calculates all terms from 4 to N using a loop:
- Compute the Next Term: The next term in the sequence is the sum of the three numbers in the array: current=terms[0]+terms[1]+terms[2]
- Shift the Array Values: The array is updated to include the new term: terms[0] (oldest term) is replaced by terms[1]. terms[1] (middle term) is replaced by terms[2]. terms[2] (newest term) is replaced by current. This process ensures that the array always contains the latest three terms.
- Repeat Until N: The loop continues until the program calculates the Geek-onacci number at position N.
- The next term in the sequence is the sum of the three numbers in the array: current=terms[0]+terms[1]+terms[2]
- The array is updated to include the new term:
- terms[0] (oldest term) is replaced by terms[1].
- terms[1] (middle term) is replaced by terms[2].
- terms[2] (newest term) is replaced by current.
- This process ensures that the array always contains the latest three terms.
- The loop continues until the program calculates the Geek-onacci number at position N.
- Return the Result
- After the loop ends, the value of terms[2] contains the Geek-onacci number at position N. This value is then printed as the result.
- Example Walkthrough
Let's consider an instance where:
- G1=1, G2=2, G3=3, and N=6.
Initial State:
terms = [1, 2, 3].
Loop Calculations:
- For i=4:
- current=1+2+3=6.
- Update terms: [2, 3, 6].
- For i=5:
- current=2+3+6=11.
- Update terms: [3, 6, 11].
- For i=6:
- current=3+6+11=20.
- Update terms: [6, 11, 20].
After the iteration, the value of terms[2] is 20, representing the 6th term in the Geek-onacci sequence.
Complexity Analysis:
Time Complexity
- The program calculates the Geek-onacci numbers from the 4th position to the Nth position using a single loop.
- Each iteration performs a constant amount of work (adding three numbers and updating the array).
- Therefore, the total number of operations is proportional to N, resulting in a time complexity of O(N).
Space Complexity
- The program uses an array of fixed size (3 elements) to store the last three terms of the sequence.
- No additional memory is used, regardless of the size of N.
- As the array size remains constant, the space complexity is O(1), indicating constant space usage.
