Khóa vòng

Một ổ khóa gồm M vòng chữ và N vòng số. Mỗi vòng chữ hoặc số chứa các giá trị biến thiên từ giới hạn  nhỏ nhất a đến giới hạn lớn nhất b. Hãy liệt kê tăng dần theo trật tự từ điển các giá trị có thể có của khóa.

KHOA.INP	KHOA.OUT
1 2 B C 2 3 0 2	12 B20 B21 B22 B30 B31 B32 C20 C21 C22 C30 C31 C32

Dữ liệu vào: tệp văn bản KHOA.INP

Dòng đầu tiên: hai số tự nhiên M và N, 1 £ M, N £ 5.

Dòng thứ i trong số M+N dòng tiếp theo: giới hạn a_i và  b_i cho các vòng khóa.

Dữ liệu ra: tệp văn bản KHOA.OUT

Dòng đầu tiên: Tổng số khả năng.

Từ dòng thứ hai trở đi: mỗi dòng một giá trị khóa liệt kê tăng dần theo trật tự từ điển. Các kí tự chữ và số trong mỗi khóa được viết liền nhau, không có dấu cách ở giữa. Các giá trị chữ được lấy từ bảng chữ HOA tiếng Anh.

Thuật toán

Phương pháp: duyệt toàn bộ các tổ hợp.

Nếu toàn bộ N vòng khóa đều chỉ chứa các chữ số với giới hạn biết trước từ cận dưới a[i] đến cận trên b[i] , i = 1..N thì ta dùng hàm Next sinh ra lần lượt các tổ hợp N phần tử  c[1..N] như  sau.

Khởi trị: c[1..N] là tổ hợp nhỏ nhất chứa toàn cận dưới:

    c[i] := a[i], i = 1..N.

Xử lí:

repeat

    Ghi tổ hợp c[1..N];

until not Next;

Mỗi lần gọi hàm Next ta thực hiện giống như phép đếm: Duyệt ngược c[1..N] với mỗi c[i] = b[i] ta đặt lại c[i] := a[i]. Gặp c[i] đầu tiên thỏa điều kiện c[i] < b[i] thì tăng vòng khóa i thêm 1 nấc. Nếu không gặp phần tử i như vậy thì chứng tỏ đã xử lí xong tổ hợp cao nhất.

Việc còn lại là chuyển các vòng chữ sang vòng số tương ứng. 

Độ phức tạp: (b₁-a₁+1)(b₂-a₂+1)...(b_v-a_v+1), v = M+N.

(*  Pascal  *)

(****************************************

                Khoa Vong

*****************************************)

program KhoaVong;

uses crt;

const mn = 20;

bl = #32; nl = #13#10; fn = 'KHOA.INP'; gn = 'KHOA.OUT';

ChuCai = ['A'..'Z'];

type mi1 = array[0..mn] of integer;

var m,n: integer;

   a,b,c: mi1;

   f,g: text;

   m: longint;

procedure Doc;

  var i: integer;

  c: char;

begin

  assign(f,fn); reset(f); readln(f,m,n);

  n := m + n;

  for i := 1 to m do

    begin

      repeat

        read(f,c);

      until c in ChuCai;

      a[i] := ord(c) - ord('A');

      repeat

        read(f,c);

      until c in ChuCai;

      b[i] := ord(c) - ord('A');

    end;

  for i := m + 1 to n do read(f,a[i],b[i]);

  close(f);

  m := 1;

  for i := 1 to n do m := m * (b[i] - a[i] + 1);

end;

function Min(a,b: integer): integer;

begin

  if (a < b) then Min := a else Min := b;

end;

function Next: Boolean;

  var i: integer;

begin

  Next := false;

  i := n;

  while (c[i] = b[i]) do

    begin

      c[i] := a[i];

      i := i - 1;

    end;

  if (i = 0)  then exit;

  c[i] := c[i] + 1;

  Next := true;

end;

procedure Duyet;

  var i: integer;

begin

  for i := 1 to n do c[i] := a[i];

  c[0] := -1;

  assign(g,gn); rewrite(g); writeln(g,m);

  repeat

    for i := 1 to m do write(g,chr(ord('A')+c[i]));

    for i := m + 1 to n do write(g,c[i]);

    writeln(g);

  until not Next;

  close(g);

end;

BEGIN

  Doc; Duyet;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH