資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢 N 的四個因數，使其乘積最大且和等於 N - 集-2
概念
關於給定的整數 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) 的有效方法。
- 我們將給定數字的所有因數儲存在一個容器中。
- 現在我們迭代所有對並將它們的和儲存在另一個容器中。
- 我們必須用 pair(element1, element2) 標記索引 (element1 + element2)，以便透過該和獲得的元素。
- 我們再次迭代所有 pair_sums，並驗證 n-pair_sum 是否存在於同一個容器中，因此這兩對形成了四元組。
- 實現 pair 雜湊陣列以獲得形成該對的元素。
- 最後，儲存所有此類四元組中最大的一個，並在最後列印它。
示例
// 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
更新於: 2020-07-24
71 次瀏覽
廣告