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;
}
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.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.