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

Đề tài: Lập trình C | đưa ra tất cả tập con của 1 tập kí tự

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    3

    Question Lập trình C | đưa ra tất cả tập con của 1 tập kí tự

    mình làm bài này thì mắc vào 1 vấn đề mà mãi kô giải quyết được, (hình như có liên quan đến Quy hoạch động, mà mình chưa học).
    với 1 xâu có n kí tự thì sẽ có 2^n -2 tập kt con (bỏ rỗng và chính nó)
    giả sử
    Input : ABCD
    Output: A,B,C,D,AB,AC,AD,BC,BD,CD,ABC,ABD,ACD,BCD
    có (2^4)-2 =14.

    mình làm theo hướng mỗi tập kt con sẽ được biểu diễn = 1 số nhị phân đúng n bit. (n là số p tử xâu).

    ví dụ 0001 = D, 0011 = CD ..v..v

    nhưng bị hạn chế bộ nhớ lưu các xâu con vì nó lại phụ thuộc vào độ dài n.

    đây là code, đoạn này chỉ chạy đc với n=10, trên 10 là lỗi ngay

    PHP Code:
    #include <stdio.h>
    #include <string.h>
    #include <math.h>

    char N[100];     // Luu xau ban dau can tim xau con.
    char M[100];    // Luu xau nhi phan
    char xaucon[1024][100]; //Luu cac xau con
    int main(void)
     {
     
    int in,i,m;
     
    //bien in dung luu so trung gian khi tim nhi phan
     //Bien i,m dung chay vong lap
     
    int num;
     
    //Bien num dung luu so xau con cua 1 xau, num=2^(strlen)
     
    int xyjk,l;
     
    //Bien x luu 2 gia tri 0,1
     //bien y de lap
     //Bien j,k de tang
     
     
    printf("Nhap xau N: ");
     
    fflush(stdin);gets(N);
     
     
    num pow(2,strlen(N));
     
    printf("Se co %d xau con\n",num-2);

     for(
    m=1;m<num-1;m++)
     {
     
    =0;
     
    k=0;
     
    in=m;
     for(
    strlen(N)-1>= 0y--)
     {
      
    in / (<< y);
      
    in in * (<< y);
      if(
    x==0)
      {
      
    M[j]='0';
      }
      else
      {
      
    M[j]='1';
      }
      
    j++;
     }
     for(
    i=0;i<strlen(M);i++)
     {
        if(
    M[i]=='1')
        {
         
    xaucon[m-1][k]=N[i];
         
    k++;
        }
     }
     
    printf("\n---> Xau con so %d  = %s ",m,xaucon[m-1]);
     }
     return 
    1;


    vấn đề là ở biến xaucon, làm sao để không bị hạn chế vì độ dài n nhỉ, mình không rành C cho lắm nên bó tay

    thanks
    Đã được chỉnh sửa lần cuối bởi myNew : 26-11-2007 lúc 07:44 PM.

  2. #2
    Ngày gia nhập
    11 2007
    Bài viết
    3

    hic....bạn nào help tớ với.....:(( khẩn khẩn

  3. #3
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    char N[100]; // Luu xau ban dau can tim xau con.
    char M[100]; // Luu xau nhi phan
    char xaucon[1024][100]; //Luu cac xau con
    Tui nghĩ lỗi là do 3 cái này gây ra (tràn stack). Nếu đúng thì bạn giải quyết bằng cách cấp phát động.

    P/s: thuật toán đọc khó hỉu quá :(. Chắc tại tui dở :(
    Keep moving forward!

    ... Retired ...

  4. #4
    Ngày gia nhập
    11 2007
    Bài viết
    3

    Trích dẫn Nguyên bản được gửi bởi nhc1987 Xem bài viết
    Tui nghĩ lỗi là do 3 cái này gây ra (tràn stack). Nếu đúng thì bạn giải quyết bằng cách cấp phát động.

    P/s: thuật toán đọc khó hỉu quá :(. Chắc tại tui dở :(
    uh, thì do chỗ đó mà, với n phần tử thì sẽ có 2^n tập con, nếu lưu
    xaucon[1024][100]; tức là chỉ lưu số xâu con của 1 xâu 10 ptử (2^10 =1024)

    ....

    Cấp phát động là sao nhỉ:">, mà bạn nào có thuật toán hay hơn chỉ tớ với....

  5. #5
    Ngày gia nhập
    02 2007
    Nơi ở
    TP.HCM - dưới cầu SG
    Bài viết
    12

    Theo mình nghĩ, bài toán có thể giải quyết một cách đơn giản hơn bạn nghĩ: ta đâu cần phải lưu các chuỗi nhị phân biểu diễn cho 1 xâu con?! Ứng với 1 số nguyên từ 1->2^n - 1 bạn in trực tiếp xâu con cho nó. Minh họa sau với giả sử bạn đã lưu các ký tự của chuỗi ban đầu trong mảng a[n]:
    Code:
    for( i = 1; i < 2 ^ n - 1; i++ ) {
      // in tổ hợp tương ứng với chuỗi i ra
      // chẳng hạn i = 1101 -> in ABD ra
      for( j = 0; j < n; j++ ) {
         if( i & ( 1<< ( n - j - 1))) // bit tương ứng với ký tự a[j] = 1
            cout << a[j];
      } 
      cout << ", ";
    }
    Nếu bạn muốn in theo đúng thứ tự, chẳng hạn A,B,C,D, AB, AC, AD,BC, BD, CD, ABC..., thì có lẽ bạn phải dùng cách khác.
    Thân!
    Nơi nào khiến anh dừng bước, nơi đó có em.

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