To solve this problem, we need to compute the nth term in a Fibonacci-like sequence where the sequence starts with F(2) = 1, F(3) = 2, and each subsequent term is the sum of the two preceding terms (F(n) = F(n-1) + F(n-2) for n ≥ 4).
Approach
The approach to solve this problem efficiently involves using an iterative method to avoid the overhead of recursive calls and potential stack overflow for larger values of n. Here are the key steps:
- Base Cases: Directly return the known values for n=2 (1) and n=3 (2).
- Iterative Calculation: For values of n greater than 3, keep track of the two preceding terms and iteratively compute the next term until we reach the nth term. This ensures we only use constant space (O(1)) and linear time (O(n)).
Solution Code
n = int(input())
if n == 2:
print(1)
elif n == 3:
print(2)
else:
a, b = 1, 2
for _ in range(4, n + 1):
c = a + b
a = b
b = c
print(b)
Explanation
- Base Cases: For n=2, the result is 1, and for n=3, it's 2. These are the starting points of our sequence.
- Iterative Step: For n > 3, we initialize
a(F(n-2)) andb(F(n-1)) with the base values 1 and 2 respectively. We then loop from 4 to n, updatingaandbeach time to the next pair of preceding terms. The value ofbat the end of the loop will be the nth term of the sequence.
This method efficiently computes the desired term with optimal time and space complexity, making it suitable for both small and large values of n. For example:
- Input 2 → Output: 1
- Input 3 → Output: 2
- Input 4 → Output:3
- Input5 → Output:5
- Input6 → Output:8
All these examples align with the expected results from the problem statement.


作者声明:本文包含人工智能生成内容。