Bài tổ hợp

[HaiLy]

tính tổ hợp chập k của n phần tử,các bác check hộ em code sai ở đâu,cám ơn các bác

//to hop chap k cua n phan tu VD:n=5 k=3      {1 2 3} ...{1 3 5} {1 4 5}... {3 4 5} 
#include<conio.h>
#include<stdio.h>
void main()
{
	int n,k,i,j;
        int x[30];
	printf("nhap n va k ");
	scanf("%d%d",&n,&k);
	for(i=0;i<k;i++)
		x[i]=i+1;
		
	while(i!=0)
        {
	   for(j=0;j<k;j++)
		   printf("%3d",x[j]);
	   i=k;
	   while ((i>0) && (x[i] = n-k+i))
				i--;
	   if(i>0)
          {
	    x[i]++;
	    for(j=i+1;j<k;j++)
		x[j]=x[j-1]+1;
          }
          printf("\n");
	
        }

getch();
}

[Ada]

Không giúp bạn chữa code nhưng có thể giúp bạn thuật toán (cả code) khác cho bài này:

http://forums.congdongcviet.com/showthread.php?t=8008

Thời gian sinh mỗi tổ hợp là O(1).

[HaiLy]

thuật toán là
-Tìm từ cuối dãy lên đầu cho tới khi gặp 1 phần tử x[i] chưa đạt giới hạn n-k+i:
i:=n;
while (i>0) and (x[i]=n-k+i) do i=i-1;
VD: (1,2,6,7,8,9)
-Nếu tìm thấy
if i>0 then
+Tăng x[i] đó lên 1
x[i]=x[i]+1;
(1,3,6,7,8,9)
+Đặt tất cả các phần tử sau x[i] bằng giới hạn dưới
for j=i+1 to k do x[j]=x[j-1]+1;
(1,3,4,5,6,7)
Nhưng khi chuyển thành đoạn code như trên lại ko đc

[Ada]

Code của bạn sau khi chữa, dịch và chạy thử trong gcc:

//to hop chap k cua n phan tu VD:n=5 k=3      {1 2 3} ...{1 3 5} {1 4 5}... {3 4 5}
#include<conio.h>
#include<stdio.h>
int main()
{
    int n,k,i,j;
    int x[30];
    printf("nhap n va k ");
    scanf("%d%d",&n,&k);
    for (i=1;i<=k;i++)
        x[i]=i;
    while (i!=0)
    {
        for (j=1;j<=k;j++)
            printf("%3d",x[j]);
        i=k;
        while ((i>0) && (x[i] >= n-k+i))
            i--;
        if (i>0)
        {
            x[i]++;
            for (j=i+1;j<=k;j++)
                x[j]=x[j-1]+1;
        }
        printf("\n");
    }
    getch();
}

Ví dụ

nhap n va k 6 4
  1  2  3  4
  1  2  3  5
  1  2  3  6
  1  2  4  5
  1  2  4  6
  1  2  5  6
  1  3  4  5
  1  3  4  6
  1  3  5  6
  1  4  5  6
  2  3  4  5
  2  3  4  6
  2  3  5  6
  2  4  5  6
  3  4  5  6

[HaiLy]

Thuật toán này theo em hiểu thì kiểm tra phần tử thứ i xem có bằng n-k+i hay ko,nếu ko thì tăng thêm 1.Code của bác cho đúng kết quả,nhưng nếu bỏ dấu > đi thì lại ko dc.Em ko hiểu tại sao x[i] phải >n-k+i

[Ada]

Thuật toán này theo em hiểu thì kiểm tra phần tử thứ i xem có bằng n-k+i hay ko,nếu ko thì tăng thêm 1.Code của bác cho đúng kết quả,nhưng nếu bỏ dấu > đi thì lại ko dc.Em ko hiểu tại sao x[i] phải >n-k+i

Nếu bạn ghét dấu >= thì thay nó bằng dấu ==, đừng thay bằng dấu =.
Và mình chưa già, đừng gọi mình là "bác". :P

[HaiLy]

ah uh nhỉ,phép so sánh,chưa già mà đã lẫn