Chúng ta được cho một số dương N. Mục đích 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ông bằng nhau. N nằm trong khoảng [1,5000].
Chúng tôi sẽ làm điều này bằng cách sử dụng ba vòng lặp for cho 3 phần của số. Kiểm tra ở vòng lặp trong cùng xem tổng của cả ba bằng N. Nếu đúng, hãy tăng số lượng các cách.
Hãy cùng hiểu với 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ể được hiển thị dưới dạng tổng của (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ể được hiển thị dưới dạng tổng của:(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 tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một số nguyên N được khởi tạo với giá trị từ 1 đến 5000.
-
Hàm splitN (int n) nhận n và trả về số cách có thể chia n thành 3 phần.
-
Lấy số lượng biến ban đầu là 0 cho số cách.
-
Duyệt bằng cách sử dụng ba vòng lặp for cho mỗi phần của số.
-
Vòng ngoài cùng từ 1 <=i
-
Kiểm tra xem tổng của i, j và k có bằng n hay không. Nếu đúng thì số gia tăng.
-
Ở cuối tất cả các số vòng lặp sẽ có tổng số cách chia n thành ba phần.
-
Trả về kết quả là số lượng.
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<< "Number of ways to divide N in 3 parts : "<<divideN(N);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Number of ways to divide N in 3 parts: 20833