Home Home » Pascal nâng cao » MỘT SỐ CHÚ Ý VỀ BÀI TẬP ỨNG DỤNG THUẬT TOÁN QUAY LUI

MỘT SỐ CHÚ Ý VỀ BÀI TẬP ỨNG DỤNG THUẬT TOÁN QUAY LUI

Thứ Bảy, 13 tháng 5, 2017
Thủ tục đệ quy quay lui có dạng
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;

Khi sử dụng ta bắt đầu bằng lời gọi Try(1);
Ví dụ:


Dạng 1: Xuất tất cả phương án (các phần tử xét lặp lại)
Vd: n=3: 000;001;010;,,,,

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;

 Dạng 2: Xuất các phương án với b[j] không trùng nhau. (phần tử không lặp trong các nghiệm)
Ví dụ: n=3; 123;132;213;231;312;321

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;

Một số bài toán ứng dụng cơ bản

Bài 1: 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


CODE THAM KHẢO:

var t:array[1..100] of longint;
   a,x:array[1..100] of 0..1;
   i,n:integer; sum,s:int64;
   kt:boolean;
   fi,fo:text;
   
procedure xuat;
   var i:integer;
   begin
     sum:=0;
     for i:=1 to n do
       sum:=sum+a[i]*t[i];
     if sum=s then
       begin
         x:= a;
         kt:=true;
         exit;
       end;
   end;

procedure try(i:integer);
   var j:integer;
   begin
   for j:=0 to 1 do
     if kt=false then
       begin
          a[i]:=j;
          if i=n then xuat else try(i+1);
       end;
   end;

begin
 assign(fi,'atm.inp'); reset(fi);
 assign(fo,'atm.out'); rewrite(fo);
 readln(fi,n,s); kt:=false;
 for i:=1 to n do read(fi,t[i]);
 try(1);
 if kt then
   begin
      for i:=1 to n do
         if x[i]=1 then write(fo,t[i],' ');
   end
   else write(fo,-1);
close(fO);
 end.

Bài 2: Tiền khách sạn

  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.
TIENKS.INP
TIENKS.OUT
Vi dụ 1
3
128
236
476
20
Vi dụ 2
4
145
138
354
469
17
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 trả 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 nhất

CODE THAM KHẢO

var i,t,d,n,k:integer; s:byte;
max,tks,vao,ra,a:array[0..100] of integer;
b:array[0..100] of 0..1;

procedure xuat;
var i:byte;
begin
d:=d+1; max[d]:=0;{reset để tính max hoán vị mới}
for i:=1 to k do max[d]:=max[d]+tks[a[i]];
end;

 procedure try(i:byte);
var j:byte;
begin
 for j:=1 to n do
   if b[j]=0 then
     begin
      a[i]:=j;
      if a[i]>a[i-1] then
      if vao[a[i]]>=ra[a[i-1]] then
      if i=k then xuat {kiem tra tuan tu cac hoan vi}
        else
        begin
         b[j]:=1;
         try(i+1);
         b[j]:=0;
        end;
   end;
end;

BEGIN
 assign(fi,'tienks.inp'); reset(fi);
 assign(fo,'tienks.out'); rewrite(fo);
 readln(fi,n);
 for i:=1 to n do
  readln(fi,vao[i],ra[i],tks[i]);
 d:=0;

for k:=1 to n do try(1); {xét tất cả hoán vị từ 1-n}

t:=max[1];
 for i:=2 to d do if max[i]>t then t:=max[i];
 write(fo,t);
close(fo);
end.


Bài 3: 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ìnhcộng trong dãy.
TBC.INP
TBC.OUT
5
4 3 6 3 5
2
7
6 4 5 2 8 9 7
5
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.

CODE THAM KHẢO

VAR a:array[0..1000] of integer;
    t,x:array[0..1000] of longint;
    b:array[0..1000] of 0..1;
   dem,i,j,kq,n:integer;
   fi,fo:text;

Procedure xuat;
var tong,i,j:integer;
begin
  tong:=0;
  for i:=1 to 3 do tong:=tong+x[a[i]];
  if tong mod 3 = 0 then {Tìm các phần tử chia hết cho 3}
  begin
    inc(dem);
    t[dem]:=tong;
  end;
end;

Procedure try(i:integer);
 var j:integer;
 begin
   for j:=1 to n do
     if b[j]=0 then
       begin
         a[i]:=j;
         if a[i]>a[i-1] then
         if i=3 then xuat else
         begin
           b[j]:=1;
           try(i+1);
           b[j]:=0;
         end;
     end;
  end;
BEGIN
   kq:=0;
   assign(fi,'tbc.inp'); reset(fi);
   assign(fo,'tbc.out'); rewrite(fo);
   readln(fi,n);
   for i:=1 to n do read(fi,x[i]);
   try(1);
   for i:=1 to n do {duyệt dãy ban đầu}
     for j:=1 to dem do
      if t[j] div 3=x[i] then 
{nếu có tổng chia hết thì tăng biến đếm}
       begin
         inc(kq); break; 
{Dem xong thoat khoi vong lap 2 vi Moi phan tu chi dem 1 lan}
       end;
   write(fo,kq);
   close(fo);
 end.

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

Comments[ 0 ]


Đăng nhận xét