Khái niệm
Đối với một số nguyên N cho trước, nhiệm vụ của chúng ta là xác định tất cả các thừa số của N và in ra các thừa số tích lũy của N sao cho -
- Tổng của bốn yếu tố bằng N.
- Tích của bốn yếu tố là lớn nhất.
Người ta thấy rằng nếu không thể xác định được 4 yếu tố đó thì in “Không thể”. Cần lưu ý rằng tất cả 4 yếu tố này có thể bằng nhau để tối đa hóa sản phẩm.
Đầu vào
N = 60
Đầu ra
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625
Chọn hệ số 15 bốn lần,
Do đó, 15 + 15 + 15 + 15 =60 và tích là lớn nhất.
Phương pháp
Đây là một phương pháp có độ phức tạp là O (P ^ 3), trong đó P là số nhân tố của N đã được giải thích.
Vì vậy, có thể thu được một phương pháp hiệu quả về độ phức tạp thời gian O (N ^ 2) với sự trợ giúp của các bước sau.
- Chúng tôi lưu trữ tất cả các thừa số của một số nhất định trong một vùng chứa.
- Bây giờ chúng tôi lặp lại cho tất cả các cặp và lưu trữ tổng của chúng trong một vùng chứa khác.
- Chúng ta phải đánh dấu chỉ số (phần tử1 + phần tử2) với cặp (phần tử1, phần tử2) để lấy được các phần tử mà theo đó tổng thu được.
- Một lần nữa, chúng tôi lặp lại cho tất cả các cặp và xác minh xem n-cặp_sum có tồn tại trong cùng một vùng chứa hay không, do đó cả hai cặp tạo thành bộ tứ.
- Triển khai mảng băm cặp để lấy các phần tử mà cặp được tạo thành.
- Cuối cùng, hãy lưu trữ phần lớn nhất trong số tất cả các phần tư như vậy và in nó ở cuối.
Ví dụ
// C++ program to find four factors of N
// with maximum product and sum equal to N
#include <bits/stdc++.h>
using namespace std;
// Shows function to find factors
// and to print those four factors
void findfactors1(int q){
vector<int> vec1;
// Now inserting all the factors in a vector s
for (int i = 1; i * i <= q; i++) {
if (q % i == 0) {
vec1.push_back(i);
vec1.push_back(q / i);
}
}
// Used to sort the vector
sort(vec1.begin(), vec1.end());
// Used to print all the factors
cout << "All the factors are -> ";
for (int i = 0; i < vec1.size(); i++)
cout << vec1[i] << " ";
cout << endl;
// So any elements is divisible by 1
int maxProduct1 = 1;
bool flag1 = 1;
// implementing three loop we'll find
// the three largest factors
for (int i = 0; i < vec1.size(); i++) {
for (int j = i; j < vec1.size(); j++) {
for (int k = j; k < vec1.size(); k++) {
// Now storing the fourth factor in y
int y = q - vec1[i] - vec1[j] - vec1[k];
// It has been seen that if the fouth factor become negative
// then break
if (y <= 0)
break;
// So we will replace more optimum number
// than the previous one
if (q % y == 0) {
flag1 = 0;
maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] *y,maxProduct1);
}
}
}
}
// Used to print the product if the numbers exist
if (flag1 == 0)
cout << "Product is -> " << maxProduct1 << endl;
else
cout << "Not possible" << endl;
}
// Driver code
int main(){
int q;
q = 60;
findfactors1(q);
return 0;
} Đầu ra
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625