CHƯƠNG TRÌNH CON VÀ ÐƠN VỊ CHƯƠNG TRÌNHI. KHÁI NIỆM VỀ CHƯƠNG TRÌNH CONKhi lập trình, chúng ta thường có những đoạn chương trình hay phép tính lặp lại nhiều lần. Nếu mỗi lần lặp lại, ta phải viết những đoạn lệnh như nhau thì chương trình của chúng ta trở nên dài dòng,rối rắm và mất thời gian vơ ích. Ðể giải quyết những trường hợp như vậy, Pascal cho phép chúng ta tạo ra các module, mỗi module mang một đoạn chương trình gọi là chương trình con subroutine haysubprogram. Mỗi chương trình con sẽ mang một cái tên khác nhau. Một module chỉ cần viết một lần và sau đó chúng ta có thể truy xuất nó nhiều lần, bất kỳ nơi nào trong chương trình chính. Khi cầnthiết, chúng ta chỉ việc gọi tên chương trình con đó ra để thi hành lệnh.Nhờ sử dụng chương trình con, chương trình có thể tiết kiệm được ơ nhớ. Ðồng thời, ta có thể kiểm tra tính logic trong tiến trình lập trình cho máy tính điện tử, có thể nhanh chóng loại bỏ nhữngsai sót khi cần hiệu chỉnh hay cải tiến chương trình. Ðây là khái niệm cơ bản trong ý tưởng lập chương trình có cấu trúc. Một q trình tính cũng có thể có nhiều chương trình con lồng ghép vàonhau.Trong Pascal, chương trình con được viết dưới dạng thủ tục procedure và hàm function. Cấu trúc của 2 kiểu chương trình con này thì tương tự với nhau, mặc dầu cách truy xuất của chúng cókhác nhau và cách trao đổi thơng tin trong mỗi kiểu cũng có điểm khác nhau. Hàm function trả lại một giá trị kết quả vô hướng thông qua tên hàm và hàm được sử dụng trong biểu thức.Ví dụ hàm chuẩn, như hàm sinx mà chúng ta đã biết trong chương trước có thể được xem như một chương trình con kiểu function với tên là sin và tham số là x. Trong khi đó, thủ tụcprocedure không trả lại kết quả thông qua tên của nó, do vậy, ta khơng thể viết các thủ tục trong biểu thức. Các lệnh Writeln, Readln trong chương trước được xem như các thủ tục chuẩn.Một chương trình có chương trình con tự thiết lập có 3 khối block : Khối khai báoKhối chương trình con Khối chương trình chínhII . THỦ TỤC VÀ HÀM Một số khái niệm biến:· Biến tồn cục global variable: Còn được gọi là biến chung, là biến được khai báo ở đầu chương trình, nó được sử dụng bên trong chương trình chính và cả bên trong chương trình con. Biến tồn cụcsẽ tồn tại trong suốt quá trình thực hiện chương trình. · Biến cục bộ local variable: Còn được gọi là biến riêng, là biến được khai báo ở đầu chươngtrình con, và nó chỉ được sử dụng bên trong thân chương trình con hoặc bên trong thân chương trình con khác nằm bên trong nó các chương trình con lồng nhau. Biến cục bộ chỉ tồn tại khi chươngtrình con đang hoạt động, nghĩa là biến cục bộ sẽ được cấp phát bộ nhớ khi chương trình con được gọi để thi hành, và nó sẽ được giải phóng ngay sau khi chương trình con kết thúc.· Tham số thực actual parameter là một tham số mà nó có thể là một biến tồn cục, một biểu thức hoặc một giá trị số cũng có thể biến cục bộ khi sử dụng chương trình con lồng nhau mà ta dùngchúng khi truyền giá trị cho các tham số hình thức tương ứng của chương trình con. · Tham số hình thức formal parameter là các biến được khai báo ngay sau Tên chương trình con,nó dùng để nhận giá trị của các tham số thực truyền đến. Tham số hình thức cũng là một biến cục bộ, ta có thể xem nó như là các đối số của hàm tốn học.Lời gọi chương trình con thủ tục và hàm:Ðể chương rrình con được thi hành, ta phải có lời gọi đến chương trình con, lời gọi chương trình con thơng qua tên chương trình con và danh sách các tham số tương ứng nếu có. Các qui tắccủa lời gọi chương trình con: · Trong thân chương trình chính hoặc thân chương trình con, ta chỉ có thể gọi tới các chương trìnhcon trực thuộc nó. · Trong chương trình con, ta có thể gọi các chương trình con ngang cấp đã được thiết lập trước đó.
1. Thủ tục Procedure
Thủ tục là một đoạn cấu trúc chương trình được chứa bên trong chương trình Pascal như là một chương trình con. Thủ tục được đặt tên và có thể chứa danh sách tham số hình thức formalparameters. Các tham số này phải được đặt trong dấu ngoặc đơn . Ta có thể truy xuất thủ tục bằng 13Có 2 loại thủ tục: + thủ tục không tham số+ và thủ tục có tham số. a. Cấu trúc của thủ tục không tham sốPROCEDURE Tên thủ tục ; { Các khai báo hằng, biến, kiểu cục bộ... }BEGIN { ... các lệnh trong nội bộ thủ tục ... }END ; Ví dụ 7.1:Tìm số lớn nhất trong 3 trị số nguyên PROGRAM Largest ; Xác định số lớn nhất trong 3 trị số nguyên được nhập vàoVAR a, b, c : integer ; yn : char ;PROCEDURE maximum ; VAR max : integer ;BEGIN IF a b THEN max := a ELSE max := b ;IF c max THEN max := c ; Writeln Số lớn nhất là , max ;END ; BEGINÐoạn chương trình chính yn := ‘Y‘ ;WHILE upcaseyn = ‘Y ‘ DO BEGINWriteln Nhập 3 số nguyên : ; Readln a, b, c ;maximum ; --- Lời gọi thủ tục maximum --- Write Tiếp tục nhập 3 số mới không yn ? ;Readln yn ; END ;END. Chú ý:Trong chương trình trên, thủ tục maximum được khai báo trước khi nó được truy xuất, các biến a, b, c được gọi nhập vào ở chương trình chính và biến max được định nghĩa bên trong thủ tục.Ðiều này cho ta thấy, không phải lúc nào cũng cần thiết khai báo biến ngay đầu chương trình chính. b. Cấu trúc của thủ tục có tham sốPROCEDURE Tên thủ tục danh sách tham số hình thức : kiểu biến; { Các khai báo hằng, biến, kiểu cục bộ ... }BEGIN { ... các lệnh trong nội bộ thủ tục ... }END ; Khi viết một thủ tục, nếu có các tham số cần thiết, ta phải khai báo nó kiểu, số lượng, tínhchất, .... Các tham số này gọi là tham số hình thức formal parameters. Một thủ tục có thể có 1 hoặc nhiều tham số hình thức. Khi các tham số hình thức có cùng mộtkiểu thì ta viết chúng cách nhau bởi dấu phẩy ,. Trường hợp các kiểu của chúng khác nhau hoặc giữa khai báo tham số truyền bằng tham biến và truyền bằng tham trị sẽ học ở phần sau thì ta phảiviết cách nhau bằng dấu chấm phẩy ;. Ví dụ 7.2: Tính giai thừa của một sốPROGRAM Tinh_Giai_thua ; VARn : integer ; gt : real ; {các biến chung} PROCEDURE giaithua m : integer ;14BEGIN gt := 1 ;FOR i := 1 TO m DO gt := gt i ; END ;BEGIN Thân chương trình chínhWriteNhập số ngun n 0 = n 33 = ;Readln n ; If n=0 thenBegin giaithua n ;Writeln Giai thừa của , n, là : , gt: 10 : 0 ; EndElse Writeln Khơng tính giai thừa của một số âm ;Readln; END.Trong chương trình trên m là các tham số hình thức của thủ tục giaithua. Khi gọi thủ tục giaithua n thì tham số thực n được truyền tương ứng cho tham số hình thứcm. Ví dụ 7.3: Giải phương trình ax2 + bx + c = 0, theo dạng chương trình con lồng nhau:PROGRAM Giai_PTB2; VAR hsa, hsb, hsc:real; {các biến toàn cục}PROCEDURE Ptb2a,b,c:real; {a, b, c là các tham số hình thức của Ptb2} Var delta:real; {biến cục bộ}PROCEDURE Ptb1a1,b1:real; {a,b là các tham số hình thức của Ptb1} Beginif a1=0 thenif b1=0 then writelnPhương trình vơ số nghiệmelse writelnPhương trình vơ nghiệmelse writelnPhương trình có nghiệm =,-b1a1:8:2;End; {kết thúc thủ tục Ptb1} Begin {bắt đầu thủ tục Ptb2}3 if a=0 then ptb1b,c {b, c là các tham số thực cho Ptb1}4 elsebegin delta:=sqrb-4ac;if delta0 then beginwritelnNghiệm x1= ,-b+sqrtdelta2a:8:2; writelnNghiệm x2= ,-b-sqrtdelta2a:8:2;end elseif delta=0 then writelnNghiệm kép x1=x2= ,-b2a:8:2else writelndelta 0 = Phương trình vơ nghiệm;end; End; {kết thúc thủ tục Ptb2}Begin {chương trình chính} 1 writeNhập các hệ số a, b, c = ;readlnhsa, hsb, hsc;2 Ptb2hsa,hsb,hsc; {hsa, hsb, hsc là các tham số thực cho Ptb2} 5 readln;End. {kết thúc chương trình}15cho các tham số hình thức a, b, c tương ứng trong thủ tục Ptb2. Nếu ta lại xét đến thủ tục con của thủ tục Ptb2 là Ptb1 thì các tham số a, b, c này chính xác làb và c lại là tham số thực đối với Ptb1, với b và c được truyền tương ứng cho các tham số hình thức a, b của thủ tục Ptb1.Như vậy ta nhận thấy rằng, vấn đề xác định được đâu là biến toàn cục, đâu là biến cục bộ, đâu là tham số thực và đâu là tham số hình thức tham số biến và tham số trị là ứng bước nào mà chươngtrình đang thực hiện? Ðây là phần then chốt để nắm được cách vận hành và kết quả của chương trình xử lý.Sơ đồ minh họa cách vận hành và quản lý biến của chương trình:
Chương 4CHƯƠNG TRÌNH CON: THỦ TỤC VÀ HÀMI. KHÁI NIỆM VỀ CHƯƠNG TRÌNH CONChương trình con [CTC] là một đoạn chương trình thực hiện trọn vẹn hay một chứcnăng nào đó. Trong Turbo Pascal, có 2 dạng CTC:• Thủ tục [PROCEDURE]: Dùng để thực hiện một hay nhiều nhiệm vụ nào đó.• Hàm [FUNCTION]: Trả về một giá trị nào đó [có kiểu vô hướng, kiểu string hoặckiểu con trỏ]. Hàm có thể sử dụng trong các biểu thức.Ngoài ra, trong Pascal còn cho phép các CTC lồng vào nhau.II. CẤU TRÚC CHUNG CỦA MỘT CHƯƠNG TRÌNH CÓ SỬ DỤNG CTCPROGRAM Tên_chương_trình;USES CRT;CONST ............;TYPE ............;VAR ............;PROCEDURE THUTUC[[Các tham số]];[Khai báo Const, Type, Var]BEGIN..............END;FUNCTION HAM[[Các tham số]]:;[Khai báo Const, Type, Var]BEGIN..............HAM:=;END;BEGIN {Chương trình chính}...................THUTUC[[...]];...................A:= HAM[[...]];...................END.Chú ý: Trong quá trình xây dựng CTC, khi nào thì nên dùng thủ tục/hàm?Dùng hàmDùng thủ tục- Kết quả của bài toán trả về 1 giá trị duynhất [kiểu vô hướng, kiểu string hoặckiểu con trỏ].- Lời gọi CTC cần nằm trong các biểu thứctính toán.- Kết quả của bài toán không trả về giá trịnào hoặc trả về nhiều giá trị hoặc trả vềkiểu dữ liệu có cấu trúc [Array, Record,File].- Lời gọi CTC không nằm trong các biểuthức tính toán.Ví dụ 1: Viết CTC để tính n! = 1.2...n.Ý tưởng: Vì bài toán này trả về 1 giá trị duy nhất nên ta dùng hàm.Function GiaiThua[n:Word]:Word;Var P, i:Word;BeginP:=1;For i:=1 To n Do P:=P*i;GiaiThua:=P;End;Ví dụ 2: Viết chương trình con để tìm điểm đối xứng của điểm [x,y] qua gốc tọa độ.Ý tưởng: Vì bài toán này trả về tọa độ điểm đối xứng [xx,yy] gồm 2 giá trị nên ta dùng thủtục.Procedure DoiXung[x,y:Integer; Var xx,yy:Integer];Beginxx:=-x;yy:=-y;End;CHÚ Ý: Trong 2 ví dụ trên:• n, x, y được gọi là tham trị [không có từ khóa var đứng trước] vì sau khi ra khỏiCTC giá trị của nó không bị thay đổi.• xx, yy được gọi là tham biến [có từ khóa var đứng trước] vì sau khi ra khỏi CTCgiá trị của nó bị thay đổi.III. BIẾN TOÀN CỤC VÀ BIẾN ĐỊA PHƯƠNG• Biến toàn cục: là các biến được khai báo trong chương trình chính. Các biến nàycó tác dụng ở mọi nơi trong toàn bộ chương trình.• Biến địa phương: là các biến được khai báo trong các CTC. Các biến này chỉ cótác dụng trong phạm vi CTC đó mà thôi.Chú ý: Trong một CTC, nếu biến toàn cục trùng tên với biến địa phương thì biếnđịa phương được ưu tiên hơn.Ví dụ:Program KhaoSatBien;Var a,b: Integer; {biến toàn cục}Procedure ThuBien;Var a: Integer; {biến địa phương}Begina:=10;Writeln[‘A=’,a,’B=’,b];End;Begina:=50;b:=200;ThuBien; {A=10 B=200}Writeln[‘A=’,a,’B=’,b]; {A=50 B=200}End. IV. ĐỆ QUI4.1. Khái niệm đệ quiTrong một chương trình, một CTC có thể gọi một CTC khác vào làm việc. Nếu nhưCTC đó gọi lại chính nó thì gọi là sự đệ qui.4.2. Phương pháp thiết kế giải thuật đệ qui• Tham số hóa bài toán• Tìm trường hợp suy biến.• Phân tích các trường hợp chung [đưa về các bài toán cùng loại nhưng nhỏ hơn].Ví dụ: Viết hàm đệ qui để tính n! = 1.2...n.• Tham số hóa: n! = Factorial[n];• Factorial[0] = 1 [trường hợpsuy biến]• Factorial[n] = n*Factorial[n-1] [trường hợp chung]Function Factorial[N:integer]:Longint;BeginIf N=0 Then Factorial:=1Else Factorial:=N*factorial[N-1]; { lời gọi đệ qui }End;4.3. Giải thuật quay luiBài toán:Hãy xây dựng các bộ giá trị gồm n thành phần [x1,...,xn] từ một tập hữu hạncho trước sao cho các bộ đó thỏa mãn yêu cầu B cho trước nào đó.Phương pháp chungGiả sử đã xác định được k-1 phần tử đầu tiên của dãy: x1,...,xk-1. Ta cần xácđịnh phần tử thứ k. Phần tử này được xác định theo cách sau:- Giả sử Tk: tập tất cả các giá trị mà phần tử xk có thể nhận được. Vì tập Tkhữu hạn nên ta có thể đặt nk là số phần tử của Tk theo một thứ tự nào đó, tức là ta cóthể thành lập một ánh xạ 1-1 từ tập Tk lên tập {1, 2, ..., nk}.- Xét j∈{1, 2, ..., nk}. Ta nói rằng “j chấp nhận được” nếu ta có thể bổ sungphần tử thứ j trong Tk với tư cách là phần tử xk vào trong dãy x1,...,xk-1 để được dãyx1,...,xk.- Nếu k=n: Bộ [x1,...,xk] thỏa mãn yêu cầu B, do đó bộ này được thu nhận.- Nếu k