Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Dãy các hoán vị của N chữ cái HOA đầu tiên trong bảng chữ tiếng Anh được sắp theo trật tự từ điển tăng dần và viết liền nhau thành một dãy kí tự duy nhất. Hãy cho biết kí tự thứ M trong dãy tính từ 1 trở đi, 2 £ N £ 10, 1 £ M £ N.N!. Thí dụ, với N=3, ta có dãy 6 hoán vị xếp theo trật tự từ điển là ABC, ACB, BAC, BCA, CAB, CBA. Sau khi ghép chúng ta thu được dãy duy nhất gồm 18 kí tự ABCACBBACBCACABCBA.Kí tự thứ M = 15 trong dãy là: B.

 Thuật toán

Nếu ta viết mỗi hoán vị trên 1 dòng thì kí tự thứ M sẽ nằm trên dòng d = (M-1) div N (tính từ dòng 0) và sẽ chiếm vị trí v = ((M-1) mod N)+1 (tính từ 1) trên dòng d đó. Như vậy ta cần  xác định hoán vị trên dòng d rồi lấy kí tự nằm ở vị trí v làm kết quả.
Để xác định hoán vị (c1,c2,...,cN) tại dòng d ta lần lượt tính các kí tự ci, i = 1..N. Ta phân hoạch các hoán vị theo nhóm. Nếu bỏ kí tự đầu tiên thì ta còn lại (N-1)! hoán vị, khi đó hoán vị tại dòng d sẽ rơi vào nhóm d div (N-1)! và sẽ chiếm dòng d mod (N-1)! trong nhóm đó. Tương tự, ta tính cho các kí tự thứ 2, 3, ..., N-1. Kí tự còn lại sẽ chiếm vị trí thứ N. Nếu biết nhóm d của kí tự thứ i trong hoán vị thì ta tính được chính kí tự đó như sau.
   d = 1 ứng với kí tự thứ nhất trong số các kí tự chưa dùng,
   d = 2 ứng với kí tự thứ hai trong số các kí tự chưa dùng,
   ...
Tổng quát, d ứng với kí tự thứ d trong số các kí tự chưa dùng.
Mỗi lần xác định được kí tự nào thì ta đánh dấu kí tự đó bằng thủ tục Mark.
Để tránh việc tính n! ta viết thủ tục ThuongDu(z, n, q, r) cho ra thương q và dư r của phép chia số tự nhiên z cho n!, cụ thể là q = z div n! và r = z mod n!.  Thủ tục này khá đơn giản. Ta có
q1 = z div n; r1 = z mod n Þ z = q1.n + r1;
q2 = q1div (n-1); r2 = q1 mod (n-1) Þ q1 = q2.(n-1) + r2;
qn-1 = qn-2 div 2; rn-1 = qn-2 mod 2 Þ qn-2 = qn-1.2 + rn-1.
qn = qn-1div 1 = qn-1; rn = qn-1 mod 1 = 0.
Thay lần lượt các đại lượng của dòng dưới vào dòng trên ta thu được q = qn-1 và r = r1+ n.r2 + (n-1).r3 +…+ 3.rn-1 + 2.rn. Nhận xét này cho phép ta xây dựng thủ tục theo kỹ thuật chia liên tiếp như sau.
 procedure ThuongDu(z,n: longint;var q,r: longint);
    var c: longint;
   begin
     r := 0; q := z; c := 1;
     while n > 1 do
       begin
         r := r + (q mod n)*c;
         q := q div n;
         c := n; n := n - 1;
       end;
   end;
Thủ tục Test trong chương trình dưới đây tính mọi xuất hiện của các kí tự (M = 1..24*4) trong  dãy các hoán vị với N = 4.

Chương trình Pascal

(* Pascal *)
   uses crt;
   const MN = 20; bl = #32;
   var   b: array[0..MN] of byte;
   { d = z div n! r = z mod n! }
   procedure ThuongDu(z,n: longint;var q,r: longint);
    Tự viết
   { Danh dau ki tu v thu k
      trong so cac ki tu chua dung }
   procedure Mark(N,k,v: integer);
    var i,d: integer;
    begin
      d := 0;
      for i := 1 to N do
        if b[i] = 0 then
         begin
           d := d+1;
           if d = k then
            begin
              b[i] := v;
              exit;
            end;
         end;
    end;
   { Xac dinh ki tu thu M trong day cac hoan vi }
   function Value(N: integer;M: longint): char;
    var i,j,v: integer;
        th,du,d: longint;
   begin
      fillchar(b,sizeof(b),0);
      d := (M-1) div N; { Dong chua ki tu M }
      v := (M-1) mod N + 1; { vi tri cua M tren dong d }
      { xac dinh hoan vi tai dong d }
      j := N-1;
      for i := 1 to N-1 do
       begin
         ThuongDu(d,j,th,du);
         Mark(N, th+1,i);
         j := j-1;
         d := du;
       end;
      Mark(N,1,N);
      for i:=1 to N do
        if b[i] = v then
        begin
          Value := chr(ord('A') + i-1);
          exit;
        end;
   end;
   procedure Test;
     var N: integer;
         M: longint;
   begin
     N := 4; writeln;
     for M := 1 to 24*N do
       begin
        write(Value(N,M));
        if M mod N = 0 then
         begin
           if readkey = #27 then halt else writeln;
         end;
       end;
   end;

   BEGIN
     Test;
   END.




N
N!
N
N!
1
2
3
4
5
6
7
8
9
10

1
2
6
24
120
720
5040
40320
362880
3628800
11
12
13
14
15
16
17
18
19
20
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000

Giai thừa của 20 số nguyên dương đầu tiên


Với C# bạn có thể dùng kiểu int64 hoặc long với 64 bit (8 byte) biểu diễn số nguyên trong khoảng
[-9.223.372.036.854.775.808, 9.223.372.036.854.775.807].

Độ phức tạp

Thuật toán chỉ đòi hỏi N = 20 phép chia các số nguyên có tối đa 20 chữ số và gọi thủ tục Mark N lần, mỗi lần gọi phải thực hiện phép duyệt trên dãy N phần tử. Tổng cộng là N2 phép toán, tức là cỡ 400 phép toán thay vì 2432902008176640000 phép toán nếu ta sinh lần lượt N! hoán vị bằng phương pháp vét cạn với N = 20.

Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH
 
tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts