Tìm các số A, B, C thỏa : A + B + C = N

Cho 3 vòng for lồng nhau là được. với n không quá lớn.

2 vòng for thôi
for i=1 -> n-2
for j = i -> n-i-1 {
k = n - i - j;
if (k >= j) -> i, j, k chinh la nghiem cua phuong trinh.
}

Mình có ý tưởng thế này

#include <stdio.h>
int main()
{
    int n, k;
    printf("Nhap n: ");
    scanf("%d", &n);
    if(n<3)
        printf("Khong thoa dieu kien!\n");
    else
    {
        for(int i=1; i<n; i++)
            for(int j=1; j<n; j++)
                if((k = n-i-j)>0)
                    printf("%d + %d + %d = %d\n", i, j, k, n);
    }
}

Cách của bác vẫn chưa loại được nghiệm trùng nhau

• N= 4, output:
1 + 1 + 2 = 4
1 + 2 + 1 = 4
2 + 1 + 1 = 4

1 1 2 với 2 1 1 vẫn tính khác nhau à :v

Bạn tự tưởng tượng ra bạn có n quả bóng.
Bạn đặt n quả bóng bạn có thành 1 hàng. Tiếp theo, giữa mỗi cặp của quả bóng liền kề, tự nhiên có 1 hàng rao từ trên trời rơi xuống hoặc không có gì cả.

Ví dụ: Bạn có 3 quả bóng, có khả năng bóng của bạn sẽ trông giống như thế này.

O|O|O    (111)
OO|O     (21)
O|OO     (12)
OOO      (3)

Hiển nhiên rằng, có 1 thoả thuận ngầm giữa cách sắp xếp bóng/hàng rào với các cặp số (combination numbers, *** éo biết tiếng việt của từ này) có tổng là n.

Từ đó, bạn có thể thấy rằng sẽ luôn có n - 1 hàng rào mà chúa trời ban cho bạn, cũng như có 2^(n-1) lần chúa trời ném hàng rào từ trên trời xuống hoặc không ném gì cả.

Do đó, thuật toán cho vấn đề này là: f(n) = 2^(n-1)

Chúc bạn may mắn!

PS: Tham khảo thêm http://mathworld.wolfram.com/Partition.html

Mình nhớ mang máng là bài toán quy hoạch động hình như có trong GT Lê Minh Hoàng ấy bạn xem thử.

Bài này không phải quy hoạch động đâu bạn. Bài này 3 vòng for lồng nhau là được rồi mà. Phía dưới là code của mình, có thể không tối ưu. Bạn có thể tham khảo

#include <iostream>

using namespace std;

int main()
{
    int n;
    cout << "nhap n: ";
    int dem=0;
    cin >> n;
    for(int i=1;i<n;i++)
        for(int j=1;j<n;j++)
            for(int k=1;k<n;k++)
                if(i+j+k==n){
                    cout << i << " + " << j << " + " << k << " = " << n << endl;
                    dem++;
                }
    cout << "Found: " << dem << endl;
    return 0;
}

Số lượng bộ 3 thõa mãn là: C²_n-1
###Chứng minh:

đặt x=a-1,y=b-1,c=z-1; biểu thức tương đương x+y+z=n-3
bài Toán quy về tìm bộ ba số tự nhiên có tổng = n-3. Có liên quan đến bài toán tổ hợp: số cách xếp n viên bi vào k hộp khác nhau là một bài toán tổ hợp lặp thường gặp:có kq = C^k-1_n+k-1
Thay vào n=n-3,k=3 được công thức trên

#include<conio.h>
#include<stdio.h>
int main()
{ int i,j,k;
int n;

	do{
	
	printf("Nhap vao gia tri cua n:");
	scanf("%d",&n);}while(n<3);
	for(i=1;i<n;i++)
	{
		for(j=1;j<n;j++)
		{
		k=n-i-j;
		if(k>0)
		{
			printf("Bo ba so do la %d-%d-%d\n",i,j,k);
		}
		}
	}
}

Theo output thi bo 3 so ko cần khác nhau phải ko vậy

Cảm ơn mọi người nhiều ! Mình đã hiểu được vấn đề rồi !