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

[daigiakotien]

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.

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!

[meoconlongvang]

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

[daigiakotien]

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?

[bobby_tran]

Đâ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!

[tiger86love102]

Đâ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í.

[DKhanh]

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.

Đọ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)
}

[tsandtm]

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.

[daigiakotien]

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

[DKhanh]

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:

#include "stdafx.h" #define N 3 void main(){    int a[N+1] = {0};    int n_subset = 0;     for (;;)    {        // ------ đổi các bit 1 đầu tiên thành 0 ------         int i = 0;        while (a[i])        {            a[i++] = 0;        }         if (i == N) break;         // ----- và đổi bit 0 đầu tiên bên trái thành 1 -----        a[i] = 1;         // ------- in tập con ra màn hình -----        for (i = 0; i < N; ++i)        {            if (a[i])            {                cout << i + 1 << "  ";            }        }         cout << endl;        ++n_subset;    }    cout << "Number of subset: " << n_subset << endl;    getch();}