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

Đề tài: giúp em liệt kê tập con k của n phần tử ?

  1. #1
    Ngày gia nhập
    04 2008
    Bài viết
    27

    Wink giúp em liệt kê tập con k của n phần tử ?

    Ví dụ :
    em có mảng 4 phần tử ( 3 , 10 , 20 , 30 )

    Em sẽ có
    3 20 30
    3 10 30
    3 10 20
    10 20 30

    4 phần tử có thể là 1 số nào đó bất kì
    Mong các anh chị giúp đỡ em về thuật toán và có thể cho em xem đoạn code C cài đặt luôn nha ! Thanks

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    607

    Code:
    /*===================================================================*/
    /* C program for distribution from the Combinatorial Object Server.  */
    /* Generates the k-combinations of [n] by transpositions via a       */
    /* direct algorithm (see the book for what "direct" means).          */
    /* No input error checking.  Assumes 0 <= k <= n <= MAX.             */
    /* Outputs both the bitstring and the transposition (x,y) (meaning   */
    /* that x leaves the subset and y enters).                           */
    /* Algorithm is CAT (Constant Amortized Time).                       */
    /* The program can be modified, translated to other languages, etc., */
    /* so long as proper acknowledgement is given (author and source).   */     
    /* Programmer: Frank Ruskey, 1995.                                   */
    /* The latest version of this program may be found at the site       */
    /* http://theory.cs.uvic.ca/inf/comb/CombinationsInfo.html            */
    /*===================================================================*/
    
    #define MAX 100   /* maximum value of n */
    
    int b[MAX+1];
    int n, k;
    int cnt=0;
    
    void PrintIt ( int x, int y ) {
      int i;
      printf( "%8d: ", ++cnt );
      for ( i=1; i<=n; ++i ) printf( "%d ", b[i] );  
      if (x != 0) printf( "     (%d,%d)", x,y ); 
      printf( "\n" );
    } /*of PrintIt*/;
    
    void swap ( int x, int y ) {
      int t;
      b[x] = 1;  b[y] = 0;
      PrintIt( x, y ); 
    } /* of swap */;
    
    void NEG ( int n, int k );
    void GEN ( int n, int k ); 
    
    void GEN ( int n, int k ) {
      if (k > 0 && k < n) {
         GEN( n-1, k );
         if (k == 1) swap( n, n-1 );  else swap( n, k-1 );
         NEG( n-1, k-1 );
      }
    } /* of GEN */;
    
    void NEG ( int n, int k ) {
      if (k > 0 && k < n) {
         GEN( n-1, k-1 );
         if (k == 1) swap( n-1, n );  else swap( k-1, n );
         NEG( n-1, k );
      }
    } /* of NEG */;
    
    void main () {
      int i;
      printf( "Enter n,k: " );  scanf( "%d %d", &n, &k );
      for ( i=1; i<=k; ++i) b[i] = 1;
      for ( i=k+1; i<=n; ++i) b[i] = 0;
      PrintIt( 0, 0 ); 
      GEN( n, k );
    }
    Ví dụ:

    Code:
    Enter n,k: 5 3
           1: 1 1 1 0 0
           2: 1 0 1 1 0      (4,2)
           3: 0 1 1 1 0      (2,1)
           4: 1 1 0 1 0      (1,3)
           5: 1 0 0 1 1      (5,2)
           6: 0 1 0 1 1      (2,1)
           7: 0 0 1 1 1      (3,2)
           8: 1 0 1 0 1      (1,4)
           9: 0 1 1 0 1      (2,1)
          10: 1 1 0 0 1      (1,3)
    Hướng dẫn hack:

    Các hàm gen() và neg() thực thi thuật toán. Chúng làm việc với tập hợp {1,...,n}. Chúng hoàn toàn độc lập với cấu trúc dữ liệu của tập hợp mẹ (n phần tử) và tập con (k phần tử). Chúng không biết và không cần biết cấu trúc dữ liệu của các tập hợp này.

    Hàm swap() và printit() làm việc với cấu trúc dữ liệu. swap(x,y) có tác dụng đưa x vào tập con và lấy y ra khỏi tập con. printit() xuất cấu trúc dữ liệu ra màn hình.

    Bởi thế, nếu muốn nhập và xuất ra theo dạng yêu cầu của đề bài, hãy sửa các hàm swap(), printit() và viết một hàm, chẳng hạn scanit(), để nhập dữ liệu.

    Ví dụ, theo đề bài này của bạn, thì

    + Tập hợp mẹ được thực thi bằng một mảng a[1...n] chứa các số bất kỳ. Tham số x, y cho swap(x,y) là 2 chỉ số của phần tử trong mảng. Chỉ số chạy từ 1 đến n vì gen() và neg() làm việc trên tập {1...n}.

    + Tập hợp con có thể được thực thi bằng mảng con a[1...k] của mảng a[1...n] nói trên. Khi đó swap(x,y) sẽ phải hoán đổi giá trị a[x] với a[y].

    + scanit() sẽ phải nhập tập hợp mẹ, tức là nhập a[1...n].

    + printit() sẽ phải xuất tập hợp con, tức là xuất a[1...k].
    Đã được chỉnh sửa lần cuối bởi Ada : 16-05-2008 lúc 12:53 PM.

Các đề tài tương tự

  1. Trả lời: 0
    Bài viết cuối: 16-03-2012, 07:05 PM
  2. cách ghi phần tử vào mảng lập trình c#.giúp em với
    Gửi bởi hoangkien trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 01-04-2011, 09:41 PM
  3. kiểm tra phần cứng máy tính, giúp mình?
    Gửi bởi huutrieu2005 trong diễn đàn Thắc mắc chung
    Trả lời: 6
    Bài viết cuối: 25-03-2009, 01:53 PM

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