หาตัวประกอบ 4 ตัวของ N ผลคูณมากสุด ผลรวมเท่า N

แนวคิด

ได้รับจำนวนเต็ม N ให้หาตัวประกอบทั้งหมดของ N และพิมพ์ผลคูณของตัวประกอบ 4 ตัวของ N ที่ทำให้:

ผลรวมของตัวประกอบ 4 ตัวเท่ากับ N
ผลคูณของตัวประกอบ 4 ตัวมากที่สุด

หากไม่สามารถหาตัวประกอบ 4 ตัวได้ ให้พิมพ์ "Not possible" หมายเหตุ: ตัวประกอบทั้ง 4 ตัวสามารถเท่ากันได้เพื่อให้ผลคูณมากที่สุด

อินพุต

N = 60

เอาต์พุต

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60 Product is -> 50625

เลือกตัวประกอบ 15 4 ครั้ง,

ดังนั้น 15+15+15+15 = 60 และผลคูณมากที่สุด

วิธีการ

วิธีที่ใช้ความซับซ้อน O(P^3) โดย P คือจำนวนตัวประกอบของ N ได้รับการอธิบาย

ดังนั้นวิธีที่มีประสิทธิภาพความซับซ้อน O(N^2) สามารถทำได้ด้วยขั้นตอน:

เก็บตัวประกอบทั้งหมดของจำนวนที่กำหนดในคอนเทนเนอร์
วนลูปทุกคู่และเก็บผลรวมในคอนเทนเนอร์อื่น
ทำเครื่องหมายดัชนี (element1 + element2) ด้วย pair(element1, element2) เพื่อรับสมาชิกที่ได้ผลรวม
วนลูปทุก pair_sum อีกครั้ง ตรวจสอบว่า n-pair_sum อยู่ในคอนเทนเนอร์เดียวกันหรือไม่ ทำให้ทั้งสองคู่สร้าง quadruple
ใช้ pair hash array เพื่อรับสมาชิกที่สร้างคู่
สุดท้าย เก็บ quadruple ที่มากที่สุดและพิมพ์ท้ายสุด

ตัวอย่างโค้ด C++

// โปรแกรม C++ หาตัวประกอบ 4 ตัวของ N
// ที่ผลคูณมากที่สุดและผลรวมเท่ากับ N
#include <bits/stdc++.h>
using namespace std;

// ฟังก์ชันหาตัวประกอบและพิมพ์ตัวประกอบ 4 ตัว
void findfactors1(int q) {
    vector<int> vec1;
    // ใส่ตัวประกอบทั้งหมดในเวกเตอร์
    for (int i = 1; i * i <= q; i++) {
        if (q % i == 0) {
            vec1.push_back(i);
            vec1.push_back(q / i);
        }
    }
    // เรียงเวกเตอร์
    sort(vec1.begin(), vec1.end());
    // พิมพ์ตัวประกอบทั้งหมด
    cout << "All the factors are -> ";
    for (int i = 0; i < vec1.size(); i++)
        cout << vec1[i] << " ";
    cout << endl;
    
    // ทุกตัวเลขหาร 1 ลงตัว
    int maxProduct1 = 1;
    bool flag1 = 1;
    // ใช้ 3 ลูปหาตัวประกอบ 3 ตัวที่มากที่สุด
    for (int i = 0; i < vec1.size(); i++) {
        for (int j = i; j < vec1.size(); j++) {
            for (int k = j; k < vec1.size(); k++) {
                // เก็บตัวประกอบตัวที่ 4 ใน y
                int y = q - vec1[i] - vec1[j] - vec1[k];
                // หากตัวที่ 4 เป็นลบ ให้ break
                if (y <= 0)
                    break;
                // แทนที่ด้วยตัวเลขที่เหมาะสมกว่าเดิม
                if (q % y == 0) {
                    flag1 = 0;
                    maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] * y, maxProduct1);
                }
            }
        }
    }
    // พิมพ์ผลคูณหากมีตัวเลข
    if (flag1 == 0)
        cout << "Product is -> " << maxProduct1 << endl;
    else
        cout << "Not possible" << endl;
}

// โค้ดหลัก
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

หาตัวประกอบ 4 ตัวของ N ผลคูณมากสุด ผลรวมเท่า N - เซต 2 ใน C++

แนวคิด

อินพุต

เอาต์พุต

วิธีการ

ตัวอย่างโค้ด C++

เอาต์พุต