컨셉
주어진 정수 N과 관련하여 우리의 임무는 N의 모든 인수를 결정하여 N의 네 인수의 곱을 출력하여 다음이 되도록 하는 것입니다.
- 네 가지 요소의 합은 N과 같습니다.
- 네 가지 요인의 곱이 가장 큽니다.
그러한 요소 4개를 찾는 것이 불가능하면 "불가능"이라고 인쇄하십시오.
4가지 요소는 모두 제품을 최대화하기 위해 서로 동일할 수 있다는 점에 유의해야 합니다.
입력
24
출력
All the factors are -> 1 2 4 5 8 10 16 20 40 80 Product is -> 160000
요소 20을 네 번 선택하고
따라서 20+20+20+20 =24이며 제품은 최대입니다.
방법
다음은 이 문제를 해결하기 위한 단계별 알고리즘입니다 -
- 먼저 1에서 'N'의 제곱근까지 방문하여 숫자 'N'의 인수를 결정하고 'i'와 'n/i'가 N을 나누는지 확인하고 벡터에 저장합니다.
- 이제 벡터를 정렬하고 모든 요소를 인쇄합니다.
- 세 개의 루프를 구현하여 네 번째 숫자로 제품을 최대화하기 위해 세 개의 숫자를 결정합니다.
- 마지막으로 다음 최대 제품을 이전 제품으로 교체합니다.
- 네 가지 요소를 찾을 때 제품을 인쇄하십시오.
예시
// 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;
} 출력
All the factors are -> 1 2 4 5 8 10 16 20 40 80 Product is -> 160000