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



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 ai  bi 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: (b1-a1+1)(b2-a2+1)...(bv-av+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
LẬP TRÌNH


0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts