Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Bài tổ hợp

  1. #1
    Ngày gia nhập
    05 2008
    Nơi ở
    HàNội™
    Bài viết
    4

    Angry Bài tổ hợp

    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
    Code:
    //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();
    }
    Đã được chỉnh sửa lần cuối bởi HaiLy : 22-05-2008 lúc 11:23 PM.

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    448

    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).

  3. #3
    Ngày gia nhập
    05 2008
    Nơi ở
    HàNội™
    Bài viết
    4

    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

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    448

    Code của bạn sau khi chữa, dịch và chạy thử trong gcc:
    Code:
    //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ụ
    Code:
    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
    Đã được chỉnh sửa lần cuối bởi Ada : 23-05-2008 lúc 11:28 AM.

  5. #5
    Ngày gia nhập
    05 2008
    Nơi ở
    HàNội™
    Bài viết
    4

    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

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    448

    Mặc định Bài tổ hợp

    Trích dẫn Nguyên bản được gửi bởi HaiLy Xem bài viết
    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

  7. #7
    Ngày gia nhập
    05 2008
    Nơi ở
    HàNội™
    Bài viết
    4

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

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn