home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

เพิ่มผลคูณของ 4 ตัวประกอบของจำนวน N ให้สูงสุดใน C++

งานคือหาผลคูณสูงสุดของ 4 ตัวประกอบ (factors) A, B, C, D ของจำนวน N โดยมีเงื่อนไข: A + B + C + D = N และ A,B,C,D ต้องเป็นตัวประกอบของ N ทั้งหมด

ตัวอย่าง

N = 10

ตัวประกอบ: 1, 2, 5, 10

ลองทุกชุด 4 ตัวที่รวมได้ 10:

5+2+2+1 = 10 → 5×2×2×1 = 20 ← สูงสุด
5+5+?+? → เกิน 10
10+... → เกิน 10

Output: 20

N = 16

ตัวประกอบ: 1, 2, 4, 8, 16

4+4+4+4 = 16 → 4×4×4×4 = 256 ← สูงสุด

Output: 256

แนวทางแก้ปัญหา (Brute Force บนตัวประกอบ)

  1. หาตัวประกอบทั้งหมดของ N → เก็บใน array factors[]
  2. วนลูป 4 ชั้น (i,j,k,l) บน index ของ factors[]
  3. ถ้า factors[i]+factors[j]+factors[k]+factors[l] == N คำนวณผลคูณ
  4. เก็บค่าสูงสุด

ตัวอย่างโค้ด (แก้ไขจากต้นฉบับ)

#include <bits/stdc++.h>
using namespace std;

vector<int> findFactors(int N) {
    vector<int> factors;
    for (int i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            factors.push_back(i);
            if (i != N / i) factors.push_back(N / i);
        }
    }
    return factors;
}

int maxProductFourFactors(int N) {
    vector<int> factors = findFactors(N);
    int maxProd = 0;
    int sz = factors.size();
    
    for (int i = 0; i < sz; i++)
        for (int j = 0; j < sz; j++)
            for (int k = 0; k < sz; k++)
                for (int l = 0; l < sz; l++) {
                    int sum = factors[i] + factors[j] + factors[k] + factors[l];
                    if (sum == N) {
                        int prod = factors[i] * factors[j] * factors[k] * factors[l];
                        maxProd = max(maxProd, prod);
                    }
                }
    return maxProd;
}

int main() {
    int N = 10;
    cout << "Max product: " << maxProductFourFactors(N) << endl;
    N = 16;
    cout << "Max product: " << maxProductFourFactors(N) << endl;
    return 0;
}

ผลลัพธ์

Max product: 20
Max product: 256

การปรับปรุงประสิทธิภาพ

ลูป 4 ชั้นเป็น O(F⁴) โดย F = จำนวนตัวประกอบ (สำหรับ N ≤ 10⁵, F ≤ ~128 ยังทำงานได้เร็ว)

สามารถลดเหลือ O(F³) โดยคำนวณตัวที่ 4: l_val = N - (a+b+c) แล้วเช็คว่าเป็น factor หรือไม่ (ใช้ hash set)

ข้อสังเกตจากโค้ดต้นฉบับ

  • โค้ดต้นฉบับมี bug: int size = K+1 แต่ K คือตัวนับจำนวน factors → ควรเป็น K ไม่ใช่ K+1
  • ใช้ global array Factors[30] ขนาดคงที่ – ควรใช้ vector
  • Output บอก "Maximum Profit: 20" แทน "Max product" – คัดลอกผิด

ข้อคิดเพิ่มเติม (Mathematical Insight)

จาก AM-GM: ผลคูณ 4 ตัวที่มีผลรวมคงที่ = N จะมากที่สุดเมื่อ 4 ตัวเท่ากันคือ N/4

แต่ต้องเป็นตัวประกอบของ N → คำตอบคือ "ตัวประกอบที่ใกล้ N/4 มากที่สุด" ใช้ซ้ำ 4 ครั้ง (ถ้ารวมได้ N)

เช่น N=16, N/4=4 → 4 เป็นตัวประกอบ → 4×4×4×4=256

N=10, N/4=2.5 → ตัวประกอบใกล้ที่สุดคือ 2 และ 5 → 5+2+2+1=10 (ใช้ 5,2,2,1)