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

Đề tài: [Solved]Duyệt tập con của n phần tử!

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

    Unhappy [Solved]Duyệt tập con của n phần tử!

    Duyệt mọi tập con của tập hợp 1,2,..n.Dữ liệu vào cho bởi file tapcon.in.kết quả ghi lại trong file bài1.out.
    Code:
    tapcon.in		tapcon.out
    3			1
    			2
    			2	1
    			3
    			3	1
    			3	2
    			3	2	1
    Mình nghĩ mãi không ra.Mong các bạn giúp!

  2. #2
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Cái này là bài cơ bản về đọc file thôi bạn, bạn search một tí trên 4rum sẽ ra. Để cho dễ mình nghĩ bạn dùng các hàm đọc file của thự stdio.h cho dễ, ví dụ như fscanf, fgets
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

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

    Mình không biết code phần in ra như hình trên thôi!Bạn có thể giúp mình không?

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

    Đây là 1 bài đệ quy "rất rất" cơ bản. Bạn nên cố gắng suy nghĩ trước khi hỏi người khác!

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

    Trích dẫn Nguyên bản được gửi bởi bobby_tran Xem bài viết
    Đây là 1 bài đệ quy "rất rất" cơ bản. Bạn nên cố gắng suy nghĩ trước khi hỏi người khác!
    Who is this ?

    PS: Mèo ơi cậu hướng dẫn sơ sơ vấn đề của chủ topic đi, mình thấy lạ lạ, nhòm tí.

  6. #6
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    Mặc định [Solved]Duyệt tập con của n phần tử!

    Bài này có nhiều cách làm, bạn có thể làm theo cách của mình như sau, tuy cách này hơi chuối.

    Ý tưởng như sau: số tập con của tập có n phần tử = 2^n - 1 (không kể tập rỗng), tương ứng với các chuỗi nhị phân n bit từ 0..001 --> 1..111.

    Code:
    Đọc từ file vào số n.
    
    Đặt biến int maxBin = số nhị phân lớn nhất có n bit 1 (maxBin = (1 << n) - 1)
    (vd n = 10, thì maxBin = 1023, n = 8 thì maxBin = 255.)
    
    Cho vòng lặp for (int i chạy từ 1 --> maxBin)
    {
        Đổi số i ra chuỗi nhị phân strBin n bit (ví dụ i = 10 --> strBin = "00..001010")
    
        Đặt biến index = 1; (chỉ số thứ tự chạy vòng lặp)
        Cho vòng lặp for duyệt từng bit của strBin từ bên phải sang trái.
        {
            bit nào = 1 thì in ra số index, còn = 0 thì không in.
            index = index + 1;
        }
    
        (vd lúc đó i = 10 ứng với strBin = "0..001010", thì in ra 2 4)
        (vd lúc đó i =  8 ứng với strBin = "0..000111", thì in ra 1 2 3)
    }
    Đã được chỉnh sửa lần cuối bởi DKhanh : 27-10-2008 lúc 08:20 AM.

  7. #7
    Ngày gia nhập
    10 2008
    Bài viết
    18

    Trích dẫn Nguyên bản được gửi bởi daigiakotien Xem bài viết
    Mình không biết code phần in ra như hình trên thôi!Bạn có thể giúp mình không?
    \r : Xuống hàng mới

    Bạn áp dụng cai này là ok.
    Còn giải thuật thì cơ bản thôi mình tin là bạn làm được.

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

    Cám ơn mọi người!Mình hiểu rồi.Nhưng có thể hướng dẫn mình chỗ:
    Đổi số i ra chuỗi nhị phân strBin n bit (ví dụ i = 10 --> strBin = "00..001010")

  9. #9
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    Trích dẫn Nguyên bản được gửi bởi daigiakotien Xem bài viết
    Cám ơn mọi người!Mình hiểu rồi.Nhưng có thể hướng dẫn mình chỗ:
    Đổi số i ra chuỗi nhị phân strBin n bit (ví dụ i = 10 --> strBin = "00..001010")
    Không nhất thiết là phải đổi ra chuỗi nhị phân, bạn có thể dùng các toán tử trên bit để lấy từng bit của nó ra. Hoặc bạn cũng có thể dùng quy tắc nào đó sinh ra số nhị phân tiếp theo lớn hơn số nhị phân trước đó.

    Code cụ thể như thế này:

    C++ Code:
    1. #include "stdafx.h"
    2.  
    3. #define N 3
    4.  
    5. void main()
    6. {
    7.     int a[N+1] = {0};
    8.     int n_subset = 0;
    9.  
    10.     for (;;)
    11.     {
    12.         // ------ đổi các bit 1 đầu tiên thành 0 ------
    13.         int i = 0;
    14.         while (a[i])
    15.         {
    16.             a[i++] = 0;
    17.         }
    18.  
    19.         if (i == N) break;
    20.  
    21.         // ----- và đổi bit 0 đầu tiên bên trái thành 1 -----
    22.         a[i] = 1;
    23.  
    24.         // ------- in tập con ra màn hình -----
    25.         for (i = 0; i < N; ++i)
    26.         {
    27.             if (a[i])
    28.             {
    29.                 cout << i + 1 << "  ";
    30.             }
    31.         }
    32.  
    33.         cout << endl;
    34.         ++n_subset;
    35.     }
    36.     cout << "Number of subset: " << n_subset << endl;
    37.     getch();
    38. }

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

  1. Trả lời: 6
    Bài viết cuối: 31-07-2013, 07:51 PM
  2. Phần Euler và phần duyệt theo chiều rộng (DFS) chạy sai kết quả?
    Gửi bởi hoangde102 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 09-05-2012, 09:37 AM
  3. Cấu trúc dữ liệu Duyệt các phần tử bên phải của cây nhị phân
    Gửi bởi giacmo1612 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 7
    Bài viết cuối: 10-12-2011, 09:08 AM
  4. Cách thức duyệt tiền tự trên cây khi duyệt từ con trái nhất rồi sang anh em ruột phải?
    Gửi bởi tyrant trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 14-09-2011, 10:53 AM
  5. [ Solved ]Duyệt đồ thị bằng BFS cần giúp đỡ T_T !
    Gửi bởi rox_rook trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 21-11-2008, 07:09 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