นับจำนวนวิธีแบ่งจำนวนเป็น 3 ส่วนใน C++

ภาพรวมปัญหา

ให้จำนวนเต็มบวก N (1 ≤ N ≤ 5000) ต้องการนับจำนวนวิธีแบ่ง N เป็นผลรวมของ 3 จำนวนเต็มบวก ส่วนต่างๆ อาจเท่ากันหรือไม่เท่ากันก็ได้

ตัวอย่าง

Input: N = 5

Output: 2

คำอธิบาย: (1,1,3) และ (1,2,2)

Input: N = 9

Output: 7

คำอธิบาย: (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4), (3,3,3)

แนวทาง Naive (Three Nested Loops)

1. ฟังก์ชัน divideN(int n)
2. ใช้ 3 nested loops: i จาก 1 ถึง n-2, j จาก i ถึง n-1, k จาก j ถึง n
3. ถ้า i + j + k == n ให้เพิ่ม count
4. คืนค่า count

โค้ดตัวอย่าง (Naive)

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

int divideN(int n) {
    int count = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < n; j++) {
            for (int k = j; k < n; k++) {
                if (i + j + k == n) count++;
            }
        }
    }
    return count;
}

int main() {
    int N = 500;
    cout << "Number of ways: " << divideN(N);
    return 0;
}

ผลลัพธ์

Number of ways to divide N in 3 parts: 20833

แนวทางคณิตศาสตร์ที่มีประสิทธิภาพมากกว่า

จำนวนวิธีแบ่ง N เป็น 3 ส่วน (unordered partitions) มีสูตร:

round(N² / 12) หรือคำนวณได้จาก: ⌊(N² + 6) / 12⌋

โค้ดที่ปรับปรุงแล้ว

int divideN_fast(int n) {
    return (n * n + 6) / 12;
}

ความซับซ้อน

หมายเหตุ

วิธี Naive ใช้ได้กับ N ≤ 5000 แต่ช้า สูตร O(1) แนะนำสำหรับ N ใหญ่