Home Home » Pascal nâng cao » THUẬT TOÁN QUAY LUI

THUẬT TOÁN QUAY LUI

Chủ Nhật, 19 tháng 2, 2017
THUẬT TOÁN QUAY LUI

Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng. 
            Giả sử cấu hình liệt kê có dạng a[1..n], khi đó thuật toán quay lui thực hiện qua các bước
1)     Xét tất cả các giá trị a[1] có thể nhận, thử a[1] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho a[1] ta sẽ:
2)     Xét tất cả các giá trị a[2] có thể nhận, thử cho a[2] nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán cho a[2] lại xét tiếp các khả năng chọn a[3]... cứ tiếp tục như vậy cho đến bước:
.....
n) xét tất cả các giá trị a[n] có thể nhận, thử cho a[n] nhận lần lượt các giá trị đó, thông báo cấu hình tìm được (a[1], a[2], ..., a[n])
Mô hình của thuật toán quay lui được mô tả như sau
{thủ tục thử a[i] nhận lần lượt các giá trị mà nó có thể nhận}

Procedure TRY(i: integer);
Var j: integer;
Begin
   For (mọi giá trị của j có thể gán cho a[i]) do
    Begin
       (Thử cho a[i]=j);
        If (a[i] là phần tử cuối cùng trong cấu hình) THEN
            (thông báo cấu hình tìm được)
            else
             Begin
                        (Ghi nhận việc cho a[i] nhận giá trị j nếu cần))
                        Try(i+1); {gọi đệ quy để chọn tiếp a[i+1]}
                        (nếu cần, bỏ ghi nhận việc thử a[i]:= j để thử giá trị khác);
              End;
     End;
 End;

Thuật toán quay lui được bắt đầu bằng lời gọi try(1)
Ví dụ1: liệt kê dãy nhị phân có độ dài n
Biểu diễn dãy nhị phân có độ dài n dưới dạng a[1..n]. ta sẽ liệt kê các dãy nhị phân bằng cách thử dùng các giá trị {0,1} gán cho a[i]. Với mỗi giá trị thử gán cho a[i] lại thử các giá trị có thể gán cho a[i+1]. Chương trình liệt kê bằng thuật toán quay lui có thể viết như sau:
Var a:array[1..100] of integer;
n:integer; f:text;
procedure xuat;
var i:integer;
begin
  for i := 1 to n do write(f,a[i]);
writeln(f);
end;
procedure try(i:integer);
var j: integer;
Begin
 for j := 0 to 1 do       {xét các giá trị có thể gán cho a[i]}
  begin
     a[i] := j;     {thử a[i]}
     if i=n then xuat {nếu thử đến cấu hình cuối thì in kết quả}
else
 try(i+1); {nếu chưa phải cấu hình cuối thì gọi đệ quy chọn tiếp a[i+1]}
end;
end;
BEGIN
Assign(f,’nhiphan.inp’); reset(f);
Read(f,n); close(f);
Assign(f,’nhiphan.out’); rewrite(f);
Try(1); {Thử các cách chọn giá trị a[1]}
Close(f);
End.
          Ví dụ với n=3,  cây tìm kiếm quay lui như sau


Ví dụ 2: liệt kê các chỉnh hợp không lặp chập k của n phần tử
Var a:array[1..100] of integer;
B:array[1..100] of 0..1;
k,n:integer; f:text;
procedure xuat;
var i:integer;
begin
  for i := 1 to k do write(f,a[i]);
writeln(f);
end;
procedure try(i:integer);
var j: integer;
Begin
 for j := 1 to n do       {xét các giá trị có thể gán cho a[i]}
if b[j]=0 then 
begin
     a[i] := j;     {thử a[i]}
     if i=k then xuat {nếu thử đến cấu hình cuối thì in kết quả}
else
        begin
  b[j]:=1;
  try(i+1); {nếu chưa phải cấu hình cuối thì gọi đệ quy chọn tiếp a[i+1]}
  b[j]:=0;
   end;
end;
end;
BEGIN
Assign(f,’chinhhop.inp’); reset(f);
Read(f,k,n); close(f);
Assign(f,’chinhhop.out’); rewrite(fo);
Try(1); {Thử các cách chọn giá trị a[1]}
Close(f);


MỘT SỐ BÀI TẬP CÙNG DẠNG
Bài 1: Liệt kê các chỉnh hợp lặp chập k của n phần tử
Bài 2: Liệt kê các tập con k phần tử của n số nguyên đầu tiên.(các phần tử khác nhau)
Bài 3: Từ ví dụ 1 ở trên hãy chỉnh sửa để được dãy nhị phân có độ dài n nhưng không có 2 số 0 kề nhau.
Bài 4: Cho xâu s chỉ gồm các kí tí tự 'A' đến 'Z' (các kí tự đôi một khác nhau). Hãy liệt kê tất cả các hoán vị khác nhau của xâu s.
Bài 5:  Cho số nguyên dương n (n<=20). Hãy liệt kê tất cả các xâu độ dài n chỉ gồm 2 kí tự ‘A’ hoặc ‘B’ mà không có kí tự ‘B’ nào đứng cạnh nhau.
Bài 6: Bài toán rút tiền tự động ATM
Một máy rút tiền tự động ATM có n (n<=20) tờ tiền có giá trị t1,t2,…,tn. Hãy đưa ra một cách trả với số tiền đúng bằng S.
          Dữ liệu vào từ file “ATM.INP” có dạng:
-        dòng đầu là 2 số n và s
-        dòng 2 gồm n số t1,t2,…,tn
Kết quả ra file “ATM.OUT” có dạng: Nếu có thể trả đúng S thì đưa ra cách trả, nếu không thì ghi -1
ATM.INP
ATM.OUT
10 390
200 10 20 20 50 50 50 50 100 100
20 20 50 50 50 100 100
Bài 7: Cho một xâu S (Chỉ gồm các kí tự ‘0’ đến ‘9’ độ dài nhỏ hơn 10 và số nguyên M, hãy đưa ra tất cả các cách chèn vào S các dấu ‘+’ hoặc ‘-‘ để thu được số M cho trước nếu không có phương án nào thỏa mãn thì ghi là khong the chen.
Dữ liệu vào từ tệp PHEPTOAN.INP gồm 2 dòng
- dòng 1 xâu S
- dòng 2 số nguyên M
Kết quả ra file PHEPTOAN.OUT tất cả các cách chèn hoặc khong the chen

PHEPTOAN.INP
PHEPTOAN.OUT
1234567
10
-1-2+3+4+5-6+7
-1+2-3+4-5+6+7
+1-2-3-4+5+6+7
+1-2+3+4+5+6-7
+1+2-3+4+5-6+7
+1+2+3-4-5+6+7
12345
6
Khong the chen

Chỉnh sửa lại chương trình để đưa ra một cách chèn thỏa mãn nếu có thể
ví dụ
M=8, s=’1234567’ một cách chèn ‘-1-2-3-4+5+6+7’

Bài 8: Lập chương trình liệt kê tất cả các tổ hợp chập k của n phần tử
Dữ liệu vào: từ tệp TOHOP.INP gồm 2 số nguyên k và n (k<n)
Dữ liệu ra: Ghi tất cả các tổ hợp liệt kê được vào tệp TOHOP.OUT, mỗi phương án ghi trên một dòng.
TOHOP.INP
TOHOP.OUT
2 4
1 2
1 3
1 4
2 3
2 4
3 4
Phát triển bài toán thành liệt kê tất cả tổ hợp chập k của dãy a1,a2,…,an 


Bài 9: Một xâu X=x1,x2,…,xm được gọi là xâu con của xâu Y=y1,y2,…,yn nếu ta có thể nhận được xâu X từ xâu Y bằng cách xóa đi một số kí tự, tức là tồn tại một dãy các chỉ số:
1<=i1<i2<…<im<=N để x1=yi1, x2=yi2, xm=yim

Ví dụ: X=’adz’ là xâu con của xâu Y=’baczdtz’ ; i1=2<i2=5<i3=7.


Đọc xâu từ tệp xaucon.inp độ dài không quá 15 kí tự chỉ gồm các kí tự ‘a’ đến ‘z’(các kí tự trong xâu là khác nhau).


Hãy liệt kê tất cả các xâu con khác nhau của xâu s và ghi vào tệp xaucon.out



Bài 10: Tiền khách sạn (đề thi học sinh giỏi tỉnh Bình phước năm 2015)

  Trong dịp nghi lễ 30 tháng 4 và 1 tháng 5 vừa qua do cùng đợt nghỉ với ngày giỗ tổ Hùng Vương 10 tháng 3(âm lịch) nên số ngày nghỉ lễ tăng lên. Vì thế lượng khách du lịch đổ về Nha Trang tham quan cũng tăng kỷ lục, dẫn đến tinh trạng các khách sạn ở đây “cháy phòng”.
      Khách sạn Quang Huy chỉ còn một phòng nên quyết định cho thuê phòng này theo hình thức thỏa thuận về giá cả. Sau khi tổng hợp các đơn đặt hàng, khách sạn nhận được n đơn đặt hàng, trong đó đơn đặt hàng thứ i đăng ký ngày bắt đầu là ai, ngày trả phòng là bi và chấp nhận trả số tiền thuê phòng là ci.
     Do có nhiều đơn đặt hàng, thời gian đặt phòng lại chồng chéo nhau, số tiền khách hàng chấp nhận trả cho khách sạn cũng khác nhau nên ban quản lý khách sạn đang rất khó khăn không biết nhận lời hay từ chối khách hàng nào.
Yêu cầu: Viết chương trình giúp khách sạn nhận đơn đặt phòng sao cho lợi nhuận thu được là lớn nhất.
Lưu ý: Theo điều lệ của khách sạn, khách hàng phải ưả phòng trước 12 giờ trưa, khách hàng khác có thể nhận phòng từ 12 giờ trong một ngày.
Dữ liệu vào: được ghi trên tệp tienks.inp bao gồm:
o Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 12000) thể hiện số đơn đặt hàng.
o n dòng tiếp theo gồm 3 số nguyên ai, bi và ci. Mỗi số cách nhau một khoảng trắng với ràng buộc(l ≤ai ≤ bi ≤ 100, 0 ≤ c ≤1000).
Dữ liệu ra: lưu trong tệp tienks.out với một số nguyên thể hiện số tiền lớn
Ví dụ:
TIENKS.INP
TIENKS.OUT
Vi dụ 1
3
128
236
476
20
Vi dụ 2
4
145
138
354
469
17
Bài 11: Dãy số
Cho dãy số nguyên a1,a2,..an. số ap (1 < p < n) được gọi là một số trung bình cộng trong dãy nếu tồn tại 3 chỉ số i, j, k (1 < i, j, k < n) đôi một khác nhau,
sao cho ap = (ai + aj + ak)/3
Yêu cầu: Cho n và dãy số a1 a2,.. an„. Hãy tìm số lượng các số trung bình cộng trong dãy.
Dữ liệu vào:  Từ tệp TBC.INP
-              Dòng đầu ghi số nguyên dương n (3 < n < 1000)
-              Dòng thứ hai chứa n số nguyên ai  (|ai|< 108) mỗi số cách nhau bởi dấu cách.
Kết quả ra : Ghi vào tệp TBC.OUT
Số lượng các số trung Bình cộng trong dãy.
ví dụ:

TBC.INP
TBC.OUT
5
4 3 6 3 5
2
7
6 4 5 2 8 9 7
5

Chia sẻ bài viết
Bài liên quan

1 nhận xét: