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

Đề tài: Nhờ chi dẫn hộ: Thuật toán sinh kế tiếp

  1. #1
    No Avatar
    meohoang8x Khách

    Arrow Nhờ chi dẫn hộ: Thuật toán sinh kế tiếp

    Xin các bác chỉ dẫn hộ: em không biết thuật toán sinh kế tiếp là gì mà thầy giáo lại ra mấy bài này dùng thuật toán sinh kế tiếp(em mới học C mà):
    1. Liệt kê các xâu nhị phân độ dài n.
    2. Liệt kê tất cả các xâu nhị phân thuận nghịch độc độ dài n.

  2. #2
    No Avatar
    meohoang8x Khách

    Không ai giúp em với à, em không biết nên hỏi các bác mà.Tủi thân quá.

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

    Thuật toán sinh ( ko rõ tiếng Anh là gì nữa ) cho bài toán "liệt kê các xâu nhị phân độ dài n" thì mình có học. Mình giới thiệu sơ qua một chút:
    + Với một bài toán cụ thể, người ta xây dựng nên một cái gọi là "cấu hình" và xác định cấu hình ban đầu + cấu hình kết thúc của bài toán ( cấu hình là gì thì sau khi đọc xong bạn có thể tưởng tượng ra ).
    + Cấu hình ban đầu có thể hiểu như là "đầu vào + điểm bắt đầu" của bài toán còn cấu hình kết thúc là "điểm kết thúc".
    + Người ta xây dựng một "hàm sinh" dựa trên thông tin cấu hình, sử dụng cấu hình ban đầu như một đầu vào để sinh ra "cấu hình kế tiếp", lại sử dụng cấu hình kế tiếp đó để sinh ra cấu hình tiếp theo nữa ... và khi nào đi đến "cấu hình kết thúc" thì bài toán dừng lại.
    Minh họa mã giả cho bài toán "liệt kê các xâu nhị phân độ dài n":
    Code:
    int config[n]; // mảng toàn cục để lưu thông tin cấu hình
                     // cũng là mảng các bit 0-1
    config_begin[] = 00...0; // cấu hình ban đầu gồm n số 0
    config_end[] = 11...1; // cấu hình kết thúc gồm n số 1.
    
    void next_config( config[] ) { // hàm sinh, nhận cấu hình trong mảng config 
                            // và sinh ra cấu hình kế tiếp, cũng lưu vào config
      if( config != config_end ) {
        // sinh ra cấu hình kế tiếp bằng cách sau
        int i = n-1; // làm chỉ số duyệt từ cuối mảng 
        while( i > 0 && config[i] != 0 ) // !=0 thì cũng là ==1
           config[i] = 0; 
        if( i > 0 )
           config[i] = 1;
      }
    }
    Như vậy ta đã sinh ra cấu hình kế tiếp bằng cách: duyệt từ cuối mảng về đầu mảng config( chứa dãy các bit 0-1 ) và tìm chỉ số đầu tiên == 0. Khi nào tìm thấy thì tăng nó lên 1 và trong quá trình "đi ngang qua" bit nào bằng 1 thì bật nó về 0. Nó chính là phép cộng nhị phân cấu hình nhận được với 1, cũng giống như cộng thập phân chẳng hạn: 18789999 + 1 = ?
    Vậy "liệt kê tất cả các xâu nhị phân thuận nghịch độc độ dài n" là sao? Mình chưa hiểu.
    Thân!
    Đã được chỉnh sửa lần cuối bởi whoru : 27-06-2007 lúc 09:29 AM. Lý do: Thêm thông tin vào bài
    Nơi nào khiến anh dừng bước, nơi đó có em.

  4. #4
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    uhm whoru nói vậy là chính xác rồi . Cách giải của bài cậu tương tự với việc sử dụng thuật toán sinh để liệt kê hoán vị tổ hợp hay chỉnh hợp , chỉ có điều là cấu hình sinh là 1 dãy 00000000 còn cấu hình cuối là 11111111 . không khác biệt gì nhiều đâu .

  5. #5
    No Avatar
    meohoang8x Khách

    Cảm ơn bác đã chỉ dẫn.
    Còn xâu NP thuận nghịch độc là xâu nếu đọc từ trái sang phải hay từ phải sang trái ta vẫn nhận được chính xâu đó, VD như 10100101 .

    Còn thuật toán sinh kế tiếp, tui có code như thế này không biết là có đúng không:
    Code:
     
    char *S;
    //Nhập n;
    for (i=0;i<n;i++) (S[i]='1)
    while (1) {
      i=n-1;
      while (S[i]=='1')  (S[i]='0'; i--)
      if (i==-1) break;
      s[i] = '1';
     // In ra S;
    }

  6. #6
    No Avatar
    N.V.T Khách

    Mặc định Nhờ chi dẫn hộ: Thuật toán sinh kế tiếp

    Liệt kê các xâu nhị phân độ dài n :
    Xâu nhị phân đầu tiên là 0000000...0000 ( n số 0 tương đương n bit) .
    Xâu nhị phân cuối cùng là 1111111...1111 (n số 1)
    Giả sử hiện tại b1,b2,b3...bn;
    Quy tắc sinh xâu nhị phân kế tiếp :
    Tìm chỉ sổ i đầ tiên từ phải qua trái thỏa mã bi = 0 .
    Gán lại bi = 1 và bj = 0 với tất cả j > i ;
    In ra xâu nhị phân kết tiếp .

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

    Code:
    char *S;
    //Nhập n;
    for (i=0;i<n;i++) (S[i]='1)
    while (1) {
      i=n-1;
      while (S[i]=='1')  (S[i]='0'; i--)
      if (i==-1) break;
      s[i] = '1';
     // In ra S;
    }
    Đoạn code này có lẽ ko sai ( mình ko chạy thử nên ko dám chắc ). Nó hơi khác một chút: bắt đầu bằng cấu hình 11...1 và sinh ra cấu hình tiếp theo giảm dần xuống 00...0. Tuy nhiên, việc sử dụng vòng while ko có kiểm tra "tràn chỉ số" theo mình là ko nên ( chỉ sử dụng khi bạn chắc chắn 100% nó ko bao giờ tràn chỉ số vì bạn đã kiểm soát chặt chẽ).
    Nếu bạn đã hiểu về "thuật toán sinh" của câu 1 thì câu 2 cũng ko khó gì, chỉ là một chút mẹo thôi. Theo như bạn nói "xâu NP thuận nghịch độc" là xâu đối xứng phải ko? Ta dùng cách sau để sinh cấu hình kế tiếp:
    Code:
    Ta dùng hàm sinh ( ở câu 1 ) cho một nửa sau của xâu ( chỉ số [n-1] -> [n/2] ). 
    Sau đó:
    for( int i = 0; i < n/2; i++ )
      config[i] = config[n-1-i];// lấy đối xứng cho nửa còn lại
    Chú ý:
    +Cấu hình bắt đầu và kết thúc vẫn như cũ.
    +Có thể dùng hàm sinh cho một nửa (đầu hoặc cuối) của mảng chứa cấu hình. Hai hàm sinh trong 2 trường hợp sẽ sinh cấu hình kế tiếp khác nhau. Tất nhiên là đều đúng.
    Thân!
    Đã được chỉnh sửa lần cuối bởi whoru : 29-06-2007 lúc 01:27 PM. Lý do: Cho rõ thêm
    Nơi nào khiến anh dừng bước, nơi đó có em.

  8. #8
    No Avatar
    meohoang8x Khách

    Cảm ơn whoru!!!

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Đã nói là thuật toán sinh thì meohoang ko thể viết như vậy được , code của meohoang là viết theo lối suy nghĩ để giải bài này thôi chứ ko thể gọi là theo thuật toán sinh mà ông thầy bảo .

    Nếu ứng dụng để viết cho tổ hợp thì code của meohoang gặp nhiều trục trặc và nhất là sau này khó mà "tái sử dụng" được .
    Thuật toán sinh nó có một khung tổng quát các hàm và tùy theo bài mà các hàm lại có 1 khả năng riêng . Do đó nếu cậu viết thì mọi người đọc rất dễ hiểu cũng như bảo trì nâng cấp .

  10. #10
    No Avatar
    meohoang8x Khách

    ừ thì tui cũng nghĩ theo cái thuật toán mà, cảm ơn đã chỉ chỗ sai cho tui.

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

  1. MacBook Pro 2012 - Đẳng cấp trong từng chi tiết - Giá bất ngờ cho Học Sinh - Sinh Viên!!!
    Gửi bởi nvhuu.nmslaptop trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 20
    Bài viết cuối: 27-05-2013, 12:48 PM
  2. Thuật toán C++ Thuật toán sinh tổng con kế tiếp trong C++ như thế nào?
    Gửi bởi ducvietphan trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 21-10-2012, 08:13 PM
  3. Trả lời: 6
    Bài viết cuối: 31-07-2012, 09:12 PM
  4. Vấn đề về thuật toán sinh kế tiếp
    Gửi bởi chanphat01001 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 24-10-2007, 05:41 AM
  5. Thuật toán sinh kế tiếp!
    Gửi bởi meohoang8x trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 17-10-2007, 07:44 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