Time Limit: 2s Memory Limit: 192MB
Problem Description
Fibonacci Sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… This sequence is known as the “Fibonacci sequence”, where each number is a “Fibonacci number”.
Input Format
An integer N (N cannot be greater than 40)
Output Format
A Fibonacci sequence consisting of N “Fibonacci numbers”.
Sample Input
6
Sample Output
1 1 2 3 5 8
Code
#include <iostream>using namespace std;
int main() { int n; cin >> n; // Read input N
if (n <= 0) return 0; // Handle special case
// Initialize the first two Fibonacci numbers int a = 1, b = 1;
if (n >= 1) cout << "1"; if (n >= 2) cout << " 1";
// Generate from the third number onwards for (int i = 3; i <= n; i++) { int next = a + b; // Calculate the next Fibonacci number cout << " " << next;
// Update the previous two numbers a = b; b = next; }
cout << endl;
return 0;}Output Result
Code Explanation:Input Handling: Read the integer N, which indicates the length of the Fibonacci sequence to output N cannot be greater than 40 (as per problem requirements)Special Case Handling: If n is less than or equal to 0, return directly The first two numbers of the Fibonacci sequence are both 1Sequence Generation: Use two variables a and b to store the first two Fibonacci numbers Use a loop to generate subsequent Fibonacci numbers starting from the 3rd number Each new number is the sum of the previous two: next = a + bOutput Format: The first number is output directly (without a space) Subsequent numbers are prefixed with a space to ensure correct output format
Another Implementation Method (Using Arrays):
#include <iostream>using namespace std;
int main() { int n; cin >> n;
if (n <= 0) return 0;
int fib[40]; // Array to store Fibonacci sequence
// Initialize the first two numbers fib[0] = 1; fib[1] = 1;
// Generate subsequent numbers for (int i = 2; i < n; i++) { fib[i] = fib[i-1] + fib[i-2]; }
// Output result for (int i = 0; i < n; i++) { if (i > 0) cout << " "; cout << fib[i]; } cout << endl;
return 0;}Third Method (Recursive Implementation, Not Recommended for This Problem):
#include <iostream>using namespace std;
// Recursive function to calculate Fibonacci number (inefficient)
int fibonacci(int n) { if (n == 1 || n == 2) return 1; return fibonacci(n-1) + fibonacci(n-2);}
int main() { int n; cin >> n;
for (int i = 1; i <= n; i++) { if (i > 1) cout << " "; cout << fibonacci(i); } cout << endl;
return 0;}Extended Knowledge:Fibonacci Sequence: Sequence Definition: F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) (n ≥ 3) Each number is the sum of the previous two numbers Widely used in mathematics, computer science, and natureAlgorithm Selection: The first method (iteration) is highly recommended: time complexity O(n), space complexity O(1) The second method (array) is also good: time complexity O(n), space complexity O(n) The third method (recursion) is not recommended: time complexity O(2^n), too inefficientTeaching Suggestions: For beginners, the first iterative method is recommended, as it is both efficient and easy to understand Discuss the applications of the Fibonacci sequence in real life (e.g., golden ratio, plant growth patterns, etc.) Emphasize the importance of algorithm efficiency and compare the time complexities of different methodsNotes: The problem states that N cannot be greater than 40, so there is no need to consider large number overflow issues If N could be very large, consider using long long type to prevent integer overflow
C++ Basic Tutorial Collection
C++ Basic Materials
1. C++ Output
2. C++ Variables
3. C++ Input
4. C++ Expressions
5. IF Statements
6. IF Applications
7. WHILE Loop Statements
8. FOR Loop Statements
9. Arrays
10. One-Dimensional Arrays
11. Two-Dimensional Arrays
12. C++ Functions
13. C++ File Operations – Writing Files
If you find it interesting, just click on me
