Trong bài toán này, chúng ta được cho một số nguyên N. Nhiệm vụ là tìm số hạng thứ n trong chuỗi 1 2 2 3 3 3 4….
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 6
Đầu ra
3
Giải thích
Chuỗi số hạng thứ n là 1, 2, 2, 3, 3, 3, ...
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là sử dụng một vòng lặp lồng nhau. Vòng lặp for bên ngoài từ 1 đến n. Và vòng lặp bên trong từ 1 đến i (biến lặp của vòng lặp ngoài). Đối với mỗi lần lặp trong vòng lặp bên trong, hãy đếm số phần tử của chuỗi và trả về giá trị của i khi số lượng bằng n.
Một cách tiếp cận hiệu quả hơn để giải quyết vấn đề là sử dụng các vị trí mẫu. Các phần tử của dãy có vị trí của chúng trong dãy là -
Element 1: position 1 Element 2: position 2, 3 Element 3: position 4, 5, 6 Element 4: position 7, 8, 9, 10
Đối với những giá trị này, chúng ta có thể tạo một chuỗi bằng cách sử dụng vị trí cuối cùng của phần tử trong chuỗi đó là,
1, 3, 6, 10, 15, 21, 28, ….
x xuất hiện trong thuật ngữ, 1 + 2 + 3 +… + (x-2) + (x-1) ...
Điều này có thể được tổng quát là n =x * (x-1) / 2
2n =x 2 - x => x 2 - x - 2n =0
Giải phương trình bằng công thức nghiệm của phương trình bậc hai,
$$ x =1/2 * (1+ \ sqrt {1 + 8 * n)} $$
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int findNthTerm(int n) {
int x = (((1) + (double)sqrt(1 + (8 * n))) / 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