Ý 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ỳ

#1

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 ■■■ người ^^

1 Like
#2

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.
			}
		}
	}
}
7 Likes
#3

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

#4

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

2 Likes
#5

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++

#6 
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.

  • a = b = 1. => s = 4 -> Số c cao nhất có thể chọn là c = (int) 4 / 2 = 2 => Sẽ có thể chọn c = 1 hoặc 2
3 Likes
#7

Đây là 1 dạng toán có 1 bài điển hình là bài toán chia kẹo.

#8

Bạn có ý tưởng bài toán chia kẹo không ạ

#9

Ý tưởng của bài toán chia kẹo bây giờ rất nhiều trên google.com . Anh vui lòng lên google và search từ khoá Bài toán chia kẹo trong lập trình để biết thêm thông tin chi tiết :slight_smile:

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?