Hướng dẫn này sẽ thảo luận về một vấn đề trong đó chúng ta được cung cấp một mảng các số nguyên dương riêng biệt. Chúng ta cần tìm tập hợp con lớn nhất sao cho mỗi cặp phần tử lớn hơn được chia cho phần tử nhỏ hơn, ví dụ -
Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.
Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1 Phương pháp tiếp cận để tìm giải pháp
Có hai cách tiếp cận khác nhau mà chúng tôi sẽ giải thích trong hướng dẫn này.
Cách tiếp cận đơn giản
Theo một cách tiếp cận đơn giản, chúng ta có thể áp dụng đệ quy để giải quyết vấn đề này. Chúng tôi sẽ lấy từng phần tử và kiểm tra xem nó có nên đưa nó vào tập hợp con hay không. Giả sử chúng ta bắt đầu với yếu tố đầu tiên. Chúng ta sẽ có hai lựa chọn, hoặc là được đưa vào tập hợp con hoặc không cho phần tử đầu tiên. Hãy bao gồm yếu tố đầu tiên. Sau đó, để phần tử thứ hai được bao gồm trong tập hợp con, nó phải chia hết cho hoặc chia hết các phần tử trong chuỗi con, tức là phần tử đầu tiên. Đây là cách chúng ta sẽ đi xuyên suốt mảng. Vì vậy, sẽ có 2 ^ n đường đi có thể tạo ra độ phức tạp Thời gian là O (2 ^ n). Hãy xem cách tiếp cận khả thi để giải quyết vấn đề này.
Phương pháp tiếp cận hiệu quả
Có thể áp dụng một cách tiếp cận hiệu quả bằng cách sử dụng lập trình động trong vấn đề này.
-
Sắp xếp mảng để được phần tử bên trái chia hết cho phần tử bên trái. Chúng ta phải kiểm tra tính chất chia hết một lần.
-
Chúng ta sẽ lấy Dãy con tăng dài nhất, tức là mảng dp [] của chúng ta, để lưu trữ tập hợp con có thể chia được lớn nhất của chỉ số cho đến thứ i. Chúng tôi sẽ khởi tạo mỗi chỉ mục bằng một chỉ mục vì mọi phần tử đều tự phân chia.
-
Bây giờ chúng ta sẽ lặp lại từ chỉ mục thứ 2 và kiểm tra từng phần tử để tìm tập hợp con có thể chia được tối đa kết thúc bằng chỉ mục hiện tại. Bằng cách này, chúng tôi sẽ tìm thấy tập hợp con tối đa cho mỗi chỉ mục.
-
Bây giờ hãy xem qua mảng và với mọi phần tử, hãy tìm một số chia có số bị chia là lớn nhất. Và thay đổi các giá trị đếm có thể chia hết của chỉ số hiện tại thành số đếm có thể chia hết của phần tử đó + 1.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#include<bits/stdc++.h>
using namespace std;
int main(){
int nums[] = {1, 2, 3, 6};
int n = sizeof(nums)/sizeof(int);
// sorting the array to exclude one condition for division.
sort(nums, nums+n);
vector <int> prev_res(n, -1);
// vector to store divisors of all the elements
vector <int> dp(n, 1);
int max = 1;
for (int i=1; i<n; i++){ // Check if there's a divisor of ith element present at jth index.
for (int j=0; j<i; j++){
if (nums[i]%nums[j] == 0){
// check If adding that increases the number of elements in subsequence.
if (dp[i] < dp[j] + 1){
dp[i] = dp[j]+1;
prev_res[i] = j;
}
}
}
// finding index having a maximum number of subsets.
if(max<dp[i])
max = dp[i];
}
cout << "Largest divisible subset in the array: ";
// printing the maximum subset
int k = max;
while (k >= 0){
cout << nums[k] << " ";
k = prev_res[k];
}
return 0;
} Đầu ra
Largest divisible subset in the array: 6 2 1
Kết luận
Trong hướng dẫn này, chúng ta đã thảo luận về một vấn đề:chúng ta cần tìm tập hợp con có thể chia hết lớn nhất trong mảng đã cho mà các số nguyên trong mỗi cặp đều có thể chia hết. Chúng tôi đã thảo luận về một cách tiếp cận từ đệ quy tạo ra độ phức tạp về thời gian theo cấp số nhân, vì vậy chúng tôi đã thảo luận về một giải pháp lập trình động. Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.