View Full Version : Hoán vị...
minhlazy
14-02-2004, 16:21
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
14-02-2004, 16:52
Thì cứ làm bình thường, thêm 1 biến đếm nữa là xong !
minhlazy
15-02-2004, 14:33
Tui xin nói thêm là n<100 nếu làm như unfriendlyboy thì chắc là ko được rùi
minhlazy
19-02-2004, 14:14
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....
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
19-02-2004, 17:53
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???
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 ...
Xài đệ quy quay lui được mà .( có giới hạn k)
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
21-02-2004, 09:25
thankyou bác msn nha, pots lên luôn cho em coi đi
happydragon
08-03-2004, 23:11
"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.
------------
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.