30/09/2018, 23:21

Ý tưởng cho thuật toán , tìm tất cả các cách để cộng ra một số nguyên bất kỳ

Em đang tìm ý tưởng cho thuật toán tìm tất cả các cách để cộng ra một số nguyên bằng 4 số nguyên dương a,b,c,d ( a<=b<=c<=d. )

N = 5 có 1 cách:
1+1+1+2
N = 6, có 2 cách:
1+1+1+3
1+1+2+2

em đang định dùng 4 vòng for để bắt các số kèm điều kiện nhưng chưa rõ làm thế nào cho hợp lý

cảm ơn mọi người ^^

X viết 01:28 ngày 01/10/2018

Mỗi bài toán thường có nhiều cách giải. Nếu dùng for thì đơn giản như thế này:

for(int a = 1; a < n; a++) {
	for(int b = a; b < n; b++) {
		for(int c = b; c < n; c++) {
			for(int d = c; d < n; d++) {
				if sum(abcd) = n then increment 'counter' by 1.
			}
		}
	}
}

Kiều Trang viết 01:34 ngày 01/10/2018

anh cho em hỏi 4 vòng for tại sao lại ko để tất cả xuất phát từ 1 ạ ?

X viết 01:29 ngày 01/10/2018

a<=b<=c<=d

Từ cái điều kiện của em đấy

Củ Chuối viết 01:38 ngày 01/10/2018

dùng thử quay lui, mình k biết nó có rườm rà hơn For hay ko. Nhưng cách này có thể tăng số nguyên dương từ 4 lên 5,6…N bất kỳ.
C++

Tuấn Nguyễn Văn viết 01:30 ngày 01/10/2018

int a, b, c, s, n, count = 0;
    
if(n < 4)
{
    cout << count;
    return 0;
}

for(int a = 1; a <= n - 3; a++)
{
    for(int b = a; b <= n - a - 1; b++)
    {
        s = n - (a + b);
        if(s >= 2 * b) // Có thể chọn được số c và d
        {
            c = s / 2;
            count += ((int) c - (b - 1));
        }
    }
}

Sau khi tính được a + b rồi thì c + d = n - (a + b). Do tính chất a <= b <= c <= d nên
c + d >= 2b thì mới có thể chọn các số c và d được. => Phần chênh lệch giữa (int) c - (b - 1) là số cách chọn 2 số c và d.
Ví dụ: N = 6.