แนวคิด
ด้วยความเคารพของจำนวนเต็ม N ที่กำหนด งานของเราคือการกำหนดปัจจัยทั้งหมดของ N และพิมพ์ปัจจัยภายนอกผลิตภัณฑ์ของ N เพื่อให้ -
- ผลรวมของปัจจัยสี่มีค่าเท่ากับ N
- ผลคูณของปัจจัยทั้งสี่มีค่ามากที่สุด
จะเห็นได้ว่าหากไม่สามารถระบุปัจจัยดังกล่าวได้ 4 ประการ ให้พิมพ์ว่า "เป็นไปไม่ได้" ควรสังเกตว่าปัจจัยทั้งสี่สามารถเท่ากันเพื่อเพิ่มผลผลิตได้มากที่สุด
อินพุต
N = 60
ผลลัพธ์
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625
เลือกปัจจัย 15 สี่ครั้ง
ดังนั้น 15+15+15+15 =60 และผลิตภัณฑ์จึงใหญ่ที่สุด
วิธีการ
วิธีการนี้ใช้ความซับซ้อนของ O(P^3) โดยที่ P คือจำนวนปัจจัยของ N ได้รับการอธิบายแล้ว
ดังนั้นวิธีที่มีประสิทธิภาพของความซับซ้อนของเวลา O(N^2) สามารถรับได้โดยทำตามขั้นตอนต่อไปนี้
- เราเก็บปัจจัยทั้งหมดของตัวเลขที่ระบุในคอนเทนเนอร์
- ตอนนี้ เราทำซ้ำสำหรับคู่ทั้งหมดและเก็บผลรวมในคอนเทนเนอร์อื่น
- เราต้องทำเครื่องหมายดัชนี (element1 + element2) ด้วยคู่ (element1, element2) เพื่อให้ได้องค์ประกอบที่ได้รับผลรวม
- เราทำซ้ำอีกครั้งสำหรับ pair_sums ทั้งหมด และตรวจสอบว่า n-pair_sum มีอยู่ในคอนเทนเนอร์เดียวกันหรือไม่ ส่งผลให้ทั้งคู่สร้างสี่เท่า
- ใช้อาร์เรย์แฮชของคู่เพื่อให้ได้องค์ประกอบที่ทั้งคู่สร้างขึ้น
- สุดท้าย ให้เก็บขนาดใหญ่ที่สุดของสี่เท่าทั้งหมด แล้วพิมพ์ออกมาในตอนท้าย
ตัวอย่าง
// 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;
} ผลลัพธ์
All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625
