Mục đích của chương trình con là gì

Bạn đang xem tài liệu "Giáo án Tin học 11 - Bài 17: Chương trình con và phân loại - Lê Thị Bích Liên", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Người soạn: Hà Trung Hòa. Lớp: SP Tin 40 Giáo viên hướng dẫn: Lê Thị Bích Liên Ngày soạn : 30/09/2008 Ngày giảng : / /2008 Chương VI: Chương trình con và lập trình có cấu trúc Bài 17: Chương trình con và phân loại I. Mục đích yêu cầu Học sinh cần biết: Chương trình con thực chất là một khối lệnh [tập các lệnh] nhằm giải quyết một bài toán con để góp phần giải quyết một bài toán lớn hơn bằng một chương trình. Khi phải viết chương trình dài, phức tạp, việc sử dụng chương trình con là hết sức cần thiết. II. Phương pháp, phương tiện giảng bài Phương pháp: Thuyết trình, giảng giải Phương tiện: SGK, SGV Bảng phụ: III. Tiến trình bài giảng Nội dung Hoạt động GV và HS Kiểm tra bài cũ: Viết chương trình tính LuyThua=an. Với a là số thực, n là số nguyên nhập từ bàn phím. Chương VI: Chương trình con và lập trình có cấu trúc Bài 17: Chương trình con và phân loại 1. Khái niệm chương trình con. Bài toán 1: Tính tổng bốn luỹ thừa: TLuythua=an+bm+cp+dq Với a, b, c, d là các số thực, n, m, p, q là các số nguyên. Input: a, b, c, d kiểu thực; m, n, p, q kiểu nguyên. Output: Đưa ra màn hình kết quả TLuythua=an + bm + cp + dq. - Việc chia nhỏ các bài toán thành các bài toán con được gọi là cách thiết kế từ trên xuống. - Để nâng cao hiệu quả lập trình, các ngôn ngữ lập trình bậc cao đều cung cấp khả năng xây dựng chương trình con dạng tổng quát “đại diện” cho nhiều đoạn lệnh tương tự nhau. Ví dụ: tính luỹ thừa luythua=xk, trong đó lũy thừa và x là giá trị kiểu thực còn k thuộc kiểu nguyên. Ta có thể đặt tên cho chương trình con này là luythua và tham số cần thiết là x và k . Khi cần tính luỹ thừa cụ thể ta chỉ cần viết tên chương trình con và thay thế [x,k] bằng giá trị cụ thể tương ứng. program Tinh_tong; var TLuyThua,a,b,c,d:real; m,n,p,q:integer; Function LuyThua[x:real;k:integer]:real; var i:integer; Tich:real; begin Tich:=1.0; For i:=1 to k do Tich:=Tich*x; LuyThua:=Tich; end; BEGIN write['Nhap du lieu theo thu tu a, b, c, d, m, n, p, q:']; readln[a,b,c,d,m,n,p,q]; TLuyThua:=LuyThua[a,m]+LuyThua[b,n] +LuyThua[c,p] +LuyThua[d,q]; write['Tong luy thua=',TLuyThua:2:2]; readln; END. * Nhận xét: Sử dụng chương trình con chương trình ngắn gọn, dễ theo dõi hơn chương trình không sử dụng chương trình con. - Khi lập trình giải toán, ta có thể phân chia chương trình thành các khối [môđun], mỗi khối bao gồm các lệnh giải một bài toán nào đó. Mỗi khối lệnh sẽ được xây dựng thành một chương trình con. Sau đó, chương trình chính sẽ được xây dựng từ các chương trình con này. Chương trình con cũng có thể được xây dựng từ các chương trình con khác. Cách lập trình như vậy dựa trên phương pháp lập trình có cấu trúc và chương trình được xây dựng gọi là chương trình có cấu trúc. * Chú ý: Chương trình con đôi khi chỉ được dùng đúng một lần xong khi đó nó vẫn có tác dụng làm sáng sủa chương trình. Bài toán 2: Viết chương trình nhập vào số nguyên dương N [0 < N < 50] và dãy số nguyên dương a1, ..., an. Đưa ra số lượng số nguyên tố. Input: Số nguyên dương [ 0 < N < 50] và dãy số nguyên dương a1, ..., an Output: Số lượng số nguyên tố. * Khái niệm chương trình con [SGK] * Lợi ích của việc sử dụng chương trình con. - Tránh được việc phải lặp đi lặp lại cùng một dãy lệnh nào đó. VD: Bài toán 1, 2 - Hỗ trợ việc thực hiện các chương trình lớn. VD: Bài toán quản lý điểm - Phục vụ cho quá trình trừu tượng hoá. Ví dụ khi sử dụng các hàm toán học như sin[x], cos[x],...ta không cần xem nó được xây dựng như thế nào. Trừu tượng hoá là tư tưởng chủ đạo để xây dựng chương trình nói chung và chương trình có cấu trúc nói riêng. -Mở rộng khả năng ngôn ngữ. Ví dụ: Trong bài toán 1 ta xây dựng thêm được chương trình con luỹ thừa. - Thuận tiện cho phát triển, nâng cấp chương trình Đáp án: Program TinhLuyThua; Var a,LuyThua:real; i,n:integer; BEGIN Write[‘Nhap a=’];readln[a]; Write[‘Nhap n=’];readln[n]; LuyThua:=1.0; For i:=1 to n do LuyThua:=LuyThua*a; Write[‘Luy thua ‘,a:2:2,’^’,n,’ =’,LuyThua:8:4]; Readln; END. GV: Các chương trình giải các bài toán phức tạp thường rất dài, có thể gồm rất nhiều lệnh. Khi đọc những chương trình dài rất khó nhận biết được chương trình thực hiện các công việc gì và hiệu chỉnh chương trình cũng khó khăn. Vậy phải cấu trúc chương trình như thế nào để cho chương trình dễ đọc, dễ hiệu chỉnh, nâng cấp? Trước tiên chúng ta đi xét bài toán sau. GV: Đưa ra bài toán 1 GV: Theo toán học để giải được bài toán này ta làm như thế nào? HS: Ta sẽ tính từng luỹ thừa, sau đó cộng tổng các luỹ thừa đó lại ta được kết quả TLuythua. GV: Giả sử có bài toán sau: TLuyThua= 63+ 64+ 65+ 66 Khi em là nhóm trưởng [nhóm gồm 4 người ] và nhóm em nhận được bài toán thì làm cách nào để có kết quả nhanh nhất. HS: Trả lời. GV: Nhận xét và khẳng định: Có thể giao cho 4 người mỗi người thực hiện một bài. Giá trị TluyThua là tổng kết quả của bốn bài toán con đó. GV: áp dụng ý tưởng đó trong lập trình ta sẽ dùng các biến LuyThua1 để tính toán và lưu trữ kết quả của an. Tương tự LuyThua2, LuyThua3, LuyThua4 dùng để tính toán và lưu trữ kết quả của bm, cp, dq. GV: Cả lớp theo dõi chương trình tinh_tong trang 92 SGK. GV: Hãy quan sát và cho biết có mấy khối lệnh được viết tương tự nhau? HS: Có 4 khối lệnh được viết tương tự nhau. GV: Bằng trực quan một em cho cô biết khi viết như vậy em có nhận xét gì không ? HS: ở đây có 4 khối lệnh tương tự nhau được lặp đi lặp lại làm cho chương trình vừa dài, vừa khó theo dõi. GV: Để nâng cao hiệu quả lập trình, các ngôn ngữ lập trình bậc cao đều cung cấp khả năng xây dựng chương trình con dạng tổng quát “đại diện” cho nhiều đoạn lệnh tương tự nhau. Chẳng hạn, tính luỹ thừa luythua=xk, trong đó lũy thừa và x là giá trị kiểu thực còn k thuộc kiểu nguyên. Ta có thể đặt tên cho chương trình con này là luythua và tham số cần thiết là x và k . Khi cần tính luỹ thừa cụ thể ta chỉ cần viết tên chương trình con và thay thế [x,k] bằng giá trị cụ thể tương ứng chẳng hạn để tính an , bm, cp, dq ta viết luythua[a, n], luythua[b, m], luythua[c, p], luythua[d,q]. GV:Sau đây thầy sẽ giới thiệu cho các em chương trình tính TLuyThua có sử dụng chương trình con được viết bằng ngôn ngữ Pascal. GV: Treo bảng phụ. GV: Bảng phụ sử dụng một chương trình con là hàm LuyThua kiểu thực với các tham số hình thức là x kiểu thực, k kiểu nguyên. Khi cần tính các giá trị cụ thể ta chi việc gọi tên chương trình. Ví dụ: Tính LuyThua=an. Ta sẽ gọi LuyThua[a,n] GV: Một em cho thầy biết chương trình có sử dụng chương trình con có ngắn gọn và dễ theo dõi hơn so với chương trình không sử dụng chương trình con không? HS: Trả lời GV: Nhận xét và khẳng định: Chương trình có sử dụng chương trình con ngắn gọn, dễ theo dõi hơn chương trình không sử dụng chương trình con. GV: Theo em, để sản xuất ra được một chiếc xe máy, có phải chỉ cần qua tay một người thợ ? Hay phải qua một dây chuyền sản xuất ? HS: Trả lời GV: Đúng vậy, để sản xuất ra một chiếc xe máy người ta phải phân thành nhiều công đoạn như sản xuất ra khung xe, yên xe,... Mỗi công đoạn được giao cho các tổ lao động chuyên làm một bộ phận. Và có một bộ phận chuyên lắp ráp sản phẩm từ các bộ phận nhỏ. GV: Đối với lập trình cũng vậy, khi lập trình giải toán, ta có thể phân chia chương trình thành các khối [môđun], mỗi khối bao gồm các lệnh giải một bài toán nào đó. Mỗi khối lệnh sẽ được xây dựng thành một chương trình con. Sau đó, chương trình chính sẽ được xây dựng từ các chương trình con này. Chương trình con cũng có thể được xây dựng từ các chương trình con khác. Cách lập trình như vậy dựa trên phương pháp lập trình có cấu trúc và chương trình được xây dựng gọi là chương trình có cấu trúc. GV: Cần chú ý là chương trình con đôi khi chỉ được dùng đúng một lần xong khi đó nó vẫn có tác dụng làm sáng sủa chương trình. GV: Để hiểu rõ hơn về việc cần thiết phải sử dựng chương trình con chúng ta đi xét bài toán 2. GV: Đưa ra bài toán GV: Từ bài toán trên một em xác định Input, Output? HS: Trả lời. GV: Để giải được bài toán trên ta cần phải làm gì? HS: Trả lời GV: Tạo 1 biến: đếm số lượng số nguyên tố. Lần lượt với mỗi số ai [với i=1,...,n] ta kiểm tra số đó có là số nguyên tố hay không. Nếu là số nguyên tố thì tăng biến đếm lên 1 đơn vị. Như vậy với N = 50 thì ta phải viết đi viết lại 50 lần dãy lệnh tương tự nhau để kiểm tra một số nguyên dương có phải là số nguyên tố hay không? GV: Như vậy chúng ta thấy được việc cần thiết phải sử dụng chương trình con trong chương trình. GV: Qua các ví dụ trên ta có khái niệm chương trình con. Vậy mời 1 em đọc khái niệm chương trình con. HS: Đọc khái niệm chương trình con trong SGK. GV: Qua hai ví dụ trên một em cho biết sử dụng chương trình con có những lợi ích gì? GV [Giải thích]: Do chương trình được tạo thành từ các chương trình con nên dễ đọc, dễ hiểu, dễ kiểm tra và hiệu chỉnh. Việc nâng cấp, phát triển chương trình con nào đó, thậm chí bổ sung thêm các chương trình con mới nói chung không gây ảnh hưởng tới các chương trình con khác. * Lưu ý: Nếu còn thời gian thì yêu cầu học sinh suy nghĩ và đưa ra các bài toán cần thiết phải sử dụng chương trình con. III. Củng cố Tóm lại qua bài học hôm nay chúng ta cần lưu ý: Chương trình con Dãy lệnh thực hiện 1 công việc nào đó Xây dựng nên chương trình chính và có thể được xây dựng từ các chương trình con khác Được gọi từ nhiều vị trí khác nhau Khi nào thì cần thiết phải sử dụng chương trình con: Khi chương trình lặp đi lặp lại các đoạn lệnh tương tự nhau. Lợi ích của việc sử dụng chương trình con IV. Dặn dò Học bài cũ và đọc trước mục 2.Phân loại và cấu trúc của chương trình con V. Rút kinh nghiệm Nhận xét của giáo viên hướng dẫn Ngày tháng năm 2008 Giáo viên hướng dẫ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 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.

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 [[:[;: ]]]: ;	[Header]
[VAR :[;: ]]	Khai báo các biến cục bộ nếu có.
BEGIN 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];

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.

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

PROCEDURE [:[;: ]]: ;	[Header]
[VAR :[;: ]	Khai báo các biến cục bộ nếu có.
BEGIN 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 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 đó.

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ố.
• - 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.

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:

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

Đố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.

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 ‘,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.