Lập trình pascal - Chương 1: Thuật giải và chương trình

LẬP TRÌNH PASCALLỚP: CĐ CK 2011Chương 1: Thuật giải và chương trình1.Thuật giải (algorithm) Là một tập hữu hạn các thao tác (các công việc, các phép toán) có thể đặt tên được và được thực hiện theo một trình tự thích hợp trên một số đối tượng để đạt được mục đích mong muốn. "Hữu hạn" ở đây được hiểu cả về mặt thời gian thực hiện lẫn công cụ thực hiện.Khái niệm+ Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn bước.+ Tính xác định: Các thao tác ở mỗi bước phải hết sức rõ ràng và chỉ được hiểu theo một nghĩa duy nhất. Trong cùng một điều kiện hai máy khác nhau hoặc hai lần thao tác khác nhau phải cho cùng một kết quả khi thực hiện cùng một thuật toán.+ Tính hàng loạt: Thuật toán có hiệu lực như nhau đối với các bài toán cùng loại (có cùng miền áp dụng thuật toán).+ Tính khả thi: Thuật toán phải bao gồm các thao tác mà máy có thể thực hiện được (chỉ bao gồm những phép toán số học, các phép so sánh, các phép logic, các phép nhập xuất thông tin tiêu chuẩn).+ Tính đầy đủ: Thuật toán phải vét được hết các tình huống, các khả năng có thể xảy ra, không bỏ sót bất kỳ một trường hợp nào.II. CÁC ĐẶC TRƯNG CỦA THUẬT TOÁNIII. CÁC DẠNG DIỄN TẢ THUẬT TOÁN1. Diễn đạt bằng văn bản (ngôn ngữ tự nhiên)-Khá đơn giản; gần gũi với tư duy của con người nhưng phụ thuộc rất nhiều vào cách diễn đạt của người sử dụng. Vì vậy nó không tránh khỏi có những chỗ rườm rà khiến cho người đọc không có được một cái nhìn khái quát với toàn bộ thuật toán.2. Diễn đạt bằng ngôn ngữ lập trìnhNgôn ngữ lập trình (language program) là ngôn ngữ do các chuyên gia tin học tạo ra chuyên dùng để viết chương trình cho máy tính. Nó được xây dựng khá đơn giản về chính tả và ngữ pháp khá gần gũi với ngôn ngữ khoa học kỹ thuật, quản lý.III. CÁC DẠNG DIỄN TẢ THUẬT TOÁN3. Diễn đạt bằng lưu đồĐiểm bắt đầu và chấm dứt thuật toánThao tác nhập hay xuất dữ liệu Khối xử lý công việc Khối quyết định lựa chọn Điểm nối Chuẩn bị Khối chương trình con Đường đi của chương trìnhBước 1: Nhập vào 2 hệ số a và b. Bước 2: Xét điều kiện a = 0 ? Nếu đúng là a = 0, thì đi đến bước 3. Nếu không, nghĩa là a ≠ 0, thì đi đến bước 4. Bước 3: Xét điều kiện b = 0 ? Nếu b = 0, thì báo phương trình có vô số nghiệm. Chuyển đến bước 5. Nếu b  0, thông báo phương trình vô nghiệm. Chuyển đến bước 5. Bước 4: PT có một nghiệm duy nhất là x = - b/a. Bước 5: Kết thúc thuật toán III. CÁC DẠNG DIỄN TẢ THUẬT TOÁNBằng văn bảnVí dụ 2: Thuật toán giải phương trình bậc nhất ax + b = 0 Bằng Lưu ĐồVí dụ 3 : Tính tổng S của n số nguyên đầu tiên, ta tiến hành theo hai thuật giải sauVí dụ 4: Thuật giải đổi chỗViết thuật giải để nhập vào 2 số A, B từ bàn phím sau đó đổi giá trị của biến A cho biến B và ngược lại.Ví dụ 5: Thuật giải tìm số lớn nhất trong 2 sốBÀI TẬP1. Viết thuật giải nhập 1 số từ bàn phím và in ra bình phương của số đó nếu số đó là số dương.2.Viết thuật giải nhập từ bàn phím một số tự nhiên N và in ra các số nguyên trong phạm vi từ 1 đến N3. Viết thuật giải nhập từ bàn phím 2 số tự nhiên m, n (mn UCLn(m,n-m) với n>m BCNN(m,n)=m*n/UCLN(m,n)CHƯƠNG 2: CÁC KHÁI NIỆM CƠ BẢN CỦA NGÔN NGỮ LẬP TRÌNH PASCAL I. GIỚI THIỆUPascal là ngôn ngữ lập trình cấp cao do giáo sư Niklaus Writh (trường ĐH kỹ thuật Zurich, Thuỵ sỹ) sáng tác và công bố vào đầu những năm 1970. Nó giúp cho sinh viên cũng như người mới học lập trình có được thói quen viết một chương trình có cấu trúc sáng sủa, rõ ràng dễ đọc và dễ hiểu.Pascal là một ngôn ngữ có định kiểu mạnh mẽ. Có nghĩa một biến và một hằng của một kiểu dữ liệu không thể tự do đem trộn lẫn với biến và hằng của một kiểu dữ liệu khác. Khi sử dụng phải khai báo rõ kiểu của chúng. Các kiểu dữ liệu trong Pascal hết sức phong phú thể hiện được nhiều kiểu dữ liệu từ đơn giản đến phức tạp. Pascal là một ngôn ngữ có cấu trúc. Một ngôn ngữ có cấu trúc khối là một ngôn ngữ mà ta có thể tách các thông tin dữ liệu (biến, hằng,..) và các lệnh cần dùng cho một nhiệm vụ xác định thành những khối riêng để người lập trình có thể giải quyết dần dần từng khối một hoặc cho nhiều người cùng tham gia lập trình. Ưu điểm của PascalTính cấu trúc của Pascal được thể hiện trên 3 mặt: Cấu trúc về mặt dữ liệu: từ các dữ liệu kiểu đơn giản hoặc lệnh có cấu trúc ta có thể xây dựng các dữ liệu có cấu trúc phức tạp hơn Cấu trúc về mặt lệnh: từ các lệnh đơn giản hoặc lệnh có cấu trúc ta có thể xây dựng các lệnh phức tạp hơn. Cấu trúc về mặt chương trình: một chương trình có thể chia thành những đơn thể (modul) tương đối độc lập và những chương trình con.Ưu điểm của PascalII. CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL  2.1. Bộ ký tự Ngôn ngữ Pascal được xây dựng từ bộ ký hiệu cơ bản sau:Bộ 26 chữ cái La tinh: 26 chữ cái thường a, b, c, ... , z 26 chữ cái hoa: A,B,C,... Z Bộ 10 chữ số thập phân: 0, 1, ... , 9Bộ dấu các phép toán: cộng + trừ - nhân * chia / luỹ thừa ^ bằng = lớn hơn > nhỏ hơn mở ngoặc ( đóng ngoặc )Bộ các ký hiệu đặc biệt: dấu gạch dưới _ dấu chấm . dấu chấm phẩy ; dấu nháy đơn ' các ký hiệu khác như [] $ ...Dấu cách (space) được dùng để ngăn cách các từ. 2.2. Từ khoáLà các từ riêng của Pascal, có ngữ nghĩa đã được xác định, không được dùng nó vào các việc khác hoặc đặt tên mới trùng với các từ khóa. Từ khóa chung: PROGRAM, BEGIN, END, PROCEDURE, FUNCTION  Từ khóa để khai báo: CONST, VAR, TYPE, ARRAY, STRING, RECORD, SET, FILE, LABEL Từ khóa của lệnh lựa chọn: IF ... THEN ... ELSE, CASE ... OF  Từ khóa của lệnh lặp: FOR... TO... DO, FOR... DOWNTO... DO,  WHILE... DO, REPEAT... UNTIL  Từ khóa điều khiển: WITH, GOTO, EXIT, HALT  Từ khóa toán tử: AND, OR, NOT, IN, DIV, MOD2.3. Tên chuẩnTên chuẩn là tên đã được định nghĩa sẵn trong Pascal, nhưng người ta có thể định nghĩa lại nếu muốn. Trong Pascal ta có các tên chuẩn sau đây:  Boolean, Char, Integer, Word, Byte, Real, Text False, True, MaxInt Abs, Chr, Cos, Sin, Eof, Eoln Exp, Ln, Odd, Ord Round, Trunc, Sqr, Pred, Succ Dispose, New, Get, Put, Read, Readln, Write, Writeln, Reset, Rewrite 2.4. Tên hay định danh Là một dãy ký tự do người sử dụng tự đặt cho các hằng, biến, hàm, thủ tục, tên chương trình, tên kiểu dữ liệu mới. Tên hay định danh trong Pascal phải tuân thủ các qui định sau:Tên phải được bắt đầu bằng một chữ cái hoặc chữ số.Trong tên không chứa dấu cáchTên không được trùng với một từ khoá của Pascal Số ký tự của tên bị hạn chế là 8 (Pascal chuẩn), 127 (Turbo Pascal)Ví dụ: Các tên viết như sau: #DLTA sai vì tên bắt đầu bằng một ký tự đặc biệt ARRAY sai vì tên trùng với từ khoá VI DU sai vì tên có dấu cáchChú ý: Để làm cho tên được sáng sủa người ta cho phép dùng dấu gạch dưới (_) khi viết tên. Ví dụ: GIAI_PHUONG_TRINHCác từ trong Pascal có thể viết hoa hoặc viết thường mà giá trị và ý nghĩa của chúng không thay đổi.CẤU TRÚC CỦA MỘT CHƯƠNG TRÌNH PASCALProgram Tên_Chương_Trình;{Phần khai báo}Uses Label Const Type Var {Phần chương trình con}ProcedureFunction{Chương trình chính}Begin{Các lệnh của chương trình chính}End.Một chương trình Pascal có các phần: * Phần tiêu đề: Phần này bắt đầu bằng từ khóa Program rồi tiếp đến là tên của chương trình và chấm dứt bằng dấu chấm phẩy (;)Tên chương trình phải được đặt theo đúng qui cách của danh hiệu tự đặt. Phần tiêu đề có hoặc không.  * Phần khai báo dữ liệu: Một chương trình Pascal có thể có một số hoặc tất cả các khai báo dữ liệu sau: USES : khai báo các thư viện chương trình CONST : khai báo hằng TYPE : định nghĩa kiểu dữ liệu mới VAR : khai báo các biến Phần khai báo CT con (có thể có hoặc không tùy theo nhu cầu).* Phần thân chương trình: Phần thân chương trình là phần quan trọng nhất và bắt buộc phải có, phần này luôn nằm giữa 2 từ khoá là BEGIN và END. ở giữa là lệnh mà các chương trình chính cần thực hiện. Sau từ khóa END là dấu chấm (.) để báo kết thúc chương trình.  CẤU TRÚC CỦA MỘT CHƯƠNG TRÌNH PASCAL* Dấu chấm phẩy (;): Dấu ; dùng để ngăn cách các câu lệnh của Pascal và không thể thiếu được.  * Lời chú thích: Lời chú thích dùng để chú giải cho người sử dụng chương trình nhớ nhằm trao đổi thông tin giữa người và người, máy tính sẽ không để ý đến lời chú thích này. Lời chú thích nằm giữa ký hiệu: { } hoặc (* *)  CẤU TRÚC CỦA MỘT CHƯƠNG TRÌNH PASCALVí dụ: Viết chương trình tính diện tích hình tròn biết bán kính là R , tính diện tích hình vuông biết cạnh là a.PROGRAM VI_DU; (* Dòng tiêu đề *) VAR R, A, Dientich: Real; (* Khai báo ba biến thực *)BEGIN Write ('Ban kinh : R= '); Readln (R); Dientich:=3.14*R*R; (* Tính diện tích hình tròn *) Writeln (‘Dien tich hinh tron la:', Dientich:10:3); Write ('Do dai canh hinh vuong: A= '); Readln (A); Dientich:=A*A; Writeln (‘Dien tich hinh vuong la’, Dientich:10:3); Readln;END.CẤU TRÚC CỦA MỘT CHƯƠNG TRÌNH PASCAL5.1. Khái niệmDữ liệu (DATA) được định nghĩa là tất cả những gì được máy tính xử lý. Các kiểu dữ liệu cần tới máy tính xử lý có rất nhiều, tồn tại dưới nhiều dạng khác nhau về bản chất, ý nghĩa, không chỉ là số liệu mà còn là các kí tự, các mệnh đề logic thể hiện qua các đối tượng cụ thể cần xử lý như tiền lương, địa chỉ, tên, tuổi, văn bản, tín hiệu. Về phương diện ngôn ngữ bậc cao thì dữ liệu đã được khái quát hoá với các kiểu dữ liệu. Một kiểu dữ liệu (Data Type) được định nghĩa với hai điểm chính như sau:- Một tập hợp các giá trị mà một biến thuộc kiểu đó có thể nhận được- Trên đó xác định một số phép toán.V. CÁC KIỂU DỮ LIỆU CƠ SỞ Một biến phải gắn liền với một kiểu dữ liệu. Các kiểu DL trong PascalKiểu dữ liệu đơn giảnKiểu số nguyên(Integer)Kiểu số thực(Real)Kiểu ký tự(Char)Kiểu logic(Boolean)Kiểu dữ liệu có cấu trúcKiểu mảng(Array)Kiểu chuỗi(String)Kiểu tập hợp(Set)Kiểu bản ghi(Record)Kiểu tập tin(File,Text)5.2. Kiểu số nguyên (Integer type)a. Kiểu số nguyên trong Turbo Pascal : Được định nghĩa với các từ khóa sau:  V. CÁC KIỂU DỮ LIỆU CƠ SỞ b. Các phép toán số học đối với số nguyên  5.3. Kiểu số thực (Real type)Có năm kiểu số thực được tổng kết qua bảng sau:Các giá trị thực được biểu diễn theo hai cách: dạng dấu phẩy tĩnh và dạng dấu phẩy động.Dạng dấu phẩy tĩnh: viết dạng thập phân bình thường. Ví dụ: 2.14, +5.0, -25.345678, 0.0006Dạng dấu phẩy động: số được tách thành hai phần là định trị và bậc. Phần định trị là một số nguyên hay số thực viết dưới dạng dấu phẩy tĩnh. Phần bậc là một số nguyên.Hai phần cách nhau bởi chữ E hay e. Ví dụ: 123.456E-4: biểu diễn số 0.0123456 0.15E+5: biểu diễn số 15000.0 5E8: biểu diễn 500000000.0 -55.3e2: biểu diễn -5530.0Các ký tự biểu diễn một số thực phải viết liền nhau.Các phép toán số học cơ bản +, -, * , / được sử dụng trong kiểu real.Chú ý: Riêng phép toán DIV và MOD không thực hiện đối với kiểu số thực   5.4. Kiểu logic (Boolean) Một dữ liệu thuộc kiểu BOOLEAN là một đại lượng được chứa trong 1 byte ở Turbo Pascal và chỉ có thể nhận được một trong hai giá trị logic là TRUE (đúng) và FALSE (sai). Qui ước: TRUE > FALSE  Các phép toán trên kiểu Boolean:  Các phép toán quan hệ cho kết quả kiểu Boolean:  5.5. Kiểu ký tự (Char type) Tất cả các dữ liệu viết ở dạng chữ ký tự được khai báo bởi từ khóa CHAR.  Một ký tự được viết trong hai dấu nháy đơn ‘ ‘. Để tiện trao đổi thông tin cần phải sắp xếp, đánh số các ký tự, mỗi cách sắp xếp như vậy gọi là bảng mã. Bảng mã thông dụng hiện nay là bảng mã ASCII .Để thực hiện các phép toán số học và so sánh, ta dựa vào giá trị số thứ tự mã ASCII của từng ký tự, chẳng hạn: 'A' ’B  TRUE‘B’ = ;  Ví dụ CONST Siso = 100; X = ‘xxx ‘;  VI. KHAI BÁO BIẾN, HẰNG, KIỂU VÀ BIỂU THỨC6.2. Biến (variable) a. Định nghĩa Biến là một đại lượng mà giá trị của nó có thể thay đổi nhiều lần trong chương trình. Tên biến là tên của ô nhớ cất giữ dữ liệu  Ví dụ : Readln (x) ; Writeln (x) ; x := 9 ;  Biến là một cấu trúc ghi nhớ dữ liệu vì vậy nó phải tuân theo qui định của kiểu dữ liệu : một biến phải thuộc một kiểu dữ liệu nhất định.  b. Cách khai báo  VAR : ;   Ví dụ : VAR a : Real ; b, c : Integer ; TEN : String [20]; X : Boolean ; Chon : Char ;  Cần khai báo các biến trước khi sử dụng chúng trong chương trình. Khai báo một biến là khai báo sự tồn tại của biến đó và cho biết nó thuộc kiểu gì.VI. KHAI BÁO BIẾN, HẰNG, KIỂU VÀ BIỂU THỨC6.3. Kiểu (Type) a. Định nghĩa Ngoài các kiểu đã định sẵn, Pascal còn cho phép ta định nghĩa các kiểu dữ liệu khác từ các kiểu căn bản theo qui tắc xây dựng của Pascal.   b. Cách khai báo TYPE = ;  Ví dụ : TYPE SoNguyen = Integer ; Diem = Real; Tuoi = 1 .. 100 ; Color = (Red, Blue, Green) ; Thu = (Sun, Mon, Tue, Wed, Thu, Fri, Sat) ; khi đã khai báo kiểu gì thì ta có quyền sử dụng để khai báo biến như ở ví dụ sau:  Ví dụ : VAR i, j : SoNguyen ; Dtb : Diem ; T : tuoi ; Mau : Color ; Ngay_hoc : Thu; VI. KHAI BÁO BIẾN, HẰNG, KIỂU VÀ BIỂU THỨC6.4. Biểu thức (Expression) a. Định nghĩa Một biểu thức là một công thức tính toán bao gồm các phép toán, hằng, biến, hàm và các dấu ngoặc.  Ví dụ : 5 + A * SQRT(B) / SIN(X) (A AND B) OR C b. Thứ tự ưu tiên Khi tính giá trị của một biểu thức, ngôn ngữ Pascal qui ước thứ tự ưu tiên của các phép toán từ cao đến thấp như sau:  Mức ưu tiên: Các phép toán: 1. Biểu thức trong ngoặc đơn ( ) 2. Phép gọi hàm 3. Not, - 4. *, /, DIV, MOD, AND 5. +, -, OR, XOR 6. =, , =, , IN  VD: (4+5)/3 + 6 - (sin((/2)+3)*2 = (9)/3 + 6 - (1+3)*2 = 3 + 6 - 8 = 1 VI. KHAI BÁO BIẾN, HẰNG, KIỂU VÀ BIỂU THỨC6.4. Biểu thức (Expression) c. Qui ước tính thứ tự ưu tiên Khi tính một biểu thức có 3 qui tắc về thứ tự ưu tiên như sau:  Qui tắc 1 : Các phép toán nào có ưu tiên cao hơn sẽ được tính trước. Qui tắc 2 : Trong các phép toán có cùng thứ tự ưu tiên thì sự tính toán sẽ được thực hiện từ trái sang phải. Qui tắc 3 : Phần trong ngoặc từ trong ra ngoài được tính toán để trở thành một giá trị đơn. d. Kiểu của biểu thức Là kiểu của kết quả sau khi tính biểu thức.  Ví dụ : Biểu thức sau được gọi là biểu thức Boolean: not (('a'>'c') and ('c'>'C')) or ('B'='b') có giá trị TRUE VI. KHAI BÁO BIẾN, HẰNG, KIỂU VÀ BIỂU THỨC7.1.Câu lệnh (statement)+ Trong một chương trình Pascal, sau phần mô tả dữ liệu là phần mô tả các câu lệnh. Các câu lệnh có nhiệm vụ xác định các công việc mà máy tính phải thực hiện để xử lý các dữ liệu đã được mô tả và khai báo.  + Câu lệnh được chia thành câu lệnh đơn giản và câu lệnh có cấu trúc. - Câu lệnh đơn giản + Vào dữ liệu : Read, Readln + Ra dữ liệu : Write, Writeln + Lệnh gán : := + Lời gọi chương trình con (gọi trực tiếp tên của chương trình con) + Xử lý tập tin : RESET, REWRITE, ASSIGN ... VII. CÁC THỦ TỤC NHẬP/XUẤT7.1.Câu lệnh (statement)+ - Câu lệnh có cấu trúc + Lệnh ghép : BEGIN .. END + Lệnh chọn : IF .. THEN .. ELSE CASE .. OF . + Lệnh lặp : FOR .. TO .. DO REPEAT .. UNTIL WHILE .. DO + Các câu lệnh phải được ngăn cách với nhau bởi dấu chấm phẩy ( ; ) và các câu lệnh có thể viết trên một dòng hay nhiều dòng.VII. CÁC THỦ TỤC NHẬP/XUẤT424. Khai báo, biểu thức, câu lệnh4.5 Câu lệnh ghépCác câu lệnh đơn được đặt giữa BEGIN và END sẽ tạo thành một câu lệnh ghép.Cách sử dụngBegin End;If (a 0) thenBegin write(‘nghiệm=’ ); write(-b/a);End;435. Các thủ tục nhập xuất dữ liệu5.1 Nhập dữ liệu từ bàn phímCách viếtÝ nghĩaRead(X1, X2, , Xn)Readln(X1, X2, , Xn)Nhập dữ liệu từ bàn phím vào các biến X1,X2,..,XnReadln;Dừng chương trình, đợi phím EnterBegin readln(s); read(a,b); readln; End.445. Các thủ tục nhập xuất dữ liệu5.2 Xuất dữ liệu ra màn hìnhCách viếtÝ nghĩawrite([‘thông báo’],X1, X2, , Xn)writeln([‘thông báo’],X1, X2, , Xn)Xuất thông báo và giá trị ra màn hình.Writeln;Chèn thêm dòng trống.Ví dụWrite(‘diem’,diem, ‘hocbong’,200);Writeln;Writeln(‘chu vi=’,(dai+rong)*2);Writeln(‘ket thuc chuong trinh’);7.2. Cấu trúc tuần tựa. Lệnh gán (Assignment statement) Một trong các lệnh đơn giản và cơ bản nhất của Pascal là lệnh gán. Mục đích của lệnh này là gán cho một biến đã khai báo một giá trị nào đó cùng kiểu với biến.  Cách viết: := ;  Ví dụ : VAR c : Char ; i,j : Integer ; x, y : Real ; p, q : Boolean ;  thì ta có thể có các phép gán sau : c := ‘A’ ; c := Chr(90) ; i := (35+7)*2 mod 4 ; i := i div 7 ; x := 0.5 ; q := i > 2*j +1 ; q := not p ;  VII. CÁC THỦ TỤC NHẬP/XUẤT BÀI TẬP1. Tính giá trị của các biểu thức dưới đây: (‘d’>‘g’) and (18 div 4 * 4 >125) = (True<False) or (‘a’ <‘c’) = round(-72.315)=2. Cho biết S thuộc kiểu gì biết rằng n là một biến kiểu Shortint và trong chương trình có lệnh gán: S:=n(n-1)/2;3. Biết rằng trong chương trình có một lệnh gán: i:=n mod 4Hỏi n có thể khai báo kiểu real được không? 4. Biết rằng trong chương trình có sử dụng một lệnh gán i:=ORD(n). Hãy xác định các kiểu có thể sử dụng được trong khai báo của n5. Biết rằng S1 và S2 là hai biến kiểu Byte và trong chương trình có lệnh gán S:=S1+S2. Xác định kiểu khai báo đúng nhất của S6. Biết rằng n là một biến kiểu Byte và trong chương trình có lệnh gán S:=n*(n+1). Hỏi S có thể nhận các kiểu khai báo nào?7.Biết rằng trong chương trình có một lệnh gán: i:=ORD(n). Hỏi kiểu của i có thể là kiểu số thực được không?8. Biết rằng trong chương trình có sử dụng lệnh gán i:=n MOD 4. Hỏi kiểu của n có thể là real được không9.Biết rằng n là một biến kiểu Integer và trong chương trình có sử dụng lệnh gán S:=n*(n+1)/2. Hỏi kiểu của S có thể trùng với kiểu của n được hay không? 10. Biết n là một biến kiểu Integer và S:=n*n. Hỏi biến i có thể khai báo kiểu Integer được không nếu gán i:=SQRT(S)11. Biết rằng n là một biến kiểu integer và S:=n*(n div (trunc (n/2))). Hỏi S có thể nhận giá trị kiểu Integer được không?