Trong bài toán đã cho, chúng ta được cung cấp một số nguyên n, chúng ta cần tìm P n , tức là số pell ở vị trí đó. Bây giờ, như chúng ta đã biết, số pell là một phần của chuỗi được cho bởi công thức này −P n =2 * P n-1 + P n-2
Với hai số đầu tiên - P 0 =0 và P 1 =1
Phương pháp tiếp cận để tìm ra giải pháp
Bây giờ chúng ta sẽ giải quyết vấn đề này bằng hai cách tiếp cận:đệ quy và lặp lại.
Phương pháp tiếp cận đệ quy
Trong công thức này, chúng tôi sẽ áp dụng một cách đệ quy công thức của Pell Number và thực hiện n lần lặp.
Ví dụ
#include <iostream>
using namespace std;
int pell(int n) {
if(n <= 2)
return n;
return 2*pell(n-1) + pell(n-2);
}
int main() {
int n = 6; // given n
cout << pell(n) <<"\n"; // Pell number at that position.
return 0;
} Đầu ra
70
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng ta sử dụng đệ quy bằng cách gọi pell (n-1) &&pell (n-2) cho đến khi n nhỏ hơn hoặc bằng 2 vì chúng ta biết các số pell cho đến 2 bằng với số đã cho. Độ phức tạp về thời gian tổng thể của chương trình trên là O (N) , trong đó N là số đã cho.
Phương pháp tiếp cận lặp lại
Trong cách tiếp cận này, chúng ta sẽ sử dụng công thức tương tự như trên nhưng tính toán số bằng vòng lặp for thay vì hàm đệ quy.
Ví dụ
#include <iostream>
using namespace std;
int main() {
int n = 6; // given n.
int p0 = 0; // initial value of pn-2.
int p1 = 1; // initial value of pn-1.
int pn; // our answer.
if(n <= 2) // if n <= 2 we print n.
cout << n <<"\n";
else {
for(int i = 2; i <= n; i++) { // we are going to find from the second number till n.
pn = 2*p1 + p0;
p0 = p1; // pn-1 becomes pn-2 for new i.
p1 = pn; // pn becomes pn-1 for new i.
}
cout << pn << "\n";
}
return 0;
} Đầu ra
70
Giải thích về đoạn mã trên
Trong chương trình đã cho, chúng ta đang đi ngang từ 2 đến n và chỉ cần cập nhật các giá trị cho pn-2 thành pn-1 và pn-1 thành pn cho đến khi chúng ta đạt đến n.
Kết luận
Trong bài viết này, chúng tôi đã giải quyết vấn đề tìm số pell thứ N bằng cách sử dụng đệ quy và lặp. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác.