โปรแกรม C++ หาจำนวนวิธีการเขียนเลขเป็นผลรวมของเลขที่เล็กกว่า

โปรแกรมนับจำนวน partition (การแยกส่วน) ของจำนวนเต็ม n โดยใช้ผลรวมของจำนวนเต็มบวกที่เล็กกว่า n เอง

อัลกอริทึม partitionCount(n)

1. สร้างอาร์เรย์ p ขนาด n, เริ่มต้น p[0] = n
2. วนลูปสร้าง partition ใหม่ๆ โดยลดค่าลงทีละ 1 และกระจายเศษ
3. นับจำนวน partition จนกว่าจะเหลือแต่ 1

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

int partitionCount(int n) {
    int p[n], k = 0, count = -1;
    p[k] = n;
    while (true) {
        count++;
        int rem = 0;
        while (k >= 0 && p[k] == 1) { rem += p[k]; k--; }
        if (k < 0) return count;
        p[k]--; rem++;
        while (rem > p[k]) { p[k+1] = p[k]; rem -= p[k]; k++; }
        p[k+1] = rem; k++;
    }
}

int main() {
    int n; cin >> n;
    if (n <= 0) { cout << "Invalid"; exit(1); }
    cout << "Partitions: " << partitionCount(n);
}

ผลลัพธ์

Enter number: 7
The number of partitions: 14

หมายเหตุ: n=7 มี partition 14 แบบ (7, 6+1, 5+2, 5+1+1, 4+3, 4+2+1, 4+1+1+1, 3+3+1, 3+2+2, 3+2+1+1, 3+1+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1)