Liệt Kê Các Hoán Vị Từ 1 đến N

Trang chủ » Thuật Toán Liệt Kê Hoán Vị Trong Pascal » Liệt Kê Các Hoán Vị Từ 1 đến N

Có thể bạn quan tâm

Đề bài: Hãy liệt kê các hoán vị từ 1 đến N theo thứ tự từ điển

Ví dụ: Nhập N=3 thì các hoán vị: 123  132  231  213 312 321

Ý tưởng:

Bước 1: Ta khởi tạo cấu hình ban đầu 123. in cầu hình ra.

Bước 2: Ta tìm dãy con giảm dần bằng cách duyệt từ cuối dãy lên và gặp A[i] nào thỏa A[i] > A[i-1] thì ngừng bước 2.

Bước 3: Ta đổi giá trị phần từ nhỏ nhất trong dãy con giảm dần và phần tử sát cuối với dãy con. Bằng cách ta duyệt từ cuối dãy gặp A[k] nào nhỏ hơn A[i-1] thì ta hoán đổi.

Bước 4: Ta sắp xếp dãy con vừa hoán đổi thành tăng dần. In cấu hình hiện tại ra.

Bước 5: Lặp lại các bước 2,3,4  trên cho đến khi i=1 thì dừng lại.

Chương trình:

program lietkehoanvi; type mang=Array[1..100] of integer; label L1; var A,B:mang; sptA,sptB:integer; i,j,n:integer; co:boolean; Procedure hoanvi(var a,b:integer); Var tam:integer; Begin tam:=a; a:=b; b:=tam; End; Procedure sapxeptd(var A:mang; spt:integer; vt:integer); var i,j:integer; Begin for i:=vt to n-1 do for j:=i+1 to n do if A[i] > A[j] then Begin hoanvi(A[i],A[j]); End; End; Procedure khoitao(var A:mang; spt:integer); var i:integer; Begin for i:=1 to spt do A[i]:=i; End; Procedure inCauhinh(A:mang; spt:integer); Begin for i:=1 to spt do write(A[i],' '); writeln; End; Begin write('Nhap so : '); Readln(n); khoitao(A,n); inCauhinh(A,n); while true do Begin for i:=n downto 1 do Begin if i=1 then goto L1; if A[i]>A[i-1] then break; End; for j:=n downto i do if A[j]>A[i-1] then Begin hoanvi(A[j],A[i-1]); sapxeptd(A,n,i); incauhinh(A,n); break; End; End; L1: Write('Ket thuc '); Readln; End.

Tải code tại đây: Click here

Chia sẻ:

  • Twitter
  • Facebook
Thích Đang tải…

Từ khóa » Thuật Toán Liệt Kê Hoán Vị Trong Pascal