Thuật toán sinh hoán vị trong Pascal

Để sinh số tự nhiên theo thứ tự từ điển trong Pascal, chúng ta có thể sử dụng thuật toán sau:

Khởi tạo mảng A[1..n] với A[i] = i với mọi i từ 1 đến n.
Lặp lại cho đến khi không còn số nào có thể thay đổi vị trí: a. Xuất dãy số hiện tại. b. Tìm phần tử cuối cùng của dãy A[i] sao cho A[i] < A[i+1].
- Nếu không tồn tại phần tử như vậy, kết thúc thuật toán. c. Tìm phần tử cuối cùng của dãy A[j] lớn hơn A[i]. d. Hoán đổi A[i] và A[j]. e. Đảo ngược các phần tử trong đoạn từ A[i+1] đến A[n].

Ví dụ:

Để sinh các số tự nhiên có 3 chữ số theo thứ tự từ điển, ta có thể sử dụng thuật toán sau:

Khởi tạo mảng A[1..3] với A[i] = i với mọi i từ 1 đến 3: A = [1, 2, 3].
Xuất dãy số hiện tại: 123.
Tìm phần tử cuối cùng của dãy A[i] sao cho A[i] < A[i+1]: i = 2.
Tìm phần tử cuối cùng của dãy A[j] lớn hơn A[i]: j = 3.
Hoán đổi A[i] và A[j]: A = [1, 3, 2].
Đảo ngược các phần tử trong đoạn từ A[i+1] đến A[n]: A = [1, 3, 2].
Xuất dãy số hiện tại: 132.
Tìm phần tử cuối cùng của dãy A[i] sao cho A[i] < A[i+1]: i = 1.
Tìm phần tử cuối cùng của dãy A[j] lớn hơn A[i]: j = 3.
Hoán đổi A[i] và A[j]: A = [3, 1, 2].
Đảo ngược các phần tử trong đoạn từ A[i+1] đến A[n]: A = [3, 2, 1].
Xuất dãy số hiện tại: 321.
Không tồn tại phần tử nào để thay đổi vị trí, kết thúc thuật toán.

Cài đặt thuật toán sinh hoán vị với Pascal:

program permutation;

const
  n = 3;

var
  a: array[1..n] of integer;
  i, j, k: integer;
  finished: boolean;

procedure output;
var
  i: integer;
begin
  for i := 1 to n do
    write(a[i]);
  writeln;
end;

begin
  // Khởi tạo hoán vị đầu tiên
  for i := 1 to n do
    a[i] := i;
  output;
  
  // Sinh các hoán vị tiếp theo
  repeat
    // Tìm vị trí i sao cho a[i] < a[i+1]
    i := n - 1;
    while (i > 0) and (a[i] >= a[i+1]) do
      dec(i);
    if i = 0 then
      finished := true
    else
    begin
      // Tìm vị trí j sao cho a[j] > a[i]
      j := n;
      while a[j] <= a[i] do
        dec(j);
      // Đổi chỗ a[i] và a[j]
      k := a[i];
      a[i] := a[j];
      a[j] := k;
      // Đảo ngược đoạn a[i+1]..a[n]
      j := i + 1;
      k := n;
      while j < k do
      begin
        swap(a[j], a[k]);
        inc(j);
        dec(k);
      end;
      output;
    end;
  until finished;
end.

Trong chương trình trên, chúng ta khởi tạo hoán vị đầu tiên bằng cách sắp xếp các phần tử từ 1 đến n. Sau đó, chúng ta lặp lại cho đến khi không còn hoán vị nào có thể sinh ra được nữa.

Trong mỗi lần lặp, chúng ta tìm vị trí i sao cho a[i] < a[i+1], nếu không tìm được thì kết thúc thuật toán. Sau đó, chúng ta tìm vị trí j sao cho a[j] > a[i], hoán đổi a[i] và a[j], và đảo ngược đoạn a[i+1]..a[n]. Cuối cùng, chúng ta xuất ra hoán vị mới sinh ra.

Lập trình Pascal

Thuật toán sinh hoán vị trong Pascal

Trả lời Hủy