Để giải một bài toán trong đó n - số người hiện tại mỗi người có thể độc thân hoặc có mặt trong một cặp, vì vậy chúng ta cần tìm tổng số cách những người này có thể được ghép đôi.
Input : 3
Output: 4
Explanation : [ {1}, {2}, {3},], [{1, 2}, {3}], [{1}, {2, 3}], [{1, 3}, {2}] these four ways are the only ways we can pa up these 3 people.
Input : 6
Output : 76 Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi sẽ sử dụng công thức của Tableau trẻ để tính toán vấn đề này và công thức mà chúng tôi sẽ sử dụng là -
A[n] = A[n-1] + (n-1) * A[n-2]
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include <bits/stdc++.h>
using namespace std;
int Young_Tableau(int n){
int A[n + 1];// To store the answer.
A[1] = 1; // initial values
A[2] = 2; // initial values
for (int i = 3; i <= n; i++) { // using the formula of "Young Tableau" to calculate our answer
A[i] = A[i - 1] + (i - 1) * A[i - 2];
}
return A[n]; // returning the answer
}
int main(){
int n = 6;
cout << Young_Tableau(n);
return 0;
} Đầu ra
76
Giải thích về Quy tắc trên
Trong cách tiếp cận ở trên, chúng tôi chỉ cần áp dụng công thức cho Young Tableau, nơi chúng tôi cần tìm hai số trước đó. Bây giờ chúng ta có thể lưu trữ những con số này trong chỉ số mảng. Bằng cách đăng ký, chúng tôi có thể đạt được giá trị của chúng cho công thức của chúng tôi và do đó chúng tôi tính toán câu trả lời của mình.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm một số cách để ghép nối mọi người. 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) 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. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.