giup toi giai thuat sinh hoan vi voi!

[real_time]

Toi hoc pascal tu kha lau lau rui nhung ma hoc mai ma chua biet duco giai thuat sinh hoan vi nhu the nao! chang hieu sao no lai roi ram den nhu the! Lieu ai co the viet giup minh giai t thuat sinh hoan vi giup voi nhi?? xin cam on rat nhieu........:
rolleyes: lol lol

[baoquan]

tui có 1 giải thuật chạy cũng rất tốt.Giai thuẩt cua tui sẽ sinh hoán vị theo thứ tự từ điển:


program HV;
const N=20;
var A:array[1..n] of byte;
B:array[1..n] of 0..1;
i,dem:integer;
procedure Print;
var i:integer;
begin
dem:=dem+1;
write('hoan vi thu', dem,':');
for i:=1 to n do
write(a[i]);
writeln;
end;


procedure hoanvi(i:integer);
var j:integer;
a,b:m1c;
begin
if i> n then print
else
begin
for j:=1 to n do
if (b[j]=1) then
begin
a[i]:=j;
b[j]:=0;
find(i+1);
b[j]:=1;
end;
end;
end;

begin
dem:=0;
for i:=1 to n do b[i]:=1;
find(1);
end.

[Mic]

Trùi, đây là đệ qui quay lui, thuật toán sinh khác nữa

[real_time]

xin loi moi nguoi vi chang wa la toi cung kha ban nen ko the xem het duoc moi nguoi thong cam di!!!!

[magirl]

bác đợi tí để em post lên, nhung thuật này là do đọc sách chứ không phải em nghĩ ra đâu....

[Junior IT]

Nếu bài này được mở rộng ra là "Nhập một số k<=10000 , và n<=20000 hãy in ra hoán vị thứ k của n số đầu tiên
Vd: n=3; k=2
=> 132

[khôngtên]

Bài trên có hai cách giải:
Một là như bao quang là đơn giản nhất hay các bác có thể làm như sau: khởi tạo một hoán vị 1 2 3 .. n rồi tìm cách timg số lớn hơn hoán vị đó mà bé nhất rồi tìm tiếp tục số kế với số vừa tìm được ... cho đến khi được hoán vị lớn nhất là n n-1 n-2 ... 1. Như thế là OK còn cách cài các bác có thể tự làm !

[viet_hung81]

Vậy bạn nào giải được bài này nhé: cho k bit 0 và n bit 1 phát sinh các cấu hình sao cho ko có hai bit 0 kề nhau.

[khôngtên]

Thuật toán cũng có thể giải bằng đệ quy quay lui như sau:
Tại mỗi bước duyệt ta sẽ điền 0 hoặc một 1 tuỳ thuộc vào số đã điền vào liền trước đó. Nhưng để ý rằng tại mỗi bước duyệt tiếp phải so sánh số lượng số 0 và 1 còn lại để điền tiếp nếu số lượng số 0 > số lượng số 1 thì không thể thực hiện được nữa ! Cứ thế cho đến khi nào điền hết số lượng 0 và 1 thì OK bạn đã có 1 cấu hình và tất nhiên bài toán có nhiều kết quả

[viet_hung81]

Tôi chưa hiểu ý bạn lắm, bạn có thể nói rõ hơn ko, hoăc bạn viết đoạn chương trình phát sinh tổ hợp.

[btkiet]

Sau đây là thủ tục sinh hoán vị liền sau theo thứ tự tự điển không đệ quy, mảng a phải được khởi tạo giá trị 1,2,3,...,n và thủ tục này sẽ kết thúc khi mảng a mang giá trị n,n-1,...2,1.
procedure hoanvi(var a:mang);
var j,k,r,s:byte;
begin
j:=n-1;
while (a[j]>a[j+1])and(j>=1) do j:=j-1;
if j>=1 then
begin
k:=n;
while a[j]>a[k] do k:=k-1;
doicho(a[j],a[k]);
r:=n;s:=j+1;
while r>s do
begin
doicho(a[r],a[s]);
s:=s+1;r:=r-1;
end;
end
else stop:=true;
end;

Còn đây là thủ tục sinh tổ hợp k chập n liền sau theo thứ tự tự điển không đệ quy, mảng a phải được khởi tạo giá trị 1,2,3,...,k và thủ tục này sẽ kết thúc khi mảng a mang giá trị n-k,n-k+1m,...n-1, n.
procedure tohop(var a:mang);
var i,j:byte;
begin
i:=r;
while (a[i]=n-r+i)and(i>=1) do i:=i-1;
if i>=1 then
begin
a[i]:=a[i]+1;
for j:=i+1 to r do a[j]:=a[i]+j-i;
end
else stop:=true;
end;

[tuyenbinh]

ban nao giai dum minh giai thuat print nhe

[ConanKudo]

Nếu bài này được mở rộng ra là "Nhập một số k<=10000 , và n<=20000 hãy in ra hoán vị thứ k của n số đầu tiên
Vd: n=3; k=2
=> 132

Sao k chỉ có 10000 thôi à, sao không chơi hẳn 10 tỷ ý.=))
QHĐ O(N)

[hung06061995]

Cho em hỏi đây là thuật toán gì vậy và có ý nghĩa gì

[tiensusu]

ban nao giai dum minh giai thuat print nhe

Mình chưa bao giờ nghe thấy giải thuật print cả, mà chỉ thấy giải thuật Prim thôi, đây là giải thuật cây khung nhỏ nhất

[llaamm44]

co pac nao co code ve giai thuat Prim tìm cây có trọng lượng nhỏ nhất ko vậy ??