Đệ qui quay lui và phương pháp nhánh cận
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (90.33 KB, 9 trang )
Đệ qui quay lui và phương pháp nhánh cận
Trần Đình Hưng
Bàitoán "Tháp Hà Nội" là một bài toán cơ bản của thuật toán đệ qui. Bài toán phátbiểu đơn
giản như sau: Cho 3 cọc A, B, C, cọc A chứa N đĩa với qui tắc trên nhỏdưới to, mỗi lần
chuyển chỉ được chuyển 1 đĩa từ cọc này sang 1 trong 2 cọc cònlại và giữ nguyên trật tự to
nhỏ, hãy đưa ra 1 cách chuyển N đĩa từ AC. Trong bài toán này ta có thể xử lí một cách dễ
dàng qua 3 lời gọi đệqui:
Procedure Chuyen(N, A, B, C: Byte);
Begin
If N=1 Then Write(Chr(A+64 ),' =>',Chr(C+64))
Else
Begin
Chuyen(N-1,A,B,C);
Chuyen(1,A,C,B);
Chuyen(N-1,B,C,A);
end;
End;
Chươngtrình chính chỉ cần gọi: Chuyen(N,1,3,2);
Tuynhiên vấn đề đặt ra ở đây rắc rối hơn: Cho 3 cọc A, B, C xếp trên 1 vòng trònlần lượt
là A, B, C chỉ được chuyển theo chiều kim đồng hồ A =>B=>C=>A.
Chúngta sẽ giải quyết bài toán bằng hai thủ tục đệ qui và thủ tục này gọi thủ tụckia thông
qua từ khoá Forward của Turbo Pascal.
Tư tưởng thuật toán như sau: Để chuyển N đĩa từ A sang Cta chuyển N-1 đĩa từ A sang C
với thủ tụcChuyen2, chuyển 1 đĩa từ A sang B (Chuyen1),chuyển N-1 đĩa từ C sang A
(Chuyen1),chuyển 1 đĩa từ B sang C (Chuyen1),chuyển N-1 đĩa từ A sang C (Chuyen2).
Nhưvậy có hai thủ tục: Chuyển A sang C và chuyển C sang A.
Dữliệu ra được ghi trong file text "Kq.dat".
Vídụ: A => B
B => C
...
Cấutrúc file rất đơn giản để tiết kiệm không gian đĩa, khi cho số đĩa chuyển lớn.
Program Chuyen_Dia;
Uses Crt;
Var N:Byte;
F:Text;
T:LongInt Absolute 0:$46C;
T1,T2,Dem:LongInt;
Procedure Chuyen1(N,C,A,B:Byte);Forward;
Procedure Khoi_Tao;
Begin
Write('Vao N:');Readln(N);
Assign(F,'Kq.Dat');
ReWrite(F);
Dem:=0;
End;
Procedure Chuyen2(N,A,C,B:Byte);
Begin
If N=1 Then
begin
Writeln(F,Chr(A+64),'->',Chr(B+64));
Writeln(F,Chr(B+64),'->',Chr(C+64));
Dem:=Dem+2;
end
Else
Begin
Chuyen2(N-1,A,C,B);
Chuyen1(1,A,B,C);
Chuyen1(N-1,C,A,B);
Chuyen1(1,B,C,A);
Chuyen2(N-1,A,C,B);
End;
End;
Procedure Chuyen1(N,C,A,B:Byte);
Begin
If N=1 Then
begin
Writeln(F,Chr(C+64),'->',Chr(A+64));
Dem:=Dem+1;
end
Else
Begin
Chuyen2(N-1,C,B,A);
Chuyen1(1,C,A,B);
Chuyen2(N-1,B,A,C);
end;
End;
Procedure Thuc_Hien;
Begin
T1:=T;
Chuyen2(N,1,3,2);
T2:=T;
Writeln('Thoi gian chaychuong trinh la:',(T2-T1)/18.2:10:10,' Giaý);
Write(F,'So lanchuyen:',Dem);
Write('So lanchuyen:',Dem);
Close(F);
Readln;
End;
BEGIN
Clrscr;
Khoi_Tao;
Thuc_Hien;
END.
Tương tự ta có thể viết chương trình cho cách chuyển từ Asang B.
Procedure Chuyen1(N,A,B,C:Byte);
Begin
If N=1 Then
Begin
Writeln(F,Chr(A+64),'->',Chr(B+64));
Dem:= Dem+1;
end
Else
Begin
Chuyen2(N-1,A,C,B);
Chuyen1(1,A,B,C);
Chuyen2(N-1,C,B,A);
end;
End;
Procedure Chuyen2(N,A,C,B:Byte);
Begin
If N=1 Then
Begin
Writeln(F,Chr(A+64),'->',Chr(B+64));
Writeln(F,Chr(B+64),'->',Chr(C+64));
Dem:=Dem+2;
end
