Nhờ mọi người góp ý code chia 1 dãy số có K nhóm (tập con) sao cho tổng bằng nhau

[Tuan_Nguyen97 (Tuấn Nguyễn)]

Chương trình này không in ra được kết quả, em đã tìm không biết sai ở chỗ nào ? Mong anh, chị giúp đỡ , xem giùm em!

hình ảnh:
absc|690x356

Chương trình của em :
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>


int Kttong(int tongTrai[], int k) // kiem tra xem tat ca tap hop con lap day hay chua
{
	int r = true;
	for (int i = 0; i < k; i++)
	{
		if (tongTrai[i] != 0)
			r = false;
	}
	return r;
}
int THtong(int S[], int n, int tongTrai[], int A[], int k)
{
	if (Kttong(tongTrai, k))
		return true;
	if (n < 0)
		return false;
		
int res = false;
	// ky thuat quay lui
	for (int i = 1; i <= k; i++)
	{
		if (!res && (tongTrai[i] - S[n]) >= 0)
		{
			A[n] = i + 1;
			tongTrai[i] = tongTrai[i] - S[n];
			res = THtong(S, n - 1, tongTrai, A, k);
			tongTrai[i] = tongTrai[i] + S[n];
		}
	}
	return res;
}

int sum(int a[], int n, int s) // tinh tong day so
{ 
    int i;
    for(i = 0 ;i < n; i++)
        s = s + a[i];
    return s;
}

void chianhom(int S[], int n, int k)
{
	
	if (n < k)
	{
		printf("\nKhong co nhom nao phu hop");
		return;
	}
	


 	int A[n], tongTrai[k];
 	for (int i = 0; i < k; i++)
		tongTrai[i] = sum(S, n, 0) / k;

	int res = (sum(S, n, 0)  / k) && THtong(S, n - 1, tongTrai, A, k); // liet ke nhom nao có tong gan bang nhau 
		
		if (n - 1 <= res <= n + 1)
{ 
	for (int i = 1; i <= k; i++)
	{	printf("\nNhom %d la: ", i);
	   	for (int j = 0; j < 8; j++)
	 		if (A[j] == i + 1)
	 		printf (" %d ", A[j]);

	}
}
		else
		printf("\nKhong co nhom nao phu hop");
		
	
}
int main()
{
	int S[]={4, 3 , 2 , 1 , 7, 9, 6, 5 ,1};
	int	n = sizeof(S) / sizeof(S[0]);
	//printf("\n%d ",n);
	int k = 3;
	chianhom(S, n, k);
	return 0;
}

[hungaya (Hung)]

Bạn có thể giải thích thêm bạn đang giải quyết vấn đề nào không? Như dãy S mà bạn khai báo nếu chạy xong được tách như thế nào?

int S[] = { 4, 3 , 2 , 1 , 7, 9, 6, 5 ,1 };

Ý nghĩa của từng hàm Kttong(), THTong(), sum(), chianhom()?

Với lại bạn upload lại hình nhé, khi mình xem raw thì url của hình không có domain gì cả.

[Tuan_Nguyen97 (Tuấn Nguyễn)]

Bài em muốn làm liệt kê được tập con (nhóm) K với điều kiện tổng những tập con gần bằng nhau

Hàm Kttong() kiểm tra xem tập hợp (nhóm) đó rỗng hay đã đầy
Hàm THtong là để tính tổng từng tập hợp con trong mảng S, sử dụng kỹ thuật quay lui

vd như S[i] + S[i+1] là 1 tập hợp con, …
Sum để tính tổng
chianhom() là để chọn tập hợp con có tổng bằng nhau

hình em up lại

chia day so K nhom co tong bang nhau.PNG

[hungaya (Hung)]

Mình vẫn chưa hiểu chỗ quay lui của bạn như thế nào?

Tuy nhiên, có vài chỗ bạn cần sửa:

Đầu tiên, mảng A[n] trong chianhom(), bạn chỉ khai báo là int A[n] nhưng chưa gán giá trị ban đầu cho từng phần tử A[i], với 0 <= i < n.

Thứ 2, là toán tử &&:

int res = (sum(S, n, 0)  / k) && THtong(S, n - 1, tongTrai, A, k);

Trong C, && chỉ trả về giá trị 0 và 1, nên res chỉ nhận giá trị 0 và 1, bạn nên sửa lại thành câu lệnh if else tường minh hơn.

int res = sum(S, n, 0) / k;
if (res) {
  res = THtong(S, n-1, tongTrai, A, k);
}

Thứ 3, phần câu lệnh if:

if (n - 1 <= res <= n + 1) {
  ...
}

Sửa lại thành

if (n - 1 <= res && res <= n + 1) {
  ...
}

---

Nếu sửa lại hết thì sẽ ra output là: “Khong co nhom nao phu hop”.

Còn với code ban đầu, do res nhận 0 hoặc 1, nhưng n = 9 nên biểu thức trong if thực hiện như sau, làm cho câu lệnh trong if luôn thực hiện, bất kể res nhận giá trị nào.

n-1 <= res <= n+1
9-1 <= res <= 9+1
8 <= { 0; 1 } <= 10
(8 <= { 0; 1 }) <= 10
0 <= 10
1

[Tuan_Nguyen97 (Tuấn Nguyễn)]

thuật toán em định làm
vd S = { 3,4, 5,2,7,1,8}
i=0
A[] = S[i] (tức là =3) + S[i+1] (tức là=4) ;
tiếp theo
3+5;
3+2;
…
lần lượt đến
4+5 ;…
sau khi cộng hết 2 số nó tới cộng 3 số…

code

for (int i = 1; i <= k; i++)
{
	if (/*!res && */(tongTrai[i] - S[n]) >= 0)
	{
		A[n] = i +1;
		tongTrai[i] = tongTrai[i] - S[n];  // tạo ra  tập hợp con thứ i

		res = THtong(S, n - 1, tongTrai, A, k); // gọi lại hàm THtong để tính tổng tập hợp con khác

		tongTrai[i] = tongTrai[i] + S[n]; //backtracking - xóa mục hiện tại khỏi tập hợp con thứ i
	}
}

[Tuan_Nguyen97 (Tuấn Nguyễn)]

mảng A[n] trong chianhom()
em định gán cho hàm sum(S,n,0) khi tính tổng ra thêm vào mảng A[n]