Giới thiệu
Cho số nguyên N. Tìm số hạng thứ N của dãy: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4… (số x xuất hiện x lần).
Ví dụ minh họa
Đầu vào
N = 6
Đầu ra
3
Giải thích
Dãy: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4...
Phương pháp 1: Lồng vòng lặp - O(√N)
Vòng ngoài i=1..N, vòng trong j=1..i, đếm đến N.
Phương pháp 2: Công thức toán học - O(1)
Vị trí cuối của số x: 1+2+...+x = x(x+1)/2. Tìm x nhỏ nhất sao cho x(x+1)/2 ≥ N. Giải phương trình bậc 2: x² + x - 2N ≥ 0 ⇒ x = ceil((√(1+8N) - 1)/2)
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
int findNthTerm(int n) {
int x = ceil((sqrt(1 + 8.0*n) - 1) / 2);
return x;
}
int main() {
int n = 12;
cout << "The series is 1, 2, 2, 3, 3, 3, 4, 4, ...\n";
cout << n << "th term of the series is " << findNthTerm(n);
return 0;
}
Đầu ra
The series is 1, 2, 2, 3, 3, 3, 4, 4, ... 12th term of the series is 5