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



Liệt kê tăng dần theo thứ tự từ điển các hoán vị của các số 1..N.
Dữ liệu vào: tệp văn bản HV.INP chứa duy nhất  số  N, 1 £ N £ 9.
Dữ liệu ra: tệp văn bản HV.OUT
Mỗi dòng một hoán vị.

HV.INP
HV.OUT

 3


 1 2 3
 1 3 2
 2 1 3
 2 3 1
 3 1 2
 3 2 1

Thuật toán

Sử dụng hàm Next trong bài trước. Khởi trị cho x là hoán vị đơn vị x = (1,2,…,N).
Độ phức tạp cho hàm Next: 2N, cho cả bài: 2N(N!).
Trong các chương trình dưới đây ta xây dựng các hàm Next không có tham biến nhằm mục đích đẩy nhanh quá trình tính toán. Như vậy, dữ liệu được cho dưới dạng các biến tổng thể, bao gồm n  -  chiều dài của các hoán vị, x[0..n-1] - mảng chứa hoán vị.
(*  Pascal  *)
(***************************************
    Liet ke cac hoan vi cua 1..N
    theo thu tu tang dan
***************************************)
program CacHoanVi;
uses crt;
const
  bl = #32;  mn  = 10;  fn = 'HV.INP';  gn = 'HV.OUT';
type
  mb1 = array[0..mn] of byte;
var
 x: mb1; { chua hoan vi }
 n: byte; { Len(x) }
 f,g: text; { input, output files }
 procedure Doc;
 begin
   assign(f,fn); reset(f);readln(f,n); close(f);
 end;
 function Next: Boolean;
   var i,j,t : byte;
 begin
   Next := false;
   { Tim diem gay }
   i := n - 1;
   while (x[i] >= x[i + 1]) do i := i - 1;
   { x[i] < x[i+1] }
   if (i = 0) then exit;
   j := n;
   while (x[j] <= x[i]) do j := j - 1;
   t := x[i]; x[i] := x[j]; x[j] := t;
   i := i + 1; j := n;
   while (i < j) do
     begin
       t := x[i]; x[i] := x[j]; x[j] := t;
       i := i + 1; j := j - 1;
     end;
   Next := true;
 end;
 procedure Run;
   var i: byte;
 begin
   Doc; x[0] := 0; // Dat linh canh
   assign(g,gn); rewrite(g);  
   for i := 1 to n do x[i] := i;// Hoan vi don vi
   repeat
     for i := 1 to n do write(g,x[i],bl);
     writeln(g);
   until not Next;
   close(g);
 end;
 BEGIN
  Run;
 END.

Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts