Giáo trình

Giáo trình Pascal 7.0

Toán học và thống kê

CHƯƠNG TRÌNH CON

Tác giả: Võ Thanh Ân

Chương IV: CHƯƠNG TRÌNH CON

  1. KHÁI NIỆM VỀ CHƯƠNG TRÌNH CON

Trong chương trình, có những đoạn cần phải lập đi, lập lại nhiều lần ở những chỗ khác nhau. Để tránh phải viết lại các đoạn đó người ta thường phân chương trình ra thành nhiều module, mỗi module giải quyết một công việc nào đó, các module như vậy là những chương trình con (subprogram).

Một tiện lợi khác của việc sử dụng module là ta có thể dễ dàng kiểm tra tính đúng đắn của nó trước khi ráp nối vào chương trình chính. Do đó việc xác định sai sót và tiến hành điều chỉnh trong chương trình sẽ thuận lợi hơn.

Trong Pascal chương trình con được viết dưới dạng hàm (FUNCTION) hoặc thủ tục (PROCEDURE). Hàm và thủ tục đều là những chương trình con, nhưng hàm khác thủ tục ở chỗ hàm trả về một giá trị cho lệnh gọi thông qua tên hàm còn thủ tục thì không. Do đó ta chỉ dùng hàm

Đối với Borland Pascal 7.0 điều này không còn bắt buộc vì ta có thể gọi hàm như gọi một thủ tục. Không nhất thiết phải lấy giá trị trả về. Để thực hiện được điều này trong menu Options >Compiler cần khai báo cú pháp mở rộng (eXtended syntax), hoặc trong chương trình cần có dẫn hướng biên dịch {$ X+}. Nếu không, khi biên dịch (gõ F9) Pascal sẽ thông báo lỗi “Error 122: Invalid variable reference”. Tuy vậy, dù không có dẫn hướng biên dịch {$ X+}, khi gõ CTRL+F9 chương trình vẫn chạy như thường! Ví dụ:{$X+}Program TestExtendSyntax;uses crt;var i,j:byte;{-------------}Function DoiViTri(i,j: byte):byte;Var Tam:byte;BEGINTam:=i; i:=j; j:=tam;Gotoxy(i,j); write('*')END;{--------------}BEGINi:=5; j:=20;Gotoxy(i,j); write('*');Doivitri(i,j);readln;END.
khi thoả mãn các yêu cầu sau.

  • Ta muốn nhận một kết quả và chỉ một mà thôi.
  • Ta cần dùng tên chương trình con (chứa kết quả đó) để viết trong các biểu thức.

Nếu không thỏa hai yêu cầu trên thì ta dùng thủ tục.

Borland Pascal thiết kế và cài đặt sẵn trong các Unit đi gèm theo gói phần mềm nhiều thủ tục và hàm rất tiện dùng. Muốn sử dụng các thủ tục hoặc hàm trong Unit nào ta chỉ cần khai báo tên Unit đó trong câu lệnh USES. Tuy nhiên phần lớn các thủ tục và hàm dùng trong chương trình là do người dùng phải tự viết.

  1. HÀM (FUNCTION)

Hàm là một chương trình con tính toán trả về cho ta một giá trị kiểu vô hướng. Cấu trúc hàm như sau:

FUNCTION <Tên hàm>[(<Th.số>:<Kiểu>[;<Th.số>: <Kiểu>])]: <KiểuKQ>; (Header)
[VAR <Biến>:<Kiểu>[;<Biến>: <Kiểu>]] Khai báo các biến cục bộ nếu có.
BEGIN <các câu lệnh>END; Thân hàm
  • Tên hàm là một danh biểu, phải tuân thủ theo qui tắc đặt danh biểu đã đề cập ở chương I.
  • Một hàm có thể không có hoặc có một hoặc nhiều tham số. Trong trường hợp có nhiều tham số có cùng một kiểu dữ liệu thì ta có thể viết chúng cách nhau bởi dấu , (phẩy). Ngược lại, các tham số hình thức khác kiểu nhau thì phải cách nhau dấu ; (chấm phẩy).
  • KiểuKQ là một kiểu vô hướng, nó phản ảnh kiểu của giá trị mà hàm trả về lại sau khi chạy xong. Ví dụ, ta khai báo hàm như sau:

FUNCTION TEST(x,y:Integer; z:Real): Real;

Đây là một hàm có tên là TEST, với 3 tham số, x và y thuộc kiểu Integer, z thuộc kiểu real, hàm trả về một kết quả kiểu real.

  • Trong hàm, ta có thể sử dụng các hằng, kiểu, biến dùng riêng trong nội bộ hàm.
  • Thông thường mục đích sử dụng hàm là để lấy trị trả về do đó cần lưu ý gán kết quả cho tên hàm trong thân hàm.

Ví dụ 1: Ta xây dựng hàm DT truyền tham số vào là bán kính của hình tròn, hàm này sẽ trả về diện tích của hình tròn đó.

Program TinhDienTich;

Uses Crt;

VAR BanKinh: real; Phép gán để trả về giá trị cho tên hàm. Ch: Char;

{--------------------------------------------}

Function DT(Radius:Real):Real;

Begin

DT := PI * Radius* Radius;

End;

{--------------------------------------------}

Begin

Clrscr;

Repeat

Write(‘Nhập bán kính: ’); Readln(BanKinh);

Writeln(‘Diện tích hinh tron tuong ung: ‘ ,DT(Bankinh):0:2);

Writeln;

Write(‘Tiếp tục (C/K)? ’);

Repeat

ch:=readkey;

Until Upcase(ch) in [‘C’,’K’];

Until UpCase(Ch) = ‘K’; {Lưu ý: ‘K’ in hoa}

End.

Ví dụ 2:

Program TinhGiaithua;

USES CRT;

Var Num:longint; Ch:char; X,Y:byte;

{---------------------------------------------}

Function GiaiThua(m: longint): longint;

Var Tam, Dem:Longint;

BEGIN

IF (M<0) THEN

Begin

Write(‘Khong tinh duoc’); HALT(1);

End

ELSE

Begin

Tam:=1;

For Dem:=1 to m do Tam:=Tam*Dem;

GiaiThua:=Tam;

End;

END;

{-------------- Chương trình chính -------------------------}

BEGIN

Writeln(‘CHUONG TRINH TINH GIAI THUA.’);

REPEAT

Write(‘Cho so nguyen muon tinh giai thua. M= ‘);

X:=WhereX; Y:=WhereY;

REPEAT

Gotoxy(X,Y); CLREOL; Readln(Num);

UNTIL (Num>=0);

Writeln(M,’! = ’,GiaiThua(Num));

REPEAT

Write(‘Tinh nua khong ? (C/K) :’); CH:=READKEY;

UNTIL Upcase(Ch) in [‘C’,’K’];

Writeln(Ch);

UNTIL Upcase(Ch)=’K’;

Readln

END.

  1. THỦ TỤC (PROCEDURE)

Cấu trúc của một thủ tục như sau:

PROCEDURE <Tên>(<Th.số>:<Kiểu>[;<Th.số>: <Kiểu>]): <Kiểu>; (Header)
[VAR <Biến>:<Kiểu>[;<Biến>: <Kiểu>] Khai báo các biến cục bộ nếu có.
BEGIN <các câu lệnh>END; Thân thủ tục.

Như vậy cấu trúc của một thủ tục cũng tương tự như cấu trúc của một hàm. Chỉ có hai điều khác:

  • Header bắt đầu bằng từ khóa Procedure thay vì Function.
  • Không có câu lệnh gán <Tenham:=GiaTri;> trong thân Procedure.

Ví dụ:

Thủ tục INSO sau sẽ in các số từ 1 đến giá trị biến truyền vào. Với n là tham số thực tế, So là tham số hình thức.

Program TEST;

Var n: Integer;

{-----------------------------------------}

Procedure INSO( So : Integer);

Var i: Integer;

Begin

For i := 1 to So do

Write( i:10 );

End;

{------------ Chương trình chính --------------------}

Begin

Write(‘Nhập một số bất kỳ lớn hơn không: ’); Readln(n);

INSO( n );

Readln;

End.

  1. LỜI GỌI CHƯƠNG TRÌNH CON VÀ VẤN ĐỀ TRUYỀN THAM SỐ.

Một chương trình có thể gồm một chương trình chính và nhiều chương trình con. Kèm theo đó là các biến, các tham số khai báo ở các vị trí khác nhau trong chương trình. Khả năng từ một vị trí nào đó trong chương trình “nhìn thấy” một chương trình con, một biến đã được khai báo là rất quan trọng. Mặt khác khi làm việc theo nhóm, các chương trình con, các modune khác nhau của chương trình có thể do nhiều người, nhiều nhóm lập trình khác nhau thực hiện. Khi đó khả năng xảy ra các nhóm khác nhau dùng cùng một tên biến, tên hàm, tên thủ tục cho các mục đích khác nhau là rất lớn. Vì vậy ngoài khả năng “nhìn thấy”, chương trình cần có một cơ chế cấu trúc sao cho có thể “che khuất” các biến khi cần thiết. Phần sau đây, nhằm mục đích đó, nghiên cứu các khái niệm liên quan đến “tầm vực “ của biến và của chương trình (con) cũng như các hiệu ứng lề (side effect) có thể xảy ra.

KHỐI (block): Một khối bắt đầu từ Header (PROGRAM | FUNCTION | PROCEDURE) của khối đó cho đến từ khóa END (END. hoặc END;) của thân chương trình/chương trình con tương ứng.

Minh họa:

PROGRAM ProgName;VAR a,b: type1; x:type2BEGIN…….…….END.PROCEDURE Proc1(t,h:type1; Var k:type2);VAR x,yBegin…….…….End;PROCEDURE Proc2Var qBEGIN…….…….END;FUNCTION func1(r:type): type;Var xBegin…….…….End;

Trong minh họa trên ta có các khối ứng với chương trình chính, các khối ứng với các Procedure Proc1, Procedure Proc2, Function func1, trong đó Proc1 và Proc2 là hai khối con cùng cấp, func1 là khối con của khối Proc2.

TẦM VỰC: Tầm vực của một biến hay một chương trình con là phạm vi mà biến đó hoặc chương trình con đó được nhìn thấy trong chương trình (ie: có thể gọi được biến đó hoặc chương trình con đó). Tầm vực của một biến hay một chương trình con bắt đầu từ chỗ nó được khai báo trong khối cho đến hết khối mà nó được khai báo trong đó, kể cả trong các khối con trừ khi trong khối con có khai báo lại biến hoặc chương trình con đó.

Qui định này về tầm vực là qui định của riêng từng ngôn ngữ. Mỗi khi học một ngôn ngữ mới sinh viên cần tham khảo qui định vê tầm vực của riêng ngôn ngữ đó.

Theo qui định trên, Và áp dụng cho hình minh họa trước ta thấy:

  • Các biến a,b là các biến toàn cục có thể gọi được ở bất cứ nới đâu trong chương trình.
  • Biến x của chương trình chính có thể gọi được ở bất cứ đâu trong chương trình trừ trong PROCEDURE Proc1 và trong FUNCTION func1vì trong procedure/function này có khai báo lại biến x. Trong thân procedure/function đó khi gọi x là ta gọi đến biến x cục bộ của nó chứ không phải biến x toàn cục.
  • Các biến t,h,k và y chỉ có thể gọi được trong Proc1 mà thôi.
  • Biến x nếu gọi trong Proc1 là biến cục bộ của riêng nó mà thôi.
  • Biến q có thể gọi được trong Proc2 và trong func1 mà thôi. Biến r chỉ có thể gọi được trong Func1 mà thôi. Biến x nếu gọi trong func1 là biến cục bộ của riêng func1, không liên quan gì đến biến x khai báo trong chương trình chính và trong Proc1.
  • Procedure Proc1 có thể gọi được trong Proc2, Func1 và trong chương trình chính. Trong Procedure Proc1 dĩ nhiên, theo qui định này, cũng có thể gọi chính nó (Đây là trường hợp gọi đệ qui mà ta sẽ nghiên cứu sau)
  • Proc2 có thể gọi được trong chương trình chính, trong Func1 và trong chính nó. Proc1 không thể gọi được Proc2.
  • Func1 chỉ có thể gọi được bới Proc2.
  • Proc1 và chương trình chính không thể gọi được Func1.
  • Có một ngoại lệ: Chương trình chính không thể gọi chính nó.
  • HOẠT ĐỘNG CỦA CHƯƠNG TRÌNH CON KHI ĐƯỢC GỌI VÀ SỰ BỐ TRÍ BIẾN.
  • Khi chương trình hoặc chương trình con được gọi thì các biến, các “tên” chương trình con được bố trí trong một vùng nhớ gọi là STACK. Khi chương trình chính được gọi thì các biến toàn cục được bố trí vào stack và tồn tại ở đó cho đến lúc chấm dứt chương trình. Khi các chương trình con được gọi thì các biến trong khai báo tham số hoặc sau từ khóa VAR (của nó) được bố trí vào stack và sẽ được giải phóng khi chương trình con này chấm dứt. Điều này rất có lợi vì nó cho phép ta sử dụng vùng nhớ hợp lí hơn. Người ta càng dùng ít biến toàn cục càng tốt để tránh lỗi (trong thời gian chạy) làm tràn stack (Stack overflow error).
  • VẤN ĐỀ TRUYỀN THAM SỐ KHI GỌI CHƯƠNG TRÌNH CON.

Khi gọi một chương trình con (thủ tục hay hàm) ta phải theo các qui định sau đây:

  • - Nếu chương trình con có qui định các tham số thì phải truyền giá trị hoặc biến cho các tham số đó.
  • - Phải truyền đủ số tham số.
    Có một điều khó chịu là Pascal cho phép “quá tải” các tham số trong các thủ tục của “bản thân” nó như trong các thủ tục Write, Writeln. Chúng ta gọi Writeln(‘Mot tham so’) hay Writeln(‘Tham so thu nhat’,’Tham so thu hai’) đều được trong khi điều đó lại không cho phép đối với các chương trình con được viết bới người dùng!
  • - Phải truyền đúng kiểu dữ liệu theo thứ tự các tham số đã khai báo.

Để hiểu rõ cách Pascal xử lí việc truyền tham số chúng ta cần xem qua ví dụ sau đây:

Program ParameterPassing;

Var a,b:byte; c:integer;

{------------------------------------------------------}

Procedure TestVar (x,y,z: byte; Var t: integer);

Var d: byte;

Begin

D:=4; {1}

X:=X+D; B:=B+X; T:=T+D; {2}

Writeln(‘Ben trong thu tuc:’);

Writeln(‘A=’,a, ‘B=’,b,’C=’,c,’D=’,d,’X=’,x,’Y=’,y,’Z=’,z,’T=’,t);

End;

{------------------------------------------------------}

BEGIN

A:=3; B:=5; C:=8;

Writeln(‘Truoc khi goi thu tuc:’);

Writeln(‘A=’,a, ‘ B=’,b,’ C=’,c);

TestVar(a,5,c,c);

Writeln(‘Sau khi goi thu tuc:’);

Writeln(‘A=’,a, ‘ B=’,b,’ C=’,c);

Readln;

END.

  • Quá trình chạy chương trình trên và diễn biến trong bộ nhớ như sau:
  • * Trước khi gọi thủ tục:
  • Cấp vùng nhớ cho các biến toàn cục a,b,c.

STACK
A=3B=5C=8
Kết xuất của chương trình:

Truoc khi goi thu tuc:

A=3 B=5 C=8

* Trong khi thực hiện thủ tục:

  • Cấp vùng nhớ cho các biến cục bộ x,y,z,t,d.
  • Chuyển giao tham số: TestVar(a,5,c,c);

Các tham số x,y,z gọi là các tham trị. Việc chuyển giao giá trị cho các tham số này có thể được thực hiện bằng trị hoặc bằng biến, giá trị được chuyển giao sẽ được COPY vào ô nhớ tương ứng của các biến đó. Các ô nhớ ứng với x,y,z lần lượt có giá trị là 3,5,8.

Tham số T được khai báo sau từ khóa VAR được gọi là tham biến. Việc chuyển giao tham số chỉ có thể được thực hiện bằng biến. Ở đây ta đã chuyển giao biến C cho vị trí tham số T. Pascal không copy giá trị của biến C vào ô nhớ ứng với T mà tạo một “con trỏ” để trỏ về C, mọi thao tác đối với T sẽ được thực hiện ở ô nhớ của C. Biến D sẽ được khởi tạo (lần đầu) bằng 0.

STACK
A=3 B=5 C=8 x=3
y=5 z=8
T= (Trỏ về C)
d=0

Sau dòng lệnh {1} và {2} của thủ tục trong bộ nhớ sẽ là:

STACK
A=3 B=5+(3+4) C=8+4 x=3+4
Y=5 z=8
T= (Trỏ về C)
d=4

Kết xuất của chương trình khi chạy đến câu lệnh cuối của thủ tục là:

Truoc khi goi thu tuc:

A=3 B=5 C=8

Ben trong thu tuc:

A=3 B=12 C=12 D=4 X=7 Y=5 Z=8 T=12

  • * Sau khi thực hiện thủ tục:
  • Thu hồi các vùng nhớ đã được cấp cho thủ tục:

STACK
A=3B=5+(3+4)C=8+4
Kết xuất của chương trình khi chạy đến câu lệnh cuối là:

Truoc khi goi thu tuc:

A=3 B=5 C=8

Ben trong thu tuc:

A=3 B=12 C=12 D=4 X=7 Y=5 Z=8 T=12

Sau khi goi thu tuc:

A=3 B=12 C=12

  • Mấy vấn đề cần nhớ:

Đối với tham trị có thể chuyển giao bằng trị hoặc bằng biến. Giá trị được chuyển giao được COPY vào nội dung ô nhớ của biến tham trị.

Đối với tham biến chỉ có thể chuyển giao bằng biến. Một con trỏ sẽ trỏ về biến chuyển giao, mọi thao tác sẽ được thực hiện trên biến chuyển giao.

  • Và kết luận quan trọng:

Sự thay đổi của tham biến bên trong thủ tục sẽ làm thay đổi giá trị của biến chuyển giao (Trường hợp của biến C). Điều này không xảy ra đối với tham trị (Trường hợp của biến A, sự thay đổi của biến X không ảnh hưởng đến nội dung của ô nhớ A).

Sự thay đổi của biến chuyển giao trong trường hợp tham biến được gọi là hiệu ứng lề (Side effect). Người lập trình phải hết sức lưu ý để phòng ngừa hiệu ứng lề ngoài mong muốn.

  1. TÍNH ĐỆ QUI CỦA CHƯƠNG TRÌNH CON

Như đã nói trên một chương trình con trong Pascal có thể gọi về chính nó. Một lời gọi như thế gọi là một lời gọi đệ qui (recursion). Gọi đệ qui là một kỹ thuật lập trình rất quan trọng vì nó thường ngắn gọn và thường … phù hợp với suy nghĩ tự nhiên về nhiều cách giải bài toán. Thậm chí nhiều bài toán hầu như chỉ có thể dùng đệ qui. Tuy nhiên xét về tốc độ giải thuật cũng như tối ưu không gian bộ nhớ thì đệ qui thường không phải là một giải pháp tốt. Người ta thường cố gắng khắc phục đệ qui bằng cách dùng vòng lặp và sử dụng stack nhưng đó là công việc không mấy dễ dàng.

Ví dụ 1:

Định nghĩa giai thừa của một số nguyên không âm m như sau:

Lập trình để tính giai thừa của một số nguyên không âm nhập từ bàn phím.

Cách 1: Dùng đệ qui.

Function GT(m: Integer): Longint;

Begin

If ( m = 0 ) or ( m = 1 ) then

GT := 1

Else

GT := m * GT( m-1 );

End;

Rõ ràng cách viết đệ qui là “phù hợp một cách tự nhiên” với định nghĩa của giai thừa.

Việc thực thi một lời gọi đệ qui diễn ra tương tự như sau:

Ví dụ ta truyền vào giá trị m = 4, tức gọi GT(4).

GT(4) m = 4 → Tính 4 * GT(4-1) → gọi GT(3)

GT(3) m = 3 → Tính 3 * GT(3-1) → gọi GT(2)

GT(2) m = 2 → Tính 2 * GT(2-1) → gọi GT(1)

GT(1) m = 1 → Gán GT(1):=1

Cuối cùng một quá trình “tính ngược” sẽ cho phép trả về giá trị của GT(4):

GT(4)  4 * (3 * (2 * GT(1))).

Cách 2: Dùng vòng lặp.

Function GiaiThua(m: longint): longint;

Var Tam, Dem:Longint;

BEGIN

IF (M<0) THEN

Begin

Write(‘Khong tinh duoc’); HALT(1);

End

ELSE

Begin

Tam:=1;

For Dem:=1 to m do Tam:=Tam*Dem;

GiaiThua:=Tam;

End;

END;

Lưu ý: Một chương trình con đệ qui bao giờ cũng có ít nhất hai phần:

  • Phần gọi đệ qui. Trong ví dụ trên là GT:=m*GT(m-1).
  • Phần “neo”. Trong ví dụ trên là IF (m=0) or (m=1) THEN GT:=1. Phần này rất quan trọng vì nó đảm bảo quá trình đệ qui phải dừng sau một số hữu hạn bước. Quên phần này sẽ xảy ra lỗi làm tràn bộ nhớ stack (stack overflow) khi xảy ra quá trình đệ qui.

Ví dụ 2:

Số Fibonacci được định nghĩa như sau:

Fibo(n)=

Chúng ta thấy bản thân định nghĩa số Fibonacci đã chứa một biểu thức truy hồi, tức về mặt lập trình đã dẫn tới một gợi ý lời gọi đệ qui. Chúng ta có thể xây dựng một hàm tính số Fibonacci như sau:

Cách 1: (Dùng đệ qui)

FUNCTION FIBO(n: word): word;

BEGIN

IF (n=1) or (n=2) THEN

FIBO:=1

ELSE

FIBO := FIBO(n-1)+FIBO(n-2);

END;

Trong cách này việc xây dựng hàm tính số Fibonacci tương đối dễ dàng vì cách viết hoàn toàn đồng nhất với định nghĩa toán học. Ví dụ thứ hai này phức tạp hơn ví dụ thứ nhất vì lời gọi đệ qui chia làm hai nhánh.

Cách 2: (Dùng chỗ lưu trữ tạm)

FUNCTION FIBO(n:word):word;

Var Counter,F1,F2:word;

BEGIN

F1:=1; F2:=1; Fibo:=1;

FOR Counter:=3 TO n DO

Begin

Fibo:=F1+F2;

F1:=F2;

F2:=Fibo;

End;

END;

Trong cách 2 này việc khử đệ qui không còn dễ dàng nữa vì cách đó không chứa rõ ràng một qui tắc tổng quát cho phép xử lí.

Ví dụ 3:

Bài toán tháp Hà Nội:

Có 3 cái cọc, đánh dấu A, B, C, và N cái đĩa. Mỗi đĩa đều có một lỗ chính giữa để đặt xuyên qua cọc, các đĩa đều có kích thước khác nhau. Ban đầu tất cả đĩa đều được đặt ở cọc thứ nhất theo thứ tự đĩa nhỏ hơn ở trên.

Yêu cầu: Chuyển tất cả các đĩa từ cọc A qua cọc C với ba ràng buộc như sau:

  1. Mỗi lần chỉ chuyển được một đĩa.
  2. Trong quá trình chuyển đĩa có thể dùng cọc còn lại để làm cọc trung gian.
  3. Chỉ cho phép đặt đĩa có bán kính nhỏ hơn lên đĩa có bán kính lớn hơn.

Trong bài toán trên hình dung một lời giải tổng quát cho trường hợp tổng quát N đĩa là không dễ dàng. Hãy bắt đầu với các trường hợp đơn giản.

N = 1. Lời giải trở thành tầm thường (nhưng không kém phần quan trọng đâu!). Đơn giản là chuyển đĩa này từ cọc A qua cọc C là xong.

N = 2. Để đảm bảo ràng buộc thứ hai ta bắt buộc chuyển đĩa trên cùng từ cọc A qua cọc B. Chuyển tiếp đĩa còn lại từ cọc A qua cọc C. Chuyển tiếp đĩa đang ở cọc B sang cọc C.

N=3. Ta phải thực hiện 7 bước như sau:

Trạng thái ban dầu ------------
Bước 1: Chuyển một đĩa từ A qua C. ---------- --
Bước 2: Chuyển một đĩa từ A qua B. ------ ---- --
Bước 3: Chuyển một đĩa từ C qua B. ------ ------
Bước 4: Chuyển một đĩa từ A qua C. ------ ------
Bước 5: Chuyển một đĩa từ B qua A. -- ---- ------
Bước 6: Chuyển một đĩa từ B qua C. -- ----------
Bước 7: Chuyển một đĩa từ A qua C. ------------

Hãy quan sát kết quả ở bước thứ ba. Đây là một kết quả quan trọng vì nó cho ta thấy từ trường hợp N=3 bài toán đã được phân chia thành hai bài toán với kích thước nhỏ hơn: đó là bài toán chuyển 1 đĩa từ cọc A qua cọc C lấy cọc B làm trung gian và bài toán chuyển 2 đĩa (dời) từ cọc B sang cọc C lấy cọc A làm trung gian. Hai bài toán con này đã biết cách giải (trường hợp N=1 và trường hợp N=2).

Nhận xét đó cho ta gợi ý trong trường hợp tổng quát:

  • Bước 1: Dời (N-1) đĩa trên cùng từ cọc A sang cọc B lấy cọc C làm trung gian.
  • Bước 2: Chuyển 1 đĩa dưới cùng từ cọc A sang cọc C.
  • Bước 3: Dời (N-1) đĩa đang ở cọc B sang cọc C lấy cọc A làm trung gian.

Bài toán đối với N đĩa như vậy được “đệ qui” về hai bài toán (N-1) đĩa và bài toán 1 đĩa. Quá trình đệ qui sẽ dừng lại khi N=0 (không còn đĩa để dời hoặc chuyển).

Chương trình sẽ như sau:

PROGRAM ThapHanoi;

Uses crt;

TYPE

Cot = Char;

{------------------------------------------------------}

Procedure Chuyen(X,Y:Cot);

BEGIN

Writeln(X,’ -> ‘,Y);

END;

{------------------------------------------------------}

Procedure Doi(N:byte; A,B,C:Cot);

{Dời N đĩa từ cọc A sang cọc C lấy cọc B làm trung gian}

BEGIN

IF (N>0) THEN

Begin

Doi(N-1,A,C,B); {Dời N-1 đĩa từ cọc A sang cọc B lấy cọc C làm trung gian}

Chuyen(A,C);

Doi(N-1,B,A,C); {Dời N-1 đĩa từ cọc B sang cọc C lấy cọc A làm trung gian}

End;

END;

{------------------------------------------------------}

BEGIN

Clrscr;

Write(‘Cho biet so dia :’); Readln(Sodia); Writeln(‘Cac buoc thuc hien:’);

Doi(Sodia,’A’,’B’,’C’);

Writeln; Writeln(‘Thuc hien xong!’); READLN;

END.

Nếu áp dụng chương trình này cho trường hợp N=3 ta có quá trình gọi đệ qui như sau:

Doi(1,A,B,C)
Doi(0,A,C,B)
Chuyen(A,C)
Doi(0,B,A,C)
Doi(3,A,B,C)
Doi(2,A,C,B) Chuyen(A,B)
Doi(1,C,A,B)
Doi(0,C,B,A)
Chuyen(C,B)
Doi(0,A,C,B)
Chuyen(A,C)
Doi(1,B,C,A)
Doi(0,B,A,C)
Chuyen(B,A)
Doi(0,C,B,A)
Doi(2,B,A,C) Chuyen(B,C)
Doi(1,A,B,C)
Doi(0,A,C,B)
Chuyen(A,C)
Doi(0,B,A,C)

Ví dụ này cho thấy việc kết xuất ở các câu lệnh Chuyen(X,Y) chỉ xảy ra khi toàn bộ các lời gọi đệ qui đã được thực hiện và cũng cho thấy thứ tự các lời gọi đệ qui lần cuối cùng. Nhận xét này rất quan trọng khi bạn viết thủ tục đệ qui vì lẽ bạn cần phải hình dung trước thứ tự các kết xuất nhất là khi lời gọi đệ qui có rất nhiều nhánh.

Đánh giá:
0 dựa trên 0 đánh giá

Cùng tác giả

 

Nội dung tương tự