Hoán vị...

[minhlazy]

Ai giúp tôi với:
Cho số n và số k là thứ tự từ điển của 1 hoán vị.Yêu cầu xây dựng hoán vị của n số đó.
Ví dụ:n=3,k=2
Dãy tìm được: 1 3 2

[unfriendlyboy]

Thì cứ làm bình thường, thêm 1 biến đếm nữa là xong !

[minhlazy]

Tui xin nói thêm là n<100 nếu làm như unfriendlyboy thì chắc là ko được rùi

[minhlazy]

Tại sao chẳng có ai chịu giúp tôi vậy.Làm ơn đi mà các bác ơi....

[novavn]

Có ai biết thuật toán "Sinh" không? TÌm đọc trong cuốn Cẩm nang thuật toán tập 2 đó!

[hiepsi4rum]

Bạn có thể nói rõ hơn được không??
Mình chưa hiểu hoán vị của n số đó nghĩ là sao???

[hechay]

cái này thuộc phần " thứ tự từ điển " , học lâu wé rồi , hồi năm lớp 10 cơ , để về kiếm sách xem lại rồi trả lời cho .... bạn đã từng làm tổ hợp , chỉnh hợp chưa vậy ? có thể áp dụng đệ quy để kill một số test nhỏ áh ...

[Global]

Xài đệ quy quay lui được mà .( có giới hạn k)

[msn]

Trời đất bài này mà sao ai cũng bảo là dùng đệ quy vậy. Với n=100 thì chắc chạy đến sang năm luôn.Bài này là bài toán cơ bản của QHĐ từ điển,lần sau tôi sẽ post code lên cho.

[minhlazy]

thankyou bác msn nha, pots lên luôn cho em coi đi

[happydragon]

"phê phán" bác msn vì kô chịu post lời giải lên
thử dùng thuật toán này xem, qhd thì mình kô biết, khi n lớn thì dùng xử lý xâu với các phép toán chia và nhân (chưa thử).
------------------
ses crt;
const
gt:array[1..10] of longint=(1,2,6,24,120,720,5040,40320,362800,362880 0);
var dd:array[1..10] of boolean;
i,dem1,tt,nn,n,dem:byte;
k:longint;
chuso:array[1..10] of byte;
begin
clrscr;
n:=4;k:=10;dem:=1;nn:=n;
fillchar(dd,sizeof(dd),false);
repeat
tt:=(k-1) div gt[n-1]+1;
k:=(k-1) mod gt[n-1]+1;
dem1:=0;
for i:=1 to nn do
begin
if dd[i]=false then inc(dem1);
if dem1=tt then break;
end;
chuso[dem]:=i;{chu so thu dem cua hoan vi thu k}
dd[i]:=true; {danh dau chu so nay da dung roi}
dec(n);inc(dem);
until n=1;
for i:=1 to nn do if dd[i]=false then chuso[nn]:=i;
{in kết quả}
for i:=1 to nn do write(chuso[i],' ');
end.
------------