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, in ra tích của bốn hệ số 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ể tìm thấy 4 yếu tố đó thì in "Không thể".
Cần lưu ý rằng tất cả bốn yếu tố có thể tương đương với nhau để tối đa hóa sản phẩm.
Đầu vào
24
Đầu ra
All the factors are -> 1 2 4 5 8 10 16 20 40 80 Product is -> 160000
Chọn hệ số 20 bốn lần,
Do đó, 20 + 20 + 20 + 20 =24 và tích là tối đa.
Phương pháp
Sau đây là thuật toán từng bước để giải quyết vấn đề này -
- Lúc đầu, hãy xác định các thừa số của một số ‘N’ bằng cách truy cập từ 1 đến căn bậc hai của ‘N’ và xác minh xem ‘i’ và ‘n / i’ có chia hết N và lưu trữ chúng trong một vectơ hay không.
- Bây giờ chúng tôi sắp xếp vectơ và in mọi phần tử.
- Xác định ba số để tối đa hóa sản phẩm bằng số thứ tư, thực hiện ba vòng.
- Cuối cùng, chúng tôi thay thế sản phẩm tối đa tiếp theo bằng sản phẩm trước đó.
- In sản phẩm khi bạn tìm thấy bốn yếu tố.
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 findfactors2(int n1){
vector<int> vec2;
// Now inserting all the factors in a vector s
for (int i = 1; i * i <= n1; i++) {
if (n1 % i == 0) {
vec2.push_back(i);
vec2.push_back(n1 / i);
}
}
// Used to sort the vector
sort(vec2.begin(), vec2.end());
// Used to print all the factors
cout << "All the factors are -> ";
for (int i = 0; i < vec2.size(); i++)
cout << vec2[i] << " ";
cout << endl;
// Now any elements is divisible by 1
int maxProduct2 = 1;
bool flag2 = 1;
// implementing three loop we'll find
// the three maximum factors
for (int i = 0; i < vec2.size(); i++) {
for (int j = i; j < vec2.size(); j++) {
for (int k = j; k < vec2.size(); k++) {
// Now storing the fourth factor in y
int y = n1 - vec2[i] - vec2[j] - vec2[k];
// It has been seen that if the fouth factor become negative
// then break
if (y <= 0)
break;
// Now we will replace more optimum number
// than the previous one
if (n1 % y == 0) {
flag2 = 0;
maxProduct2 = max(vec2[i] * vec2[j] * vec2[k] *y,maxProduct2);
}
}
}
}
// Used to print the product if the numbers exist
if (flag2 == 0)
cout << "Product is -> " << maxProduct2 << endl;
else
cout << "Not possible" << endl;
}
// Driver code
int main(){
int n1;
n1 = 80;
findfactors2(n1);
return 0;
} Đầu ra
All the factors are -> 1 2 4 5 8 10 16 20 40 80 Product is -> 160000