Hướng dẫn cho Dãy số (THTA Liên Chiểu, Đà Nẵng 2023)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho dãy số \(2, 5, 9, 14, 20, \ldots\). Nhập số tự nhiên \(n\) (\(0 < n \le 10^9\)), hãy in ra số hạng thứ \(n\) của dãy.
Phân tích
Quan sát các hiệu liên tiếp:
- \(5 - 2 = 3\)
- \(9 - 5 = 4\)
- \(14 - 9 = 5\)
- \(20 - 14 = 6\)
Nhận thấy dãy hiệu là \(3, 4, 5, 6, \ldots\), tức là tăng dần thêm \(1\) mỗi bước.
Gọi \(a_n\) là số hạng thứ \(n\):
- \(a_1 = 2\)
- \(a_n = a_{n-1} + (n+1)\) với \(n \ge 2\) (vì khi \(n=2\) thì cộng \(3\), khi \(n=3\) thì cộng \(4\), ...)
Ta cần công thức trực tiếp để tính nhanh với \(n\) rất lớn (tới \(10^9\)), không thể mô phỏng.
Hướng giải quyết
Nhận xét
Từ truy hồi:
\[a_n = 2 + \sum_{k=2}^{n} (k+1)\]
Ta biến đổi tổng:
\[\sum_{k=2}^{n} (k+1) = \sum_{k=2}^{n} k + \sum_{k=2}^{n} 1 = \left(\frac{n(n+1)}{2} - 1\right) + (n-1)\]
Thế vào:
\[a_n = 2 + \left(\frac{n(n+1)}{2} - 1\right) + (n-1) = \frac{n(n+1)}{2} + n\]
Gom lại:
\[a_n = \frac{n(n+3)}{2}\]
Công thức này đúng với ví dụ:
- \(n=5\): \(a_5=\frac{5\cdot 8}{2}=20\)
- \(n=10\): \(a_{10}=\frac{10\cdot 13}{2}=65\)
Thuật toán
- Đọc \(n\).
- Tính \(a = \dfrac{n(n+3)}{2}\).
- In \(a\).
Lưu ý:
- Với \(n \le 10^9\), giá trị \(a_n \approx 5 \cdot 10^{17}\), cần kiểu số nguyên lớn; Python xử lý tự động, còn C++ nên dùng
long long.
Độ phức tạp
- Thời gian: \(O(1)\)
- Bộ nhớ: \(O(1)\)
Code tham khảo
Python
n = int(input())
print((3 + n) * n // 2)
Bình luận