Đếm số cách chia một số thành 3 phần trong C++

Cho một số nguyên dương N. Mục tiêu là đếm số cách chia số N thành 3 phần. Các phần có thể bằng nhau hoặc khác nhau. N nằm trong khoảng [1, 5000].

Ta thực hiện bằng cách dùng ba vòng lặp for cho 3 phần của số. Kiểm tra ở vòng lặp trong nhất xem tổng của ba phần có bằng N không. Nếu đúng thì tăng biến đếm số cách.

Hãy hiểu qua các ví dụ.

Đầu vào − N=5

Đầu ra − Số cách chia N thành 3 phần: 2

Giải thích − 5 có thể biểu diễn thành tổng (1,1,3) và (1,2,2)

Đầu vào − N=9

Đầu ra − Số cách chia N thành 3 phần: 7

Giải thích − 9 có thể biểu diễn thành tổng: (1,1,7), (1,2,6), (1,3,5), (1,4,4), (2,2,5), (2,3,4) và (3,3,3).

Phương pháp sử dụng trong chương trình dưới đây

• Nhận số nguyên N giá trị từ 1 đến 5000.
• Hàm divideN(int n) nhận n và trả về số cách chia n thành 3 phần.
• Khởi tạo biến count = 0 cho số cách.
• Duyệt bằng ba vòng lặp for cho mỗi phần của số.
• Vòng ngoài: 1 <= i < n, vòng giữa: i <= j < n, vòng trong: j <= k < n.
• Kiểm tra nếu tổng i, j, k bằng n. Nếu đúng tăng count.
• Sau tất cả vòng lặp count sẽ chứa tổng số cách chia n thành 3 phần.
• Trả về count làm kết quả.

Ví dụ

#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++) {
                int sum = i + j + k;
                if(sum == n) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int N = 500;
    cout << endl << "Số cách chia N thành 3 phần: " << divideN(N);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số cách chia N thành 3 phần: 20833