PDA

View Full Version : Giúp tìm giải thuật!



saleoteo
24-08-2010, 15:52
Chào các bạn, mình có một vấn đề này mong các bạn giúp đỡ
Mình nghĩ mãi mà không ra giải thuật tạo n^2 tập hợp từ n phần tử
Ví dụ cụ thể:
nếu có 2 phần tử a,b cần giải thuật tìm ra được tập hợp có 2^2 = 4 phần tử là {rỗng,a,b,ab}
Tương tự nếu có 3 phần tử a,b,c cần giải thuật tìm ra được tập hợp có 2^3 = 8 phần tử là {rỗng,a,b,c,ab,ac,bc,abc}

phần tử rỗng trường hợp nào cũng có
Và số lượng phần tử là không biết trước (n tùy ý)
Mong các bạn giúp đỡ.
Thanks alot!

saleoteo
08-09-2010, 16:53
Sao không có ai giúp mình vậy ?
Chờ dài cổ!

nguyenducthinhdl
08-09-2010, 17:48
Thuật toán đơn giản nhất nhé.

Input: S = {S1, S2, S3, ...., Sn} : Tập hợp cần hoán vị.
n = #S: Số phần tử của tập S.
Output: T = {T_0, T_1, T_2 ... T_{2^N - 1}}: Là tập hợp các hoán vị của S.

Ta dùng một mảng phụ M cỡ n. M[i] = true nếu Si xuất hiện trong hoán vị hoặc là false nếu ngược lại.

Ban đầu M[i] = false với mọi i.

Tập M là tập hoán vị hiện thời. M = {S_i .....} với M[i] = true.

Thuật toán chính:

SinhHoanVi(S, M, k, ref T){
if (k == n + 1){
T = T U M;
return ;
}

SinhHoanVi(S, M, k + 1);
M[k] = true;
SinhHoanVi(S, M, k + 1);
}

Thuật toán gọi SinhHoanVi ra kết quả

Tậphợp goiHoanVi(S){
Tậphợp T = {rỗng};

Mảng M;

for(i=1 --> n) M[i] = false;

SinhHoanVi(S, M, 1, T); //T là biến tham chiếu.

return T;
}

jdkhang
08-09-2010, 19:27
Giải thuật tạo n^2 tập hợp từ n phần tử
Để đơn giản, đặt lại bài toán: n phần tử này là các con số từ 1, 2, ..., n
_Ta tạo 1 mảng a gồm n phần tử, với ý nghĩa:
a[i] = 0 tức không tồn tại phần tử i trong tập hợp, hoặc a[i] = 1 tức phần tử i có trong tập hợp.

Với n phần tử 1, 2, 3, .., n ta có 2^n tập hợp tạo từ các phần tử này:

Ta biết: Có 1 Tập rỗng là tập không có phần tử
Tương ứng với biến mảng: a[0, 0, 0, ..., 0]; n phần tử a[i] = 0 (1<=i<=n)

Ta biết, Có n tập hợp có 1 phần tử
Tập 1: có 1 phần tử là số 1, tương ứng với mảng a[1, 0, 0, .., 0]; a[1] = 1; a[i]=0 (2<=i<=n)
Tập 2: có 1 phần tử là số 2, tương ứng với mảng a[0, 1, 0, .., 0]; a[1] = 0; a[2]=1; a[i]=0 (3<=i<=n)
Tập 3: có 1 phần tử là số 3, tương ứng với mảng a[0, 0, 1, .., 0]; a[1] = 0; a[2]=0; a[3]=1; a[i]=0 (4<=i<=n)
...
Tập n: có 1 phần tử là số n, tương ứng với mảng a[0, 0, 0, .., 1]; a[i]=0 (1<=i<=n-1), a[n]=1

Tương tự như vậy cho tập có 2 phần tử, tập có 3 phần tử, ...

Tập có n phần tử gồm 1 tập, tương ứng với mảng a[1, 1, 1, ..., 1]; a[i]=1 (1<=i<=n)


Chương trình minh họa


Program TheSet;
Const Max = 255;
Var a : Array[1..Max] of Byte;
n : Byte;


Procedure Init;
Var i : Byte;
Begin
Write('Nhap N = '); readln(n);
End;

Procedure showResult;
Var i: Byte;
Begin
For i := 1 to n do
Begin
If a[i] = 1 then write(i);
End;
Writeln;

End;

Procedure Try(i : Byte);
Var bit: byte;
Begin
For bit := 0 to 1 do
Begin
a[i] := bit;
if i = n then showResult
else Try(i+1);
End;
End;

BEGIN
Init;
Try(1);
Readln;
END.


Chương trình này chưa đưa ra tập rỗng, vì chẳng có gì để đưa ra cả :D

saleoteo
13-09-2010, 07:05
thật sự rất cảm ơn hai bạn, để mình thử lại xem có đúng với yêu cầu của mình không.
Một lần nữa xin cảm ơn hai bạn.