Giáo trình Turbo Pascal

294 trang ngocly 140

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Turbo Pascal", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_turbo_pascal.doc

Nội dung text: Giáo trình Turbo Pascal

MỤC LỤC 1. THUẬT TOÁN 2. CÁC PHƯỢNG PHÁP BIỂU DIỄN THUẬT TOÁN 3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 4.PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN 5. THUẬT TOÁN ĐỆ QUY 6.THUẬT GIẢI 5.1.GIỚI THIỆU NGÔN NGỮ PASCAL 5.2. CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL 5.3. CẤU TRÚC CHUNG CỦA CHƯƠNG TRÌNH PASCAL 5.4. SỬ DỤNG PHẦN MỀM TURBO PASCAL 5.5 CÂU HỎI TRẮC NGHIỆM 5.6. BÀI TẬP 6.1. KHÁI NIỆM VỀ KIỂU DỮ LIỆU 6.2. KIỂU SỐ NGUYÊN 6.3. KIỂU SỐ THỰC 6.4. KIỂU KÝ TỰ (CHAR) 6.5. KIỂU LÔGIC (BOOLEAN) 6.6. CHUỖI KÝ TỰ (STRING) 6.7. CÂU HỎI TRẮC NGHIỆM 7.1. HẰNG, BIẾN và BIỂU THỨC 7.2. CÂU LỆNH và LỜI CHÚ GIẢI 7.3.1. NHẬP DỮ LIỆU, THỦ TỤC “READLN” 7.3.2. XUẤT DỮ LIỆU, THỦ TỤC “WRITE” và “WRITELN” 7.4. KIỂU LIỆT KÊ và KIỂU ÐOẠN CON 7.5. CÂU HỎI TRẮC NGHIỆM
7.6. BÀI TẬP 8.1. CÂU LỆNH IF 8.2. CÂU LỆNH CASE 8.3. CÂU HỎI TRẮC NGHIỆM 8.4. BÀI TẬP 9.1. CÂU LỆNH LẶP FOR 9.2. CÂU LỆNH LẶP WHILE 9.3. CÂU LỆNH LẶP REPEAT 9.4. CÂU HỎI TRẮC NGHIỆM 9.5. BÀI TẬP 10.1. MẢNG MỘT CHIỀU 10.2. MẢNG HAI CHIỀU (MA TRẬN) 10.3. CÂU HỎI TRẮC NGHIỆM 10.4. BÀI TẬP 11.1. CÁC VÍ DỤ NÂNG CAO VỀ CÂU LỆNH LẶP 11.2. CÁC VÍ DỤ NÂNG CAO VỀ MẢNG 11.3. KIỂU CHUỖI KÝ TỰ 11.4. CÂU HỎI TRẮC NGHIỆM 11.5. BÀI TẬP 12.1. KHÁI NIỆM VỀ CHƯƠNG TRÌNH CON 12.2. HÀM (FUNCTION) 12.3. THỦ TỤC (PROCEDURE) 12.4. CÂU HỎI TRẮC NGHIỆM 12.5. BÀI TẬP 13.1. THAM SỐ TRỊ VÀ THAM SỐ BIẾN 13.2. PHẠM VI TÁC DỤNG CỦA CÁC KHAI BÁO
13.3. SỰ THAM KHẢO TRƯỚC và SỰ ÐỆ QUI 13.4. CÂU HỎI TRẮC NGHIỆM 13.5. BÀI TẬP 14.1 KIỂU BẢN GHI 14.2. CÁC VÍ DỤ VỀ BẢN GHI 14.3. CÂU HỎI TRẮC NGHIỆM 14.4 .BÀI TẬP 15.1. KIỂU TẬP HỢP 15.2. DỮ LIỆU KIỂU TẬP TIN 15.3. CÂU HỎI TRẮC NGHIỆM 15.4. BÀI TẬP 1. THUẬT TOÁN Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán. Tại sao lại là "Thuật toán" ? Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông. Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải ? Tính "không mập mờ" và "có thể thực thi được" gọi chung là tính xác định.
Giả sử khi nhận một lớp học mới, Ban Giám hiệu yêu cầu giáo viên chủ nhiệm chọn lớp trưởng mới theo các bước sau : 1. Lập danh sách tất các học sinh trong lớp. 2. Sắp thứ tự danh sách học sinh. 3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng. Khi nhận được thông báo này, giáo viên chắc chắn sẽ rất bối rối vì không hiểu là trong danh sách học sinh cần có những thông tin gì? Danh sách chỉ cần họ tên, hay cần thêm ngày tháng năm sinh? Có cần thêm điểm trung bình không? Yêu cầu 2 lại càng gây nhiều thắc mắc. Cần phải sắp xếp danh sách theo chiều tăng dần hoặc giảm dần ? Sắp theo chỉ tiêu gì ? Theo tên, theo ngày tháng năm sinh hay theo điểm trung bình chung, Giả sử sắp theo điểm trung bình thì nếu có hai học sinh cùng điểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào sẽ sắp sau ? Hướng dẫn ở trên vi phạm tính chất "không mập mờ" của thuật toán. Nghĩa là, có quá nhiều thông tin còn thiếu để làm cho các bước 1,2 được hiểu đúng và hiểu theo một nghĩa duy nhất. Nếu sửa lại một chút ít thì hướng dẫn trên sẽ trở nên rõ ràng hơn rất nhiều và có thể gọi là một thuật toán chọn lớp trưởng ! 1. Lập danh sách tất các học sinh trong lớp theo hai thông tin: Họ và Tên; Ðiểm trung bình cuối năm. 2. Sắp hạng học sinh theo điểm trung bình theo thứ tự giảm dần (từ điểm cao đến điểm thấp). Hai học sinh có cùng điểm trung bình sẽ có cùng hạng. 3. Nếu chỉ có một học sinh có hạng nhất thì chọn học sinh đó làm lớp trưởng. Trường hợp có nhiều học sinh đồng hạng nhất thì chọn học sinh có điểm môn Toán cao nhất làm lớp trưởng. Nếu vẫn còn nhiều hơn một học sinh đồng hạng nhất và có cùng điểm môn Toán cao nhất thì tiến hành bốc thăm. Ở đây chúng ta cần phân biệt mập mờ và sự chọn lựa có quyết định. Mập mờ là thiếu thông tin hoặc có nhiều chọn lựa nhưng không đủ điều kiện để quyết định. Còn chọn lựa có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề. Chẳng hạn trong vấn đề chọn lớp trưởng ở trên, bước 3 thể hiện một sự lựa chọn có quyết định. Tất nhiên, khi chưa lập danh sách, chưa xếp hạng theo điểm trung bình thì giáo viên không thể biết được sẽ chọn lớp trưởng theo cách nào. Nhưng khi đã sắp xong danh sách thì chỉ có một phương án chọn duy nhất. Tính "thực thi được" cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được. Tính "dừng" là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật
toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau : B1. Hỏi giá trị của n. B2. S = 0 B3. i = 1 B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5 B5. Cộng thêm i vào S B6. Cộng thêm 2 vào i B7. Quay lại bước B4. B8. Tổng cần tìm chính là S. Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n. Thay vì viết là "nếu i lớn hơn n" thì ta thay bằng điều kiện "nếu i bằng n+1" vì theo toán học "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều kiện "i=n+1" không phải lúc nào cũng đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ. Nếu n là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn. Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học sinh nhất định là có khả năng đưa ra lời giải đúng! Thuật toán thì cứng nhắc ! Các tính chất của thuật toán rất chặt chẽ và cứng nhắc. Nhưng điều đó cũng có nghĩa là khả năng giải quyết vấn đề theo kiểu thuật toán cũng bị giới hạn. Sau này, người ta đã "làm mềm" đi hai tính chất quan trọng của thuật toán là tính xác định và tính đúng để giải quyết những vấn đề phức tạp hơn mà với các tính chất chặt chẽ của thuật toán thì không thể giải quyết được. Ðó là các thuật toán đệ quy và thuật giải. Ta sẽ tìm hiểu về điều này ngay trong các mục 4 và 5 của chương này. Các đặc trưng khác của thuật toán Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm 3 đặc trưng phụ khác. 1. Ðầu vào và đầu ra (input/output) : mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng.
2. Tính hiệu quả (effectiveness) : tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán. 3. Tính tổng quát (generalliness) : thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi. Thuật toán giải phương trình bậc hai ax2+bx+c=0 (a?0) 1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c 2. Nếu a=0 thì 2.1. Yêu cầu đầu vào không đảm bảo. 2.2. Kết thúc thuật toán. 3. Trường hợp a khác 0 thì 3.1. Tính giá trị D = b2-4ac 3.2. Nếu D > 0 thì 3.2.1. Phương trình có hai nghiệm phân biệt x1 và x2 3.2.2. Giá trị của hai nghiệm được tính theo công thức sau 3.2.3. Kết thúc thuật toán. 3.3. Nếu D = 0 thì 3.3.1. Phương trình có nghiệm kép x0 3.3.2. Giá trị của nghiệm kép là 3.3.3. Kết thúc thuật toán 3.4. Nếu D < 0 thì 3.4.1. Phương trình vô nghiệm.
3.4.2. Kết thúc thuật toán. Thuật toán tìm hộp có trọng lượng nặng nhất Vấn đề : Có n hộp có khối lượng khác nhau và một cái cân dĩa. Hãy chỉ ra cách cân để tìm được hộp có trọng lượng nặng nhất. Vấn đề này là thể hiện của một bài toán tổng quát : Cho một tập hợp A hữu hạn và một thứ tự toàn phần trên A. Hãy xây dựng thuật toán tìm phần tử lớn nhất của A. Bài toán trong toán học có vẻ rất phức tạp nhưng một thể hiện trên thực tế lại rất dễ hiểu, và cách giải quyết cũng đơn giản. Từ đó ta có thể dễ dàng suy ra cách giải bài toán tổng quát. 1. Nếu chỉ có 1 hộp (n=1) thì 1.1. Hộp đó chính là hộp nặng nhất. 1.2. Kết thúc thuật toán. 2. Ngược lại nếu có từ hai hộp trở lên (n>1) 2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân. 2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào nữa, sang bước 5. 3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống. 3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác. 4. Trở lại bước 3. 5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc. Thuật toán Euclid tìm ước số chung lớn nhất Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b. 1. Yêu cầu cho biết giá trị của a, b. 2. a0 = a 3. b0 = b 4. i = 0 5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7. 5.1 Tăng i lên 1. 5.2. Nếu ai-1 > bi-1 thì ai = ai-1 - bi-1
bi = bi-1 5.3. Ngược lại bi = bi-1 - ai-1 ai = ai-1 6. Trở lại bước 5. 7. Ước số chung lớn nhất của a, b là ai . 2. CÁC PHƯỢNG PHÁP BIỂU DIỄN THUẬT TOÁN Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn từ toán học như : "ta có", "điều phải chứng minh", "giả thuyết", và sử dụng những phép suy luận toán học như phép suy ra, tương đương, Thuật toán là một phương pháp thể hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Ðể có thể truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thuật toán. Có 3 phương pháp biểu diễn thuật toán : 1. Dùng ngôn ngữ tự nhiên. 2. Dùng lưu đồ-sơ đồ khối (flowchart). 3. Dùng mã giả (pseudocode). 2.1. Ngôn ngữ tự nhiên Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, Bạn có thể tham khảo lại ba ví dụ trong mục 1 của chương để hiểu cách biểu diễn thuật toán theo ngôn ngữ tự nhiên. 2.2. Lưu đồ - sơ đồ khối Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý. Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác. Một thao tác là thao tác chọn lựa dựa theo một điều kiện nào đó. Chẳng hạn : thao tác "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" là thao tác chọn lựa. Các thao tác còn lại không thuộc loại chọn lựa được
xếp vào loại hành động. Chẳng hạn, "Chọn một hộp bất kỳ và để lên dĩa cân còn trống." là một thao tác thuộc loại hành động. 2.2.1. Thao tác chọn lựa (decision) Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện. 2.2.2. Thao tác xử lý (process) Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý. 2.2.3.Ðường đi (route) Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình thực hiện sẽ lần lượt đi từ bước trước đến bước sau (trừ khi có yêu cầu nhảy sang bước khác). Trong ngôn ngữ lưu đồ, do thể hiện các bước bằng hình vẽ và có thể đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình tự thực hiện các thao tác. Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện. Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1, B2, B3. Từ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với điều kiện thỏa và một hướng ứng với điều kiện không thỏa. Do vậy, ta dùng hai cung xuất phát từ các đỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện không thỏa.
2.2.4. Ðiểm cuối (terminator) Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn bằng hình ovan, bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end. Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu) hoặc cung đi vào (điểm kết thúc). Xem lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách sử dụng của điểm cuối. 2.2.5. Ðiểm nối (connector) Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với nhau. Bên trong điểm nối, ta đặt một ký hiệu để biết sự liên hệ giữa các điểm nối. 2.2.6. Ðiểm nối sang trang (off-page connector)
Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang. Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ. 2.3. Mã giả Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp (Chúng ta sẽ tìm hiểu về thao tác lặp trong các bài sau). Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Chính vì lý do này, chúng ta chưa vội tìm hiểu về mã giả trong bài này (vì chúng ta chưa biết gì về ngôn ngữ lập trình!). Sau khi tìm hiểu xong bài về thủ tục - hàm bạn sẽ hiểu mã giả là gì ! Một đoạn mã giả của thuật toán giải phương trình bậc hai if Delta > 0 then begin x1=(-b-sqrt(delta))/(2*a) x2=(-b+sqrt(delta))/(2*a) xuất kết quả : phương trình có hai nghiệm là x1 và x2 end else if delta = 0 then
xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm * Các từ in đậm là các từ khóa của ngôn ngữ Pascal 3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Một chương trình máy tính thường được cài đặt dựa trên một thuật toán đúng để giải quyết bài toán hay vấn đề. Tuy nhiên, ngay cả khi thuật toán đúng, chương trình vẫn có thể không sử dụng được đối với một dữ liệu đầu vào nào đó vì thời gian để cho ra kết quả là quá lâu hoặc sử dụng quá nhiều bộ nhớ (vượt quá khả năng đáp ứng của máy tính). Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời gian và "không gian" cần thiết để thực hiện thuật toán. Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, của máy tính để thuật toán có thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của thuật toán. Trong phần này, khi nói đến độ phức tạp của thuật toán, chúng ta chỉ đề cập đến những đánh giá về mặt thời gian mà thôi. Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những hiểu biết sâu sắc về thuật toán và nhiều kiến thức toán học khác. Ðây là công việc mà không phải bất cứ người nào cũng làm được. Rất may mắn là các nhà toán học đã phân tích cho chúng ta độ phức tạp của hầu hết các thuật toán cơ sở (sắp xếp, tìm kiếm, các thuật toán số học, ). Chính vì vậy, nhiệm vụ còn lại của chúng ta là hiểu được các khái niệm liên quan đến độ phức tạp của thuật toán. Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối (chạy thuật toán mất bao nhiêu giây, bao nhiêu phút, ) để thực hiện thuật toán mà là xác định mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và chi phí (số thao tác, số phép tính cộng,trừ, nhân, chia, rút căn, ) để thực hiện thuật toán. Sở dĩ người ta không quan tâm đến thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của máy tính, mà các máy tính khác nhau thì có tốc độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào : T = f(input) Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi phí. Trong các thuật toán, độ lớn của dữ liệu đầu vào thường được thể hiện bằng một con số nguyên n. Chẳng hạn : sắp xếp n con số nguyên, tìm con số lớn nhất trong n số, tính điểm trung bình của n học sinh, Lúc này, người ta thể hiện chi phí thực hiện thuật toán bằng một hàm số phụ thuộc vào n : T = f(n) Việc xây dựng một hàm T tổng quát như trên trong mọi trường hợp của thuật toán là một việc rất khó khăn, nhiều lúc không thể thực hiện được. Chính vì vậy mà người ta chỉ xây dựng hàm T cho một số trường hợp đáng chú ý nhất của thuật toán, thường là trường hợp tốt nhất và xấu nhất. Chúng ta trở lại ví dụ về thuật toán tìm hộp nặng nhất trong n hộp cho trước, nhưng lần này ta làm việc trên một thể hiện khác của vấn đề. Ðây là một thuật toán tương đối đơn giản nên chúng ta
có thể tiến hành phân tích được độ phức tạp. Trước khi phân tích độ phức tạp, ta nhắc lại đôi điều về thuật toán này. Tìm số lớn nhất trong một dãy số Bài toán : Cho một dãy số a có n phần tử a1, a2, an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a. Nhận xét 1. Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất. 2. Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 £ amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử. Thuật toán 1. Ghi nhớ amax = a1. 2. i = 2. 3. Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5. 3.1. Nếu (ai > amax ) thì 3.1.1. Ghi nhớ amax = ai . 3.2. Tăng i lên 1. 4. Trở lại bước 3. 5. Phần tử lớn nhất dãy a chính là amax .Kết thúc. Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con số lớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy ra khi con số lớn nhất nằm ở cuối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần.
Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở bước 3.1 luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hoặc bất biến của thuật toán. Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i ³ 2, ai amax ở bước 3.1 luôn không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán. T = f(n) = n-1 Trường hợp xấu nhất : Ta có : với mọi i>1, ai-1 amax ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là T = f(n) = 2(n-1)=2n-2 Ðịnh nghĩa Cho hai hàm f và g có miền xác định trong tập số tự nhiên . Ta viết f(n) = O(g(n)) và nói f(n) có cấp cao nhất là g(n) khi tồn tại hằng số C và k sao cho | f(n) | £ C.g(n) với mọi n > k
Tuy chi phí của thuật toán trong trường hợp tốt nhất và xấu nhất có thể nói lên nhiều điều nhưng vẫn chưa đưa ra được một hình dung tốt nhất về độ phức tạp của thuật toán. Ðể có thể hình dung chính xác về độ phức tạp của thuật toán, ta xét đến một yếu tố khác là độ tăng của chi phí khi độ lớn n của dữ liệu đầu vào tăng. Theo định nghĩa ở trên, ta nhận thấy chi phí thấp nhất và lớn nhất của thuật toán tìm số lớn nhất đều bị chặn bởi O(n) (tồn tại hằng số C=10, k=1 để 2n-2 1). Một cách tổng quát, nếu hàm chi phí của thuật toán (xét trong một trường hợp nào đó) bị chặn bởi O(f(n)) thì ta nói rằng thuật toán có độ phức tạp là O(f(n)) trong trường hợp đó. Như vậy, thuật toán tìm số lớn nhất có độ phức tạp trong trường hợp tốt nhất và xấu nhất đều là O(n). Người ta gọi các thuật toán có độ phức tạp O(n) là các thuật toán có độ phức tạp tuyến tính. Sau đây là một số "thước đo" độ phức tạp của thuật toán được sử dụng rộng rãi. Các độ phức tạp được sắp xếp theo thứ tự tăng dần. Nghĩa là một bài toán có độ phức tạp O(nk) sẽ phức tạp hơn bài toán có độ phức tạp O(n) hoặc O(logan). 4. PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN Ðộ phức tạp của thuật toán chính là yếu tố cơ sở để phân loại vấn đề-bài toán. Một cách tổng quát, mọi bài toán đều có thể chia làm 2 lớp lớn là : giải được và không giải được. Lớp giải được chia làm 2 lớp con. Lớp con đầu tiên là các bài toán có độ phức tạp đa thức : nghĩa là bài toán có thể giải được bằng thuật toán có độ phức tạp đa thức (hay nói ngắn gọn : lớp đa thức) được xem là có lời giải thực tế. Lớp con thứ hai là những bài toán có độ phức tạp không phải là đa thức mà lời giải của nó được xem là thực tế chỉ cho những số liệu đầu vào có chọn lựa cẩn thận và tương đối nhỏ. Cuối cùng là những bài toán thuộc loại NP chưa thể phân loại một cách chính xác là thuộc lớp bài toán có độ phức tạp đa thức hay có độ phức tạp không đa thức. 4.1. Lớp bài toán có độ phức tạp đa thức Các bài toán thuộc lớp này có độ phức tạp là O(nk) hoặc nhỏ hơn O(nk). Chẳng hạn như các bài toán có độ phức tạp là O(nlog2n) được xem là các bài toán thuộc lớp đa thức vì nlog2n bị chặn bởi n2 ( nlog2n £ n2 với mọi n>0). Như vậy các bài toán có độ phức tạp hằng O(1), phức tạp tuyến tính O(n) và logarith O(nlogan) đều là các bài toán thuộc lớp đa thức. Còn các bài toán có độ phức tạp lũy thừa O(an) hoặc giai thừa O(n!) là không thuộc lớp đa thức. Tuy độ phức tạp chỉ là số đo về độ tăng của chi phí ứng với độ tăng của dữ liệu đầu vào nhưng nó cũng cho chúng ta có một đánh giá tương đối về thời gian thi hành thuật toán. Các thuật toán thuộc
lớp đa thức được xem là các bài toán có lời giải thực tế. Lời giải thực tế được hiểu rằng là chi phí về mặt thời gian và không gian cho việc giải bài toán là chấp nhận được trong điều kiện hiện tại. Bất kỳ một bài toán nào không thuộc lớp này thì đều có chi phí rất lớn. Có thể giải được hay không? Người ta đã ước tính thời gian cần thiết để giải một mật mã được mã hóa bằng khóa 128-bit là trên 1 triệu năm với điều kiện làm việc trên các siêu máy tính mạnh nhất hiện nay! Chính vì lý do này, một bài toán được xem là có thể giải được trên thực tế hay không phụ thuộc vào độ phức tạp của bài toán đó có phải là đa thức hay không. 4.2. Lớp bài toán có độ phức tạp không đa thức Thật không may mắn, nhiều bài toán thực sự có lời giải lại không thuộc lớp của bài toán đa thức. Ví dụ : cho một tập hợp có n phần tử, hãy liệt kê tất cả các tập con khác trống của tập hợp này. Bằng toán học, người ta đã chứng minh được rằng số tập con của một tập hợp có n phần tử là 2n-1. Lời giải tuy đã có nhưng khi thể hiện lời giải này bằng bất kỳ thuật toán nào thì phải tốn ít nhất 2n-1 bước. Dễ thấy rằng độ phức tạp của bài toán này cũng cỡ O(2n). Như vậy bài toán này không thuộc lớp của bài toán đa thức. Với n vào khoảng 16, số bước cần thiết chỉ khoảng vài chục ngàn là hoàn toàn giải được trên các máy tính hiện nay. Nhưng khi số phần tử lên đến 32 thì ta đã tốn một số bước lên đến 4 tỷ, chỉ thêm một phần tử nữa thôi, chúng ta đã tốn 8 tỷ bước! Với số lượng bước như vậy, dù chạy trên một siêu máy tính cũng phải tốn một thời gian đáng kể! Các bài toán không thuộc lớp đa thức chỉ giải được với một độ lớn dữ liệu đầu vào nhất định. 4.3. Lớp bài toán NP Chúng ta đều biết rằng tính xác định là một trong ba đặc tính quan trọng của thuật toán. Nghĩa là mỗi bước của thuật toán phải được xác định duy nhất và có thể thực thi được. Nếu có sự phân chia trường hợp tại một bước thì thông tin tại bước đó phải đầy đủ để thuật toán có thể tự quyết định chọn lựa trường hợp nào. Trong mục 4.3 này, ta tạm gọi các thuật toán thỏa mãn tính xác định là các thuật toán tự quyết. Vậy thì điều gì sẽ xảy ra nếu ta đưa ra một "thuật toán" có tính không tự quyết? Nghĩa là tại một bước của "thuật toán", ta đưa ra một số trường hợp chọn lựa nhưng không cung cấp đầy đủ thông tin để "thuật toán" tự quyết định? Thật ra, trong cuộc sống, những "thuật toán" thuộc loại này rất hay được áp dụng. Chẳng hạn ta có một lời chỉ dẫn khi đi du lịch : "Khi đi hết khu vườn này, bạn hãy chọn một con đường mà bạn cảm thấy thích. Tất cả đều dẫn đến bảo tàng lịch sử.". Nếu là khách du lịch, bạn sẽ cảm thấy bình thường. Nhưng máy tính thì không! Nó không thể thực thi những hướng dẫn không rõ ràng như vậy! Ðến đây, lập tức sẽ có một câu hỏi rằng "Tại sao lại đề cập đến những thuật toán có tính không tự quyết dù máy tính không thể thực hiện một thuật toán như vậy?". Câu trả lời là, khi nghiên cứu về thuật toán không tự quyết, dù không dùng để giải bài toán nào đi nữa, chúng ta sẽ có những hiểu biết về hạn chế của những thuật toán tự quyết thông thường. Ðến đây, ta hãy xem sự khác biệt về độ phức tạp của một thuật toán tự quyết và không tự quyết để giải quyết cho cùng một vấn đề. Bài toán người bán hàng
Một nhân viên phân phối hàng cho một công ty được giao nhiệm vụ phải giao hàng cho các đại lý của công ty, sau đó trở về công ty. Vấn đề của người nhân viên là làm sao đi giao hàng cho tất cả đại lý mà không tiêu quá số tiền đổ xăng mà công ty cấp cho mỗi ngày. Nói một cách khác, làm sao đừng đi quá một số lượng cây số nào đó. Một lời giải cổ điển cho bài toán này là liệt kê một cách có hệ thống từng con đường có thể đi, so sánh chiều dài mỗi con đường tìm được với chiều dài giới hạn cho đến lúc tìm được một con đường phù hợp hoặc đã xét hết tất cả các con đường có thể đi. Tuy nhiên, cách giải quyết này có độ phức tạp không phải đa thức. Bằng toán học, người ta đã chứng minh được rằng độ phức tạp của thuật toán này là O(n!). Như vậy, với số đại lý lớn thì thuật toán trên được xem là không thực tế. Bây giờ, chúng ta xem qua một thuật toán không tự quyết. 1. Chọn một con đường có thể và tính chiều dài của nó. 2. Nếu chiều dài này không lớn hơn giới hạn thì báo là thành công, ngược lại báo chọn lựa sai. Quan điểm của ta trong cách giải quyết này là nếu chọn sai thì là do lỗi của người chọn chứ không phải lỗi của thuật toán !. Theo thuật toán này thì chi phí để tính chiều dài của con đường được chọn sẽ tỷ lệ với số đại lý; chi phí để so sánh chiều dài quãng đường với giới hạn cho phép thì không liên quan đến số thành phố. Như vậy, chi phí của thuật toán này là một hàm có dạng T = an+b với n là số đại lý và a,b là các hằng số. Ta kết luận rằng, độ phức tạp của thuật toán này là O(n) hay độ phức tạp thuộc lớp đa thức. Như vậy, nếu dùng thuật toán tự quyết thì bài toán người bán hàng sẽ có độ phức tạp không thuộc lớp đa thức, còn nếu dùng thuật toán không tự quyết thì bài toán sẽ có độ phức tạp đa thức. Ðịnh nghĩa Một bài toán khi được giải bằng một thuật toán không tự quyết mà có độ phức tạp thuộc lớp đa thức thì được gọi là một bài toán đa thức không tự quyết hay viết tắt là bài toán NP. Theo định nghĩa trên thì bài toán người bán hàng là bài toán thuộc lớp NP. Cho đến nay người ta chưa chứng minh được rằng tồn tại hay không một thuật toán tự quyết có độ phức tạp đa thức cho bài toán người bán hàng rong. Vì vậy, bài toán này (là một bài toán NP) chưa thể xếp được vào lớp đa thức hay không đa thức. Do đó, lớp bài toán NP chưa thể phân loại là thuộc lớp đa thức hay không. Dĩ nhiên, lớp bài toán NP cũng chứa những bài toán thuộc lớp đa thức thực sự, bởi vì nếu một bài toán được giải bằng thuật toán tự quyết có độ phức tạp đa thức thì chắc chắn khi dùng thuật toán không tự quyết thì cũng sẽ có độ phức tạp đa thức.
5. THUẬT TOÁN ĐỆ QUY Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã biết, một thuật toán cần phải thỏa mãn 3 tính chất : – Tính hữu hạn. – Tính xác định – Tính đúng đắn Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ ba tính chất trên rất khó khăn. Trong khi đó, nếu ta xây dựng một thuật toán vi phạm một vài tính chất trên thì cách giải lại trở nên đơn giản hơn nhiều và có thể chấp nhận được. Một trong những trường hợp đó là thuật toán đệ quy. Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (hay nói một cách nôm na là đồng dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, ), và quá trình này tiếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải được bài toán ở cấp độ ban đầu. Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng, những khái niệm dựa trên chính những đối tượng, khái niệm đó. Ðịnh nghĩa giai thừa Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là : 0! = 1 n! = (n-1)!n với mọi n>0 Ðịnh nghĩa dãy số Fibonacci f0 = 1 f1 = 1
fn = fn-1 + fn-2 với mọi n>1 Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa theo kiểu quy nạp. Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học. Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề. Tuy nhiên, đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ n không được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn, để tính được giá trị phần tử thứ 5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính f3+f4, nhưng ta chưa biết giá trị f3 và f4 tại thời điểm này. Ðến đây, ta phải lùi lại để tính f3 và f4. Ðể tính f3 ta lại phải lùi về để tính f2, Tất nhiên, là quá trình tính lùi này phải dừng sau một số hữu hạn bước. Trong trường hợp này, điểm dừng chính là giá trị f1 và f0. Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp đặc biệt nào đó, còn gọi là trường hợp dừng. Sau đó, các trường hợp khác của bài toán sẽ được xác định thông qua trường hợp đặc biệt này. Ðối với việc tính dãy Fibonacci, trường hợp dừng chính là giá trị của f0 và f1. Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần: Phần cơ sở Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu cầu gọi đệ quy). Nếu thuật toán đệ quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta đôi lúc còn gọi phần cơ sở là trường hợp dừng. Phần đệ quy Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán nhưng với một cấp độ dữ liệu thấp hơn.
6.THUẬT GIẢI 6.1. Mở rộng khái niệm thuật toán : thuật giải Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đã đưa ra những nhận xét như sau : Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không. Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng. Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được.
Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán : tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn, có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ. Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở rộng cửa cho chúng ta trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra. Một trong những thuật giải thường được đề cập đến và sử dụng trong khoa học trí tuệ nhân tạo là các cách giải theo kiểu Heuristic. 6.2. Thuật giải Heuristic Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau : Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất) Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn. Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ sở như sau: Nguyên lý vét cạn thông minh : Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu. Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. Nguyên lý thứ tự : Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt. Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Ðó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải.
Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải. Bài toán hành trình ngắn nhất - ứng dụng nguyên lý Greedy Bài toán : Chúng ta trở lại với bài toán người bán hàng. Nhưng ở đây, yêu cầu bài toán hơi khác là làm sao tìm được hành trình ngắn nhất có thể được. Tất nhiên ta có thể giải bài toán này bằng cách liệt kê tất cả con đường có thể đi, tính chiều dài của mỗi con đường đó rồi tìm con đường có chiều dài ngắn nhất. Tuy nhiên, cách giải này lại có độ phức tạp O(n!) (tổng số hành trình có thể có là n!). Do đó, khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh. Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là dùng một thuật giải Heuristic ứng dụng nguyên lý Greedy. Tư tưởng của thuật giải như sau : 1. Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n đại lý rồi chọn đi theo con đường ngắn nhất. 2. Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên. Nghĩa là liệt kê tất cả con đường từ đại lý ta đang đứng đến những đại lý chưa đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại lý nào để đi. Bạn có thể quan sát hình 2.14 để thấy được quá trình chọn lựa. Theo nguyên lý Greedy, ta lấy tiêu chuẩn hành trình ngắn nhất của bài toán làm tiêu chuẩn chọn lựa cục bộ. Ta hy vọng rằng, khi đi trên n đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất. Ðiều này không phải lúc nào cũng đúng. Với điều kiện trong hình 2.14 thì thuật giải cho chúng ta một hành trình có chiều dài là 14 trong khi hành trình tối ưu là 13. Kết quả của thuật giải Heuristic trong trường hợp này chỉ lệch 1 đơn vị so với kết quả tối ưu. Trong khi đó, độ phức tạp của thuật giải Heuristic này chỉ là O(n2). Tất nhiên, thuật giải theo kiểu Heuristic đôi lúc lại đưa ra kết quả không tốt, thậm chí rất tệ như trường hợp ở hình 2.15.
Bài toán phân việc – ứng dụng của nguyên lý thứ tự Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2, ,Jm. Công ty có n máy gia công lần lượt là P1, P2, Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị ngắt ngang. Ðể gia công một công việc Ji trên một máy bất kỳ ta cần dùng một thời gian tương ứng là ti. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất. Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 công việc với thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Ta có một phương án phân công (L) như hình sau : Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên máy P1, J5 trên P2 và J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong
lúc đó, hai máy P1 và P2 vẫn đang thực hiện công việc đầu tiên mình Sơ đồ phân việc theo hình ở trên được gọi là lược đồ GANTT. Theo lược đồ này, ta thấy thời gian để hoàn thành toàn bộ 6 công việc là 12. Nhận xét một cách cảm tính ta thấy rằng phương án (L) vừa thực hiện là một phương án không tốt. Các máy P1 và P2 có quá nhiều thời gian rảnh. Xây dựng một thuật toán để tìm một phương án tối ưu L0 cho bài toán này là một bài toán khó, đòi hỏi các kỹ thuật phức tạp mà chúng ta sẽ không đề cập ở đây. Bây giờ ta xét đến một thuật giải Heuristic rất đơn giản để giải bài toán này. 1. Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công. 2. Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất. Với tư tưởng như vậy, ta sẽ có một phương án L* như sau : Rõ ràng phương án L* vừa thực hiện cũng chính là phương án tối ưu của trường hợp này vì thời gian hoàn thành là 8, đúng bằng thời gian của công việc J3. Ta hy vọng rằng một thuật giải Heuristic đơn giản như vậy sẽ là một thuật giải tối ưu. Nhưng tiếc thay, ta dễ dàng đưa ra được một trường hợp mà thuật giải Heuristic không đưa ra được kết quả tối ưu. Nếu gọi T* là thời gian để gia công xong n chi tiết máy do thuật giải Heuristic đưa ra và To là thời gian tối ưu thì người ta đã chứng minh được rằng
Với kết quả này, ta có thể xác lập được sai số mà chúng ta phải gánh chịu nếu dùng Heuristic thay vì tìm một lời giải tối ưu. Chẳng hạn với số máy = 2 (n=2) ta có , và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công thức này, số máy càng lớn thì sai số càng lớn. Trong trường hợp n lớn thì 1/(3n) xem như bằng 0. Như vậy, sai số tối đa mà ta phải chịu là T* ? 4/3To, nghĩa là sai số tối đa là 33%. Tuy nhiên, khó tìm ra được những trường hợp mà sai số đúng bằng giá trị cực đại, dù trong trường hợp xấu nhất. Thuật giải Heuristic trong trường hợp này rõ ràng đã cho chúng ta những lời giải tương đối tốt. Bài toán Ta-canh - ứng dụng của hàm Heuristic Bài toán Ta-canh đã từng là một trò chơi khá phổ biến, đôi lúc người ta còn gọi đây là bài toán 9- puzzle. Trò chơi bao gồm một hình vuông kích thước 3x3 ô. Có 8 ô có số, mỗi ô có một số từ 1 đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di chuyển một ô nằm cạnh ô trống về phía ô trống. Vấn đề là từ một trạng thái ban đầu bất kỳ, làm sao đưa được về trạng thái cuối là trạng thái mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự từ trái sang phải, từ trên xuống dưới, ô cuối dùng là ô trống. Cho đến nay, người ta vẫn chưa tìm được một thuật toán chính xác, tối ưu để giải bài toán này. Tuy nhiên, cách giải theo kiểu Heuristic lại khá đơn giản. Nhận xét rằng : tại mỗi thời điểm ta chỉ có tối đa 4 ô có thể di chuyển. Vấn đề là tại thời điểm đó, ta sẽ chọn lựa di chuyển ô nào? Chẳng hạn ở hình trên, ta nên di chuyển (1), (2), (6) hay (7)? Gọi T0 là trạng thái đích của bài toán và TK là trạng thái hiện tại. Ta gọi V(i,j) là con số nằm ở ô (i,j), với ô trống V(i,j)=0. Ta đặt d(i,j) là số ô cần di chuyển để đưa con số ở ô (i,j) về đúng vị trí của nó ở trạng thái TO .
Hàm FK tại trạng thái TK bằng tổng của các d(i,j) sao cho vị trí (i,j) không phải là ô trống. Như vậy đối với trạng thái ở hình ban đầu, hàm FK sẽ có giá trị là FK = 2+1+3+1+0+1+2+2=12. Một cách tổng quát, giá trị hàm FK tại trạng thái TK sẽ là Từ trạng thái TK , ta có tối đa 4 cách di chuyển.Ta ký hiệu các trạng thái mới này lần lượt là TKT ,TKD , TKTr ,TKP ứng với con số ở trên, dưới, trái, phải ô trống hiện tại bị di chuyển. Chẳng hạn, ứng với hình ban đầu, ta có thể có 4 trạng thái mới như hình bên. Ứng với các trạng thái mới, ta cũng sẽ có các hàm FK tương ứng là FKT ,FKD ,FKTr ,FKP. Dựa vào 4 con số này, ta sẽ chọn hướng đi có hàm FK tương ứng là nhỏ nhất, trong trường hợp bằng nhau ta chọn ngẫu nhiên một trong số các đường đó. Với ví dụ, ta sẽ chọn di chuyển ô mang số (2) vì FKD là nhỏ nhất. Sau khi đã di chuyển một ô, bài toán chuyển về một trạng thái TK mới. Ta lại thực hiện quá trình trên cho đến lúc đạt được trạng thái đích. Hàm FK trong ví dụ của chúng ta là một dạng hàm Heuristic. Tất nhiên, để giải được bài toán này trong những tình huống khó, hàm FK cần có nhiều sửa đổi. I.GIỚI THIỆU NGÔN NGỮ PASCAL PASCAL là ngôn ngữ lập trình cấp cao được giáo sư Niklaus Wirth ở trường đại học Kỹ thuật Zurich (Thụy sĩ) thiết kế và công bố vào năm 1971. Ông đặt tên cho ngôn ngữ của mình là Pascal để tưởng nhớ nhà toán học nổi tiếng người Pháp ở thế kỷ 17: Blaise Pascal, người đã sáng chế ra chiếc máy tính cơ khí đầu tiên của nhân loại. Qua thời gian sử dụng, Pascal ngày càng được đông đảo người dùng đánh gía cao, và trở thành một trong các ngôn ngữ thảo chương phổ biến nhất hiện nay. Thành công của ngôn ngữ Pascal là ở chỗ: nó là ngôn ngữ đầu tiên đưa ra và thể hiện được khái niệm lập trình có cấu trúc. Ý tưởng về một chương trình có cấu trúc xuất phát từ suy nghĩ cho rằng có thể chia một bài toán lớn, phức tạp thành nhiều bài toán nhỏ, đơn giản hơn. Nếu mỗi bài toán nhỏ được giải quyết bằng một chương trình con, thì khi liên kết các chương trình con này lại sẽ tạo nên một chương trình lớn giải quyết được bài toán ban đầu?.
Bằng cách chia một chương trình thành các chương trình con như vậy, người thảo chương có thể lập trình để giải quyết riêng lẻ từng phần một, từng khối một, hoặc có thể tổ chức để nhiều người cùng tham gia, mỗi người phụ trách một vài khối. Ðặc biệt khi phải thay đổi hay sửa chữa trong một khối thì điều đó sẽ ít ảnh hưởng đến các khối khác. Tính cấu trúc của ngôn ngữ Pascal còn thể hiện trong việc tổ chức các câu lệnh và tổ chức dữ liệu. Từ các lệnh đã có, người thảo chương có thể nhóm chúng lại với nhau và đặt giữa hai từ khóa Begin và End tạo thành một câu lệnh mới phức tạp hơn gọi là câu lệnh ghép. Ðến lượt mình, hai hay nhiều lệnh ghép lại có thể được nhóm lại để tạo thành một câu lệnh ghép phức tạp hơn nữa,.v.v. Tương tự như thế, ngôn ngữ Pascal cũng cho phép xây dựng các kiểu dữ liệu phức tạp hơn từ các kiểu dữ liệu đã có. Pascal là một ngôn ngữ không chỉ chặt chẽ về mặt cú pháp mà còn chặt chẽ về mặt dữ liệu. Mỗi biến, mỗi hằng tham gia trong chương trình luôn có một kiểu dữ liệu xác định và chỉ nhận những gía trị có cùng kiểu dữ liệu với nó. Ðiều này buộc người lập trình phải nắm chắc cú pháp và luôn chú ý đến tính tương thích của các biểu thức về mặt kiểu dữ liệu. Chính vì thế, thảo chương bằng ngôn ngữ Pascal là một cơ hội tốt không chỉ rèn luyện tư duy mà còn rèn luyện tính cẩn thận và chính xác. Ngày nay, Ngôn ngữ Pascal được dùng để viết các chương trình ứng dụng trong nhiều lĩnh vực. Với văn phạm sáng sủa, dễ hiểu, với khả năng đủ mạnh, Pascal được xem là ngôn ngữ thích hợp nhất để giảng dạy ở các trường phổ thông và đại học. II.CÁC PHẦN TỬ CƠ BẢN CỦA NGÔN NGỮ PASCAL 1.Tập ký tự cơ bản Mỗi ngôn ngữ đều được xây dựng từ một tập ký tự nào đó. Nhiều ký tự nhóm lại với nhau tạo nên các từ. Nhiều từ liên kết với nhau theo một qui tắc ngữ pháp nhất định (gọi là văn phạm) thì tạo nên các mệnh đề. Trong các ngôn ngữ thảo chương, mệnh đề?còn được gọi là câu lệnh. Một tập hợp các câu lệnh được sắp xếp theo một trật tự nhất định nhằm chỉ thị cho máy các thao tác phải thực hiện tạo thành một chương trình. Các chương trình được soạn thảo bởi người thảo chương và được lưu trữ trên đĩa dưới dạng các tập tin. Ngôn ngữ Pascal được xây dựng trên bộ ký tự cơ bản, gồm: các chữ cái la tinh: A, B, C, ,Z, a, b, c, , z các chữ số :0, 1, 2, 3, 4, 5, 6, 7, 8, 9 các ký hiệu đặc biệt: +, -, *, /, =, <, {, }, [, ], %, $, &, #, ký tự gạch nối ‘_’ và ký tự trắng ‘ ‘ ( space) Các chữ Ả rập: ,  ,  , không thuộc bộ ký tự của Pascal. 2. Từ khóa ( key word ): Có một số từ được Pascal dành riêng cho việc xây dựng các câu lệnh, các khai báo, các phép tính, gọi là từ khóa. Việc sử dụng các từ khóa đòi hỏi phải tuân thủ đúng quy tắc đề ra, và đặc biệt là người lập trình không được đặt một tên mới (tên biến, tên hằng, tên hàm, tên thủ tục, ) trùng với một trong các từ khóa. Dưới đây là danh sách các từ khóa của Pascal :
absolute, and, array, begin, case, const, div, do, downto, else, end, file, for, forward, function, goto, if, implementation, in, inline, interface, interrupt, label, mod, nil, not, of, or, packed, procedure, program, record, repeat, set, shl, shr, string, then, to, type, unit, until, uses, var, while, with, xor Các từ khóa có thể viết dưới dạng chữ hoa hay chữ thường hay xen kẽ chữ hoa với chữ thường đều được. Ví dụ viết begin hay Begin hay BEGIN là như nhau. 3. Tên (identifier): Các biến, các hằng, các hàm, các thủ tục, được sử dụng trong chương trình đều cần phải đặt tên, còn gọi là định danh hay danh hiệu. Các tên này do người thảo chương tự đặt và phải đảm bảo đúng quy tắc: tên phải bắt đầu bằng chữ cái, kế đó có thể là chữ cái, chữ số, hay dấu gạch nối ‘_’. Tên không được đặt trùng với từ khóa. Chiều dài của tên tối đa là 127 ký tự. Thông thường tên nên đặt ngắn gọn và có tính gợi nhớ. Dưới đây là ví dụ về các tên được đặt đúng: Delta, X1, X2, i, j , Chuc_vu, Luong, So_luong, Don_gia. Còn các tên: 3ABC, In, Chu vi, Ma-so là sai vì : 3ABC: bắt đầu bằng số Chu vi: có chứa ký tự trắng Ma-so : ký tự ‘-’ là dấu trừ chứ không phải gạch nối. In : trùng với từ khóa In Cũng giống như từ khóa, Tên không phân biệt viết hoa hay viết thường. Ví dụ viết X1 hay x1 cũng chỉ là một tên thôi. Trong Pascal có một số tên đã được đặt sẵn rồi, gọi là tên chuẩn, chẳng hạn : Abs, Arctan, Boolean, Byte, Char, Cos, Copy, Delete, Eof, False, Longint, Ord, Integer, Real, Readln, Writeln, True, Text, Mặc dù người thảo chương có thể đặt một tên mới trùng với một trong các tên chuẩn, song, để đỡ nhầm lẫn, chúng ta nên tránh điều này. III. CẤU TRÚC CHUNG CỦA CHƯƠNG TRÌNH PASCAL 1. Ví dụ mở đầu : Để có một cái nhìn tổng quan trước khi đi vào các vấn đề chi tiết của ngôn ngữ Pascal, xin hãy cùng xem chương trình sau: 1.1. Bài toán và chương trình : Viết chương trình để nhập vào độ dài hai cạnh của một hình chữ nhật, tính và in lên màn hình diện tích và chu vi của hình chữ nhật đó.
Nếu gọi hai cạnh của hình chữ nhật là a và b, gọi diện tích và chu vi lần lượt là S và P thì công thức tính S và P là: S = a.b P = 2(a+b) Chương trình cụ thể như sau :OGRAM VIDU51; { Tinh dien tich va chu vi hinh chu nhat } Uses CRT; Var a, b, S, P : Real ; Begin Clrscr; Write( ‘Nhap chieu dai : ‘); Readln(a); Write( ‘Nhap chieu rong : ‘); Readln(b); S:=a*b; P:=2* (a+b); Writeln (‘ Dien tich = ‘, S:8:2); Writeln (‘ Chu vi = ‘, P:8:2); Readln; End. Chay Chép chương trình nguồn VD52.PAS 1.2. Giải thích các dòng trong chương trình : { Tinh dien tich va chu vi hinh chu nhat } Đây là lời chú giải, nêu lên mục đích của chương trình. Uses CRT ;
Khai báo sử dụng thư viện CRT của Turbo Pascal. Var a, b, S, P : Real ; Khai báo 4 biến a, b, S, P có kiểu dữ liệu là số thực (Real). Begin Lệnh bắt đầu chương trình Clrscr ; Lệnh xóa màn hình. Write( ‘Nhap chieu dai: ‘); Lệnh in lên màn hình câu ‘ Nhap chieu dai: ‘ nhằm nhắc người dùng nhập vào số đo chiều dài. Readln(a) ; Lệnh nhập dữ liệu cho biến a. Write( ‘Nhap chieu rong : ‘); Lệnh in lên màn hình câu ‘Nhap chieu rong :’ nhằm nhắc người dùng nhập vào số đo chiều rộng. Readln(b); Lệnh nhập dữ liệu cho biến b. S := a* b; Lệnh tính diện tích S của hình chữ nhật. P := 2*(a+b); Tương tự, lệnh tính chu vi P của hình chữ nhật. Writeln(‘Dien tich = ‘, S:8:2); Lệnh này in lên màn hình câu ‘ Dien tich= ‘ , kế đó in gía trị của biến S. Chỉ thị S:8:2 ấn định dành 8 cột trên màn hình để in gía trị của S, trong đó có 2 cột để in phần thập phân. Writeln(‘ Chu vi = ‘, P:8:2); Lệnh này in lên màn hình câu ‘Chu vi = ‘, kế đó in gía trị của chu vi P có cả thảy 8 chữ số, trong đó có 2 số phần lẻ. Readln; Lệnh dừng màn hình để xem kết qủa chạy chương trình.
End. Dấu hiệu kết thúc chương trình. 1.3. Chạy minh họa chương trình : Để chạy chương trình mẫu nói trên, hãy nhắp vào mục Chay ở cuối chương trình đó. Nhưng trước hết xin xem phần hướng dẫn sau đây: Khi chương trình bắt đầu chạy, trên màn hình hiện lên lời nhắc : Nhap chieu dai : Bạn cần nhập số đo chiều dài từ bàn phím, chẳng hạn gõ số 8 và Enter : Nhap chieu dai : 8  Màn hình hiện tiếp lời nhắc : Nhap chieu rong : Bạn nhập số đo chiều rộng, chẳng hạn gõ số 6 và Enter : Nhap chieu rong : 6  Chương trình sẽ tính toán và in kết qủa lên màn hình như sau : Dien tich = 48.00 Chu vi = 28.00 Để kết thúc, hãy gõ phím Enter . 2. Cấu trúc chung của chương trình Pascal : Chương trình là một dãy các câu lệnh chỉ thị cho máy các công việc phải thực hiện. Một chương trình Pasccal đầy đủ gồm ba phần chính : Phần tiêu đề Phần khai báo Phần thân chương chình { Phần tiêu đề} { Phần khai báo  } Uses {khai báo sử dụng thư viện chuẩn} Label {khai báo nhãn}
Const {khai báo hằng} Type {khai báo kiểu dữ liệu} Var { khai báo biến} Function { khai báo các chương trình con} Procedure {hàm và thủ tục } { Phần thân chương trình  } Begin { Các lệnh } nd. Hình 5.1: Cấu trúc của chương trình Pascal 2.1. Phần tiêu đề chương trình : Phần này bắt đầu bằng từ khóa Program, sau đó ít nhất là một khoảng trắng và một tên do người dùng tự đặt, cuối cùng kết thúc bằng dấu chấm phẩy ‘;’. Ví dụ : Program Btap1; hoặc : Program Giai_pt_bac2; Phần tiêu đề chiếm một dòng, còn gọi là phần đầu của chương trình, nó có thể không có cũng được. 2.2. Phần khai báo : Phần khai báo có nhiệm vụ giới thiệu và mô tả các đối tượng, các đại lượng sẽ tham gia trong chương trình, giống như ta giới thiệu các thành viên trong một cuộc họp. Nó gồm khai báo sử dụng thư viện chuẩn, khai báo nhãn, khai báo hằng, khai báo kiểu dữ liệu mới, khai báo biến, và khai báo các chương trình con. Tùy theo yêu cầu cụ thể mà mỗi khai báo này có thể có hoặc không. Khai báo nhãn (Label) chỉ dùng khi trong chương trình có sử dụng lệnh nhảy vô điều kiện GOTO. Nhược điểm của lệnh GOTO là làm mất tính cấu trúc của chương trình, trong khi có thể thay thế nó bằng các câu lệnh có cấu trúc của Pascal. Vì thế, để rèn luyện kỹ năng lập trình có cấu trúc, chúng ta sẽ không dùng lệnh GOTO trong giáo trình này. Các thủ tục và hàm được dùng khi có nhu cầu thiết kế các chương trình lớn, phức tạp. Đối với các bài toán nhỏ, đơn giản, việc sử dụng chương trình con là chưa cần thiết. Chi tiết về phần này sẽ được trình bày kỹ trong bài 12. Sau đây ta điểm qua vài nét về các khai báo thông dụng nhất. a) Khai báo hằng và khai báo biến :
Biến là đại lượng có gía trị thay đổi được, còn Hằng là đại lượng có gía trị không đổi, chúng được dùng trong chương trình để lưu trữ các dữ liệu, tham gia vào các biểu thức tính toán và các quá trình xử lý trong máy. Việc khai báo có tác dụng xác định tên và kiểu dữ liệu của biến hay hằng. Biến và Hằng là những thành phần khó có thể thiếu được trong một chương trình. Để khai báo biến ta dùng từ khóa Var, để khai báo hằng ta dùng từ khóa Const, ví dụ: Const N=10 ; Var x, y : Real ; i, k : Integer ; b) Khai báo (định nghĩa) một kiểu dữ liệu mới: Ngoài các kiểu dữ liệu mà bản thân ngôn ngữ đã có sẵn như kiểu thực, kiểu nguyên, kiểu ký tự, kiểu lôgic,.v.v. người dùng có thể tự xây dựng các kiểu dữ liệu mới phục vụ cho chương trình của mình, nhưng phải mô tả sau từ khóa TYPE. Khi đã định nghĩa một kiểu dữ liệu mới, ta có thể khai báo các biến thuộc kiểu dữ liệu này. Ví dụ, ta định nghĩa một kiểu dữ liệu mới có tên là Mang : Type Mang = Array[1 10] of Real; Bây giờ có thể khai báo hai biến A và B có kiểu dữ liệu là kiểu Mang : Var A, B : Mang ; c) Khai báo sử dụng thư viện chuẩn: Turbo Pascal có sẵn một số hàm và thủ tục chuẩn, chúng được phân thành từng nhóm theo chức năng mang các tên đặc trưng, gọi là các thư viện hay đơn vị chương trình ( Unit ), như : Crt, Graph, Dos, Printer, .v.v. . Muốn sử dụng các hàm hay thủ tục của thư viện nào, ta phải khai báo có sử dụng thư viện đó, lời khai báo phải để ở ngay sau phần tiêu đề của chương trình theo cú pháp : Uses danhsáchthư viện ; Ví dụ: do thủ tục Clrscr nằm trong thư viện CRT, nên nếu trong chương trình mà có dùng lệnh Clrscr, thì phải khai báo : Uses CRT ; Muốn sử dụng cả hai thư viện CRT và GRAPH, ta khai báo : Uses CRT, GRAPH ; 2.3. Phần thân chương trình :
Đây là phần chủ yếu nhất của một chương trình, bắt buộc phải có. Thân chương trình bắt đầu bằng từ khóa BEGIN và kết thúc bằng END. (có dấu chấm ở cuối). Giữa khối BEGIN và END là các lệnh. Mỗi lệnh phải kết thúc bằng dấu chấm phẩy ‘;’. Một lệnh, nếu dài, thì có thể viết trên hai hay nhiều dòng, ví dụ : Writeln(‘ Phuong trinh co hai nghiem la X1= ‘, X1:8:2,‘ va X2= ‘, X2:8:2) ; Ngược lại, một dòng có thể viết nhiều lệnh miễn là có dấu ‘;’ để phân cách các lệnh đó, chẳng hạn : Write(‘ Nhap A, B, C: ‘ ) ; Readln(A,B,C) ; Thông thường mỗi dòng chỉ nên viết một lệnh để dễ đọc, dễ kiểm tra lỗi. 3. Ví dụ 2 : Để kết thúc phần này, xin giới thiệu chương trình cho phép nhập vào họ tên, mã số, các điểm Toán, Lý của một sinh viên, tính điểm trung bình theo công thức : rồi in Họ tên, mã số, các điểm Toán, Lý và điểm trung bình của sinh viên đó lên màn hình. PROGRAM VIDU52; Uses CRT; Var Ho_ten, Maso : String[20]; Toan, Ly, Dtb : Real; Begin Write(‘ Nhap Ho va ten : ‘); Readln(Ho_ten); Write(‘ Nhap ma so : ‘); Readln(Maso); Write(‘ Nhap diem Toan : ‘); Readln(Toan); Write(‘ Nhap diem Ly : ‘); Readln(Ly); Dtb:= (Toan+Ly) / 2; { In lên màn hình các dữ liệu về sinh viên } TextMode(C40); { đặt mode C40 cho màn hình } TextBackGround(Green); { đặt màu nền là Green }
TextColor(Red); { đặt màu chữ là Red} Clrscr ; Writeln(‘ KET QUA THI CUA SINH VIEN:’); Writeln(‘Ho va ten : ‘, Ho_ten); Writeln(‘Ma so : ‘, Maso); Writeln(‘Diem Toan : ‘, Toan:3:1); Writeln(‘Diem Ly : ‘, Ly:3:1); Writeln(‘Diem Tbinh : ‘, Dtb:3:1); Readln; TextMode(C80); { đặt trả lại mode C80 cho màn hình} END. Chạy Chép chương trình nguồn VD52.PAS Trong chương trình này có sử dụng bốn thủ tục đều thuộc thư viện CRT, đó là : Clrscr : xóa màn hình TextMode(C40) và TextMode(C80) : chuyển màn hình sang chế độ bề ngang 40 cột (chữ to) hoặc 80 cột (chữ bình thường). TextBackGround(tênmàu) : đặt lại màu nền của màn hình. TextColor(tênmàu) : đặt lại màu chữ trên màn hình. Tên màu có thể là một số từ 0 đến 15 hoặc có thể viết trực tiếp bằng tiếng Anh như : White, Black, Green, Red, Blue, Bạn có thể chạy minh họa chương trình này bằng cách nhắp chọn vào mục Chay ở cuối chương trình . Cách nhập dữ liệu tương tự như ví dụ trước. Chẳng hạn ta nhập họ tên là Nguyen Van An, mã số là 1990064, điểm toán là 6, điểm lý là 7 như dưới đây : Nhap Ho va ten : Nguyen Van An  Nhap ma so : 1990064  Nhap diem Toan : 6 
Nhap diem Ly : 7  Chương trình sẽ tính điểm trung bình và in kết qủa như sau: KET QUA THI CUA SINH VIEN: Ho va ten : Nguyen Van An Ma so : 1990064 Diem Toan : 6.0 Diem Ly : 7.0 Diem Tbinh : 6.5 Hãy Enter để kết thúc và trở lại màn hình ban đầu. Để soạn và chạy được một chương trình như trên cần phải biết sử dụng phần mềm Turbo Pascal ( viết tắt là TP ). IV. SỬ DỤNG PHẦN MỀM TURBO PASCAL 1. Giới thiệu Turbo Pascal: Turbo Pascal là một phần mềm có nhiệm vụ giúp người thảo chương soạn thảo và thực hiện các chương trình viết bằng ngôn ngữ Pascal. Các chức năng chính của Turbo Pascal là : Cung cấp một hệ soạn thảo văn bản cho phép người thảo chương soạn và sửa chương trình dễ dàng, tiện lợi. Giúp người thảo chương tìm các lỗi về văn phạm trong chương trình. Dịch (compiler) chương trình viết bằøng ngôn ngữ Pascal thành một chương trình viết dưới dạng mã máy. Thực hiện hay chạy ( Run ) chương trình viết bằng ngôn ngữ Pascal. Cung cấp các thư viện có sẵn nhiều hàm (function) và thủ tục (procedure) chuẩn mang lại cho người thảo chương nhiều công cụ hữu ích, làm giảm bớt khối lượng phải lập trình. Là sản phẩm của hãng Borland nổi tiếng, Turbo Pascal (viết tắt là TP) không ngừng được cải tiến, đến nay đã ra đời version 7.0. Tuy nhiên, ở mức độ thảo chương căn bản, người ta vẫn thích dùng phiên bản 5.5 hoặc 6.0 vì nó đơn giản mà đủ dùng, tốc độ nhanh hơn, thích hợp với các máy có cấu hình chưa mạnh. 2. Khởi động Turbo Pascal: Trong phần này sẽ trình bày cách sử dụng Turbo Pascal 6.0. Người đọc có thể tự mình suy ra cách sử dụng Turbo Pascal 5.5 hay 7.0, vì vềø cơ bản chúng giống với phiên bản 6.0. 2.1. Các tập tin chính của Turbo Pascal:
Để chạy được Turbo Pascal 6.0, chỉ cần hai tập tin sau là đủ : TURBO.EXE : tập tin chính của TP TURBO.TPL : tập tin chứa các thư viện của TP Nếu muốn vẽ đồ họa thì phải có thêm các tập tin: GRAPH.TPU, tập tin chứa thư viện đồ họa *.BGI : các tập tin màn hình đồ họa *.CHR : các tập tin tạo kiểu chữ Trong các tập tin màn hình đồ họa thì thông thường chỉ cần tập tin EGAVGA.BGI là đủ, vì ngày nay phần lớn màn hình đều có kiểu EGA hay VGA. Nếu muốn xem hướng dẫn sử dụng Turbo Pascal thì cần có thêm tập tin TURBO.HLP Thông thường các tập tin này được để trong một thư mục riêng có tên là TP, hay TP6. Dưới đây ta giả thiết thư mục chứa Turbo Pascal là TP nằm ngay tại gốc của đĩa cứng C hay đĩa mềm A. 2.2. Khởi động Turbo Pascal: a) Nếu bạn làm việc trên máy cá nhân hoặc trong một mạng có hệ điều hành là MSDOS thì sau khi khởi động máy xong: Trường hợp dễ nhất là máy của bạn đã thiết lập sẵn đường dẫn đến thư mục TP chứa Turbo Pascal thì bạn chỉ cần gõ một lệnh : TURBO  Trên màn hình sẽ hiện ra cửa sổ soạn thảo như hình 5.2 . Nếu gõ lệnh trên mà cửa sổ Turbo Pascal không hiện ra, do máy của bạn chưa thiết lập đường dẫn đến thư mục TP, trường hợp này bạn phải di chuyển vào thư mục TP bằng lệnh : CD \TP rồi sau đó gõ tiếp : TURBO 
b) Nếu bạn làm việc trên máy cá nhân hoặc trong một mạng có hệ điều hành là WINDOWS 95 hoặc mới hơn, thì sau khi khởi động WINDOWS 95 : Trường hợp có sẵn một Shortcut chứa Turbo Pascal ở trên Desktop : hãy nhắp left mouse hai lần liên tiếp vào biểu tượng Shortcut của Turbo Pascal. Trường hợp không có sẵn một Shortcut chứa Turbo Pascal: hãy chọn lệnh Start, chọn tiếp lệnh Run, rồi gõ vào đường dẫn đầy đủ của tập tin TURBO.EXE, chẳng hạn: C:\TP\TURBO.EXE  , nếu khởi động TP từ đĩa C. A:\TP\TURBO.EXE  , nếu khởi động TP từ đĩa A. 2.3. Cửa sổ Turbo Pascal và cách chọn lệnh : Trong cửa sổ này, dòng trên cùng là một thực đơn ngang, liệt kê chín nhóm lệnh chính của TP. Muốn chọn một lệnh trong thực đơn này, có thể tiến hành theo một trong hai cách: Cách một: Gõ phím F10. Lúc này, trên thực đơn xuất hiện một khung sáng (thường là màu xanh). Muốn chọn lệnh nào thì gõ các phím mũi tên  , dời khung sáng đến lệnh đó rồi Enter. Một thực đơn con của lệnh vừa chọn hiện ra, gọi là thực đơn dọc. Ví dụ, khi chọn lệnh File, ta được thực đơn con như sau:
Để chọn một lệnh trong thực đơn dọc, hãy gõ các phím mũi tên ,  dời khung sáng đến lệnh đó rồi Enter. Khi không muốn chọn lệnh nào thì gõ phím ESC để trở về vùng soạn thảo. Ngoài cách dùng phím F10 nói trên, cũng có thể chọn một lệnh trong thực đơn ngang bằng cách gõ đồng thời phím Alt với phím chữ cái đầu tiên của tên lệnh muốn chọn. Ví dụ, muốn chọn lệnh File thì gõ đồng thời hai phím Alt và F (viết tắt là Alt-F), tương tự, muốn chọn lệnh Compile thì gõ Alt- C. Cách hai: dùng phím "nóng": Có một số lệnh được gán cho những phím đặc biệt gọi là phím "nóng", ví dụ lệnh Open: F3, lệnh Save : F2, lệnh Exit : Alt-X. Để thực hiện những lệnh này, thay vì phải chọn nó từ trong thực đơn, ta chỉ cần gõ phím nóng tương ứng với nó. Ví dụ, thay vì chọn lệnh Open thì gõ phím F3, thay vì chọn lệnh Save thì gõ phím F2, Dưới thực đơn ngang là vùng soạn thảo dùng để gõ chương trình vào. Đầøu của vùng này hiện tên của tập tin đang soạn, và nếu người thảo chương chưa đặt tên thì TP sẽ đặt giùm một tên mặc nhiên là NONAME00.PAS. Dòng cuối cùng tóm tắt một số phím " nóng" hay dùng, như phím F1 để xem hướng dẫn, phím F2 để lưu tập tin lên đĩa, phím F3 dùng để mở xem một tập tin, phím F10 để khởi động thực đơn,.v.v. 2.4. Thoát khỏi Turbo Pascal: Chọn lệnh File trong thực đơn ngang, chọn tiếp lệnh Exit trong thực đơn dọc (viết gọn là chọn lệnh File/ Exit). Nếu làm việc trong TP 5.5 thì chọn lệnh File/ Quit. Hoặc gõ cặp phím nóng Alt-X 3. Các bước thực hiện một chương trình Pascal: Để soạn và chạy một chương trình Pascal trong Turbo Pascal, nên tiến hành các bước như sau: Bước 1: Khởi động Turbo Pascal
Bước 2: Đặt tên cho tập tin sẽ soạn : Chọn lệnh File/ Open (nếu làm việc trong TP 5.5 thì chọn lệnh File/ Load) hoặc gõ phím F3, sau đó gõ tên tập tin (không cầøn gõ phần đuôi) vào trong khung vừa hiện ra, ví dụ : Khi đó tên BTAP1.PAS sẽ hiện ra ở đầu vùng soạn thảo. Đuôi PAS được TP tự động gắn thêm vào. Tập tin BTAP1.PAS sẽ được lưu trong thư mục hiện thời. Nếu muốn tập tin BTAP1.PAS được lưu lên đĩa A thì khi nhập tên tập tin ta nên gõ thêm tên ổ đĩa ở đằng trước, ví dụ : Bước 3: Soạn thảo ( gõ ) chương trình . Bạn hãy gõ chương trình mẫu sau vào vùng soạn thảo của Turbo Pascal :
Bước 4: Dịch và sửa lỗi: Chọn lệnh Compile/ Compile (hoặc gõ cặp phím Alt-F9, hay đơn giản chỉ gõ phím F9 cũng được). Máy sẽ dịch chương trình sang mã máy, nếu gặp lỗi thì dừng và hiện thông báo lỗi màu đỏ ở đầu màn hình, đồøng thời con trỏ đặt ở vị trí có lỗi. Người thảo chương phải tự mình sửa lỗi, rồi gõ Alt- F9 để dịch và sửa lỗi tiếp cho đến khi hết lỗi. Dấu hiệu cho biết việc dịch đã xong là màn hình xuất hiện cửa sổ thông báo có dòng chữ đặc trưng là: Bước 5: Lưu trữ chương trình lên đĩa: chọn lệnh File/ Save hoặc gõ phím F2. Bước 6: Chạy thử chương trình: Chọn lệnh Run/ Run hoặc gõ phím nóng Ctrl-F9 (viết tắt là ^F9). Mỗi lần chạy thử, ta cần nhập một bộ dữ liệu cụ thể và kiểm tra xem kết qủa in lên màn hình có đúng không. Cần phải chạy thử một số lần ứng với các bộ dữ liệu khác nhau. Nếu kết qủa các lần chạy thử đều đúng thì chương trình đã hoàn thành. Ngược lại, nếu có một lần chạy thử cho kết qủa sai thì chương trình chưa ổn, cần phải sửa lại thuật toán của chương trình. Ví dụ : Để chạy thử chương trình mẫu trên, hãy gõ ^F9 và nhập vào chiều dài 10, chiều rộng 7, như sau : Nhap chieu dai : 10  Nhap chieu rong : 7  Chương trình sẽ in kết qủa lên màn hình :
Dien tich = 70.00 Chu vi = 34.00 Hãy Enter để trở lại màn hình soạn thảo. Việc chạy thử với bộ dữ liệu khác, xin dành cho độc giả. Bước 7: Nếu chương trình chạy đúng thì gõ phím F2 để lưu nó lên đĩa lần cuối. Bây giờ có thể lặp lại từ bước 2 để soạn một chương trình mới. 4. Mở xem một chương trình cũ : Muốn xem lại một chương trình đã có trên đĩa, hãy chọn lệnh File/ Open hoặc gõ phím F3, trong khung có tiêu đều là Name, gõ vào *.PAS  (hoặc A:*.PAS  nếu tập tin nằm trên đĩa A), một danh sách các tập tin có đuôi PAS sẽ hiện ra trong khung phía dưới cho ta chọn ( hình 5.4) : Dùng các phím mũi tên  , , , để di chuyển và đặt thanh sáng vào tên muốn chọn rồi Enter. Nội dung tập tin này sẽ được đưa lên màn hình cho chúng ta xem, sửa, chạy thử, .v.v. Chú ý rằng trong TP từ 6.0 trở lên, để đưa con trỏ từ hộp Name ở trên xuống hộp Files ở dưới, dùng phím Tab, từ hộp File về lại hộp Name : gõ Shift_Tab . 5. Lưu tập tin sang đĩa khác : Khi cần ghi tập tin đang soạn từ đĩa cứng sang đĩa A, có thể làm như sau: Chọn lệnh File/ Save as (nếu làm việc trong TP 5.5 thì chọn lệnh File/ Write to ). Trong khung hiện ra , hãy gõ tên tập tin vào, nhớ gõ thêm tên đĩa A: ở đằng trước: Name: A:\BTAP.PAS Từ nay, mỗi khi gõ phím F2 hoặc chọn lệnh File/ Save, tập tin BTAP1.PAS sẽ được ghi lên đĩa A.
6. Một vài kỹ thuật trong soạn thảo : 6.1. Thao tác trên khối: Ta gọi khối là một đoạn văn bản gồm một hay nhiềøu dòng liên tiếp. Ký tự đầu tiên của khối gọi là đầu khối, ký tự cuối cùng của khối gọi là cuối khối. Dưới đây là một khối gồm hai dòng lệnh: Write(‘ Nhap chieu dai va chieu rong hinh chu nhat: ‘); Readln(a,b); a) Đánh dấu khối: Đưa con trỏ về đầu khối Một tay đè phím Shift, trong khi tay kia gõ các phím mũi tên  , , , kéo vùng sáng phủ đến cuối khối. Nếu làm việc trong TP 5.5 thì đánh dấu khối bằng cách: đưa con trỏ vềø đầu khối, gõ ^K_B, sau đó đưa con trỏ về cuối khối, gõ ^K_K. (Cách gõ ^K_B: một tay đè phím Ctrl trong khi tay kia gõ liên tiếp hai phím K và B). b) Sao chép khối: Đánh dấu khối cần sao chép Đưa con trỏ đến nơi cần chép tới Gõ lệnh ^K_C c) Di chuyển khối: Đánh dấu khối cần di chuyển Đưa con trỏ đến nơi cần chuyển khối tới Gõ lệnh ^K_V d) Xóa khối: Đánh dấu khối cần xóa Gõ lệnh ^K_Y e) Che hoặc hiện lại khối đã đánh dấu : lệnh ^K_H 6.2. Các phím lệnh soạn thảo thông dụng: Phím Home : đưa con trỏ về đầu dòng hiện thời Phím End : đưa con trỏ về cuối dòng hiện thời
Phím Delete : xóa ký tự ngay tại vị trí con trỏ. Nếu con trỏ đang đứng ở cuối của dòng trên mà gõ phím Delete thì sẽ nối dòng dưới vào cuối dòng trên. Phím Back Space ( là phím mũi tên  nằm ngay phía trên phím Enter) : xóa ký tự bên trái con trỏ. Nếu con trỏ đang đứng ở đầu của dòng dưới mà gõ phím Back Space thì sẽ nối dòng dưới vào cuối dòng trên. Cặp phím Ctrl_Y : xóa toàn bộ dòng hiện thời và đôn các dòng ở dưới lên. Nhóm phím Ctrl_Q_Y : xóa từ vị trí con trỏ đến cuối dòng. Các phím  , , , : dời con trỏ theo hướng mũi tên. Phím Insert : mở hoặc tắt chế độ viết chèn. Ở chế độ viết chèn, con trỏ màn hình có dạng bình thường, tắt chế độ viết chèn, con trỏ có kích thước lớn gấp 4 lần bình thường. (Trong TP 5.5, chế độ viết chèn hay tắt viết chèn được nhận biết bằng việc chữ Insert có hiện ra hay không hiện ra ở đầu của cửa sổ soạn thảo). Phím Enter : Trong chế độ viết chèn: gõ Enter có tác dụng đưa con trỏ xuống đầu dòng dưới, do đó toàn bộ các chữ đứng sau con trỏ (nếu có) sẽ bị cắt xuống dòng dưới. Khi con trỏ đang đứng ở đầøu một dòng mà Enter thì sẽ tạo ra một dòng trống ngay tại vị trí đó. Nếu chế độ viết chèn là tắt thì mỗi khi gõ phím Enter, con trỏ sẽ về đầu của dòng hiện thời (dòng đang chứa con trỏ), chứ không xuống dòng dưới nữa. Chú ý: Trong Turbo Pascal không dùng chữ có dấu tiếng Việt. Tuy nhiên trong các chương trình mẫu ở giáo trình này thỉnh thoảng vẫn viết những chữ có dấu là để dễ đọc, dễ hiểu. Khi soạn trong Turbo Pascal xin hãy bỏ dấu đi. V. CÂU HỎI TRẮC NGHIỆM Trong các câu hỏi dưới đây, hãy chọn một câu trả lời thích hợp nhất: Câu 1: Tính cấu trúc của ngôn ngữ Pascal được thể hiện : a) trong việc tổ chức các dữ dtệu; b) trong việc tổ chức các câu lệnh; c) trong việc tổ chức chương trình; d)ở cả ba mục a), b), c) ; Câu 2: Ðiều gì làm cho Pacal được đánh gía cao và trở thành một trong những ngôn ngữ thảo chương phổ biến nhất hiện nay ? a) Nó là ngôn ngữ đầu tiên đưa ra và thể hiện được khái niệm lập trình có cấu trúc.; b) Nó là một ngôn ngữ chặt chẽ cả về mặt cú pháp và về mặt dữ liệu;
c) Nó là ngôn ngữ có văn phạm sáng sủa, dễ hiểu, có khả năng đủ mạnh; d)Cả ba điều nêu trong các mục a), b), c) ; Câu 3: Khẳng định nào đúng: a) VAR , BEGIN, end là các từ khóa của Pascal được khái niệm lập trình có cấu trúc.; b) Các ký hiệu a , b , g , d đều thuộc bộ ký tự cơ bản của Pascal; c) Var, begin, Integer, Real là các từ khóa của Pascal; d)VAR, Var, vaR, var là các từ khóa khác nhau của Pascal ; Câu 4: Tên nào đặt Sai quy định của Pascal: a) Giai_Ptrinh_Bac_2; b) Ngaysinh; c) Noi sinh; d)Sv2000 ; Câu 5: Mục nào có các Tên đều đặt đúng quy định của Pascal: a) x1 , X-2 ; b) Xx1 , X2; c) CONST , X_234; d)X[1], x2 ; Câu 6: Chọn câu Sai : trong một chương trình Pascal, có thể không có : a) phần thân chương trình ; b) phần khai báo biến; c) phần đầu chương trình; d)phần khai báo hằng ; Câu 7: Dấu hiệu kết thúc chương trình Pascal là : a) End; b) END; c) end. d) End ! ; Câu 8: Trong Pascal, lệnh nào có tác dụng xóa màn hình : a) CLRSSR ; b) CLRSR;
c) Clrscl; d) Clrscr ; Câu 9: Trong Pascal, nếu muốn dùng lệnh xóa màn hình Clrscr thì phải khai báo thế nào ở ngay sau phần tiêu đề chương trình : a) Uses CRT ; b) USES Graph; c) use CRT ; d) không khai báo gì ca ; Câu 10: Khẳng định nào Sai: trong Turbo Pascal, a) để lưu chương trình lên đĩa, gõ phím F2 hoặc chọn lệnh File / Save ; b) để mở một tập tin cũ, gõ phím F1; c) để tìm lỗi cú pháp của chương trình, gõ phím Alt_F9, hay F9 ; d) để chạy chương trình, gõ phím ^F9 hoặc chọn lệnh Run / Run ; VI. BÀI TẬP Câu 1. Soạn và chạy thử chương trình trong ví dụ mở đầu ở mục 5.3.1 Câu 2. Soạn và chạy thử chương trình trong ví dụ 2 ở mục 5.3.3 Câu 3. Viết chương trình nhập vào số đo một cạnh và diện tích của hình chữ nhật, tính cạnh kia và chu vi của hình chữ nhật. Câu 4. Viết chương trình in lên màn hình hai câu sau : " Chao cac ban ! " " Rat vui đuoc lam quen voi cac ban ! " Câu 5. Viết chương trình nhập hai số bất kỳ x và y, tính và in lên màn hình tổng x+y, hiệu x-y và tích x*y của hai số đó. 6.1. KHÁI NIỆM VỀ KIỂU DỮ LIỆU 6.1.1 Khái niệm : Chức năng của máy điện toán là xử lý các thông tin. Các thông tin được nhập và lưu trữ trong bộ nhớ của máy dưới các dạng khác nhau: có thể là số, là chữ, có thể là hình ảnh, âm thanh,.v.v. mà thuật ngữ tin học gọi chung là dữ liệu. Tính đa dạng của dữ liệu đòi hỏi phải tổ chức và phân phối bộ nhớ thích hợp để lưu trữ và xử lý tốt các dữ liệu. Ngôn ngữ thảo chương chia các dữ liệu thành từng nhóm riêng trên đó xây dựng một số phép toán tạo nên các kiểu dữ liệu khác nhau, mỗi kiểu dữ liệu là một tập hợp các gía trị mà một biến thuộc kiểu đó có thể nhận. Khi một biến được khai báo
thuộc kiểu dữ liệu nào thì máy sẽ dành cho biến đó một dung lượng thích hợp trong bộ nhớ để có thể lưu trữ các gía trị thuộc kiểu dữ liệu đó. 6.1.2 Phân loại kiểu dữ liệu : Các kiểu dữ liệu trong ngôn ngữ Pascal được chia ra thành hai loại chính: loại đơn giản và loại có cấu trúc. Mỗi kiểu dữ liệu đơn giản là một tập các giá trị cơ sở có thứ tự. Ví dụ kiểu Integer gồm các số nguyên nằm trong phạm vi từ -32768 đến 32767 và có thứ tự tự nhiên : -32768< < -1 < 0 < 1 < < 32767 , kiểu lô gic chỉ có hai gía trị False, True với quy ước False < True. Các kiểu dữ liệu có cấu trúc được xây dựng từ các kiểu dữ liệu đơn giản. Mỗi kiểu dữ liệu có cấu trúc là một tập các phần tử thuộc kiểu dữ liệu đơn giản được tổ chức lại theo một quy tắc nhất định . Các kiểu dữ liệu đơn giản gồm có: kiểu nguyên, kiểu thực, kiểu lô gic, kiểu ký tự, kiểu liệt kê và kiểu đoạn con. Các kiểu dữ liệu có cấu trúc gồm có :kiểu mảng, kiểu bản ghi, kiểu tập hợp và kiểu tập tin . Riêng chuỗi ký tự (STRING) là một kiểu dữ liệu đặc biệt, vừa có tính đơn giản lại vừa có tính cấu trúc. Mỗi chuỗi có thể xem là một gía trị, nhưng cũng có thể xem là một mảng các gía trị kiểu ký tự. Vì vậy, việc sử dụng chuỗi cũng có hai mức khác nhau: mức đơn giản và mức có cấu trúc. Các kiểu dữ liệu đơn giản còn được phân thành hai loại: đếm được (Ordinal type) và không đếm được. Kiểu thực thuộc loại không đếm được, các gía trị của nó dày đặc. Tất cả các kiểu dữ liệu đơn giản còn lại : nguyên, ký tự, lô gic, liệt kê và đoạn con đều thuộc loại đếm được (còn gọi là rời rạc). Dưới đây sẽ lần lượt trình bày kỹ về 4 kiểu dữ liệu đơn giản chuẩn và thông dụng: kiểu nguyên, kiểu thực, kiểu logic, kiểu ký tự . Kiểu chuỗi được giới thiệu để có thể sử dụng ngay ở mức đơn giản. 6.2. KIỂU SỐ NGUYÊN 6.2.1. Các kiểu số nguyên : Tên kiểu Phạm vi gía trị Số byte ShortInt -128 127 1 Byte 0 255 1 Integer -32768 32767 2 Word 0 65535 2 LongInt -2147483648 2147483647 4 Bảng 6.1
Ngoài kiểu Integer là thông dụng nhất, các số nguyên còn được chia ra thành 4 kiểu nữa đó là: Byte, Word, ShortInt và LongInt. Bảng 6.1 liệt kê chi tiết về tên gọi, phạm vi gía trị và độ dài tính theo đơn vị byte của từng kiểu nguyên. Các biến nguyên chỉ có thể nhận các gía trị là các số nguyên nằm trong phạm vi gía trị của biến đó. Khi gán cho một biến một số nguyên nằm ngoài phạm vi của biến thì máy sẽ báo lỗi: "Const out of range". Ví dụ, cho khai báo : Var i : Byte; N : Integer; thì các lệnh đưới đây là đúng: i:= 200; N:= -1500; còn các lệnh dưới đây là bị lỗi : i:= -5; N:= 50000; Ðặc biệt không thể gán một số thực cho một biến nguyên. Câu lệnh sau là sai : N:= 12.5 ; Khi gặp tình huống này, máy sẽ báo lỗi "Type mismatch". Chú ý: Các số nguyên hệ thập lục phân (hệ 16) được biểu diễn bằng cách viết thêm dấu $ ở trước số, ví dụ ba số dưới đây : $A , $FF và $10 là các số nguyên viết trong hệ 16. Chúng có gía trị tương ứng trong hệ 10 là: 10 , 255 và 16 6.2.2. Các phép toán số học trên số nguyên: Phép cộng và trừ : ký hiệu + và - như thường lệ. Phép nhân : ký hiệu bằng dấu *, ví dụ 4*2 cho kết qủa là 8. Phép chia : ký hiệu bằng dấu / , ví dụ 6/4 cho kết qủa là 1.5. Phép chia lấy phần nguyên : ký hiệu bằng từ khóa DIV.
Phép lấy phần dư nguyên của phép chia: ký hiệu bằng từ khóa MOD. Ví dụ: 15 DIV 6 cho kết qủa là 2. 15 MOD 6 cho kết qủa là 3. Các phép toán trên đều cho kết qủa là các số nguyên, trừ ra phép chia ( / ) luôn cho kết qủa là một số thực. Vì thế nếu N là một biến nguyên, mà gán : N:= 20/5; thì máy sẽ báo lỗi, bởi vế phải có gía trị kiểu thực (=4.0) mặc dù phần lẻ bằng không. Nhận xét : số nguyên N là chẵn nếu N mod 2 = 0 (tức N chia hết cho 2), ngược lại, là lẻ nếu N mod 2 trong Pascal có nghĩa là khác nhau ). Thứ tự thực hiện các phép toán cũng giống như thường lệ: Các biểu thức trong ( ) được tính trước tiên Kế đến là *, /, div, mod Sau cùng là +, - Ðối với các phép toán cùng thứ tự mà đứng liền nhau thì phép toán nào đứng trước được làm trước. Ví dụ: tính biểu thức sau : 15 mod (2 +4) * 20 div (10 div 4) + 40 mod ( 5* 3) =15 mod 6 * 20 div 2 + 40 mod 15 = 3 * 20 div 2 + 10 = 60 div 2 + 10 = 30 + 10 = 40 Ví dụ sau đây là một ứng dụng của các phép toán div, mod : Ví dụ 6.1: Nhập một số tiền N đồng, đổi ra xem được bao nhiêu tờ 5 đồng, bao nhiêu tờ 2 đồng, bao nhiêu tờ 1 đồng sao cho tổng số tờ là ít nhất. Ví dụ N=43 đ = 8 tờ 5 đ + 1 tờ 2 đ + 1 tờ 1 đ. Cách tính như sau : Số tờ 5 đ = 43 div 5 = 8 Số tiền dư = 43 mod 5 = 3
Số tờ 2 đ = Số tiền dư div 2 = 3 div 2 =1 Số tờ 1 đ = Số tiền dư mod 2 = 3 mod 2 = 1 Dưới đây là chương trình cụ thể : PROGRAM VIDU61; { Ðổi tiền } Var N, st5, st2, st1, sodu : LongInt; Begin Write(‘ Nhap so tien : ’); Readln(N); st5 := N div 5; Sodu := N mod 5; { tính phần dư } st2 := Sodu div 2; st1 := Sodu mod 2; Writeln(‘ KET QUA DOI TIEN LA: ’ ) ; Writeln(‘ So to 5đ= ‘, st5); Writeln(‘ So to 2đ= ‘, st2); Writeln(‘ So to 1đ=‘, st1); Readln; End. Chạy Chép tập tin nguồn 6.2.3. Các phép toán so sánh : Ngôn ngữ Pascal có sáu phép toán so sánh được liệt kê trong bảng 6.2 . Ký hiệu Ý nghĩa Ví dụ = bằng nhau x=y y
lớn hơn x>y >= lớn hơn hoặc bằng x>=y Bảng 6.2 Kết qủa của các biểu thức so sánh là một gía trị lôgic Ðúng (TRUE) hoặc Sai (FALSE). Ví dụ: Biểu thức 5*2=10 cho kết qủa là TRUE. Biểu thức 5+2 10 div 3 cho kết qủa là FALSE. 6.2.4. Các phép toán lôgic trên số nguyên : Các phép tính NOT, AND, OR, XOR xử lý các bít nhị phân được xác định như sau ( bảng 6.3 ): NOT 1 = 0 1 AND 1=1 1 OR 1=1 1 XOR 1=0 NOT 0 = 1 1 AND 0=0 1 OR 0=1 1 XOR 0=1 0 AND 1=0 0 OR 1=1 0 XOR 1=1 0 AND 0=0 0 OR 0=0 0 XOR 0=0 Bảng 6.3 Mỗi số nguyên được biểu diễn trong máy dưới dạng một dãy các bít nhị phân. Số kiểu Integer được biểu diễn bằng 16 bit. Ví dụ, số 1 và số 2 có biểu diễn trong máy lần lượt là : 0000 0000 0000 0001 0000 0000 0000 0011 Phép lấy NOT một số nguyên sẽ đảo tất cả các bít biểu diễn số nguyên đó, tức là 0 thành 1, còn 1 thành 0. Ví dụ: NOT 1 = 1111 1111 1111 1110 NOT 2 = 1111 1111 1111 1100 Phép lấy AND, OR, XOR hai số nguyên được tiến hành bằng cách AND, OR, XOR từng cặp bít tương ứng của hai số đó, ví dụ: 1 OR 2 = 0000 0000 0000 0011= 2 1 AND 2 = 0000 0000 0000 0001= 1
6.2.5. Các phép dịch chuyển số học SHR và SHL : N SHR k : dịch các bít của số nguyên N sang phải đi k bít. N SHL k : dịch các bít của số nguyên N sang trái đi k bít. Có thể chứng minh được : N SHR k = N div 2k N SHL k = N * 2k Ví dụ: 120 shr 4 = 7, vì : 120 shr 4 = 120 div 24 = 120 div 16 = 7. 120 shl 3 = 960, vì : 120 shl 3 = 120 * 23 = 120 * 8 = 960. Hai phép toán SHR và SHL được dùng khi muốn tăng tốc độ tính toán trên các số nguyên. 6.2.6. Các hàm có đối số nguyên : Hàm PRED(k) : đối số k nguyên, trả về số nguyên đứng ngay trước k, tức là k-1 . Ví dụ: Pred (5) = 4, Pred (-6) = -7. Hàm SUCC(k) : đối số k nguyên, trả về số nguyên đứng ngay sau k, tức là k+1 . Ví dụ: Succ (5) = 6, Succ (-6) = -5. Nhận xét : Lệnh k:=k+1; tương đương với lệnh k:=Succ(k); Lệnh k:=k-1; tương đương với lệnh k:=Pred(k); Hàm ODD(k) : đối số k nguyên, trả về gía trị logic là TRUE nếu k lẻ, là FALSE nếu k chẵn. Ví dụ: Odd(15) = True Odd(4) = False. Ví dụ 6.2 : Nhập số nguyên N, nếu N chẵn thì in ra chữ chẵn, nếu N lẻ thì in ra chữ le? Chương trình như sau :
PROGRAM VIDU62; Var N : Integer; Begin Write(‘Nhap so N :’); Readln(N); If Odd(N) = TRUE then write(N, ‘ La so le’) else write(N, ‘ La so chan’); Readln; End. Chạy Chép tập tin nguồn 6.2.7. Các thủ tục có đối số nguyên: Có hai thủ tục khá thông dụng là: Thủ tục INC(k) : tăng k lên một đơn vị. Ví dụ, sau khi thực hiện các lệnh : k:=5; Inc(k); thì gía trị sau cùng của k là 6. Vậy, lệnh Inc(k); tương đương với lệnh k:=k+1; hay k:=Succ(k); Thủ tục DEC(k) : giảm k đi một đơn vị. Ví dụ, sau khi thực hiện các lệnh : k:=5; Dec(k); thì gía trị của k sẽ là 4. Vậy, lệnh Dec(k) ; tương đương với lệnh k:=k-1; hay k:=Pred(k); 6.3. KIỂU SỐ THỰC 6.3.1 Kiểu Real và các kiểu mở rộng :
Kiểu Real là kiểu số thực thông dụng nhất dùng để biểu diễn các số thực x có trị tuyệt đối  x nằm trong khoảng từ 2.9*10-39 đến 1.7*10+38. Nếu  x > 1.7*10+38 thì không biểu diễn x trong máy được, còn nếu  x < 2.9*10-39 thì x được coi là bằng 0. Có hai cách biểu diễn các số thực: Cách 1: Viết bình thường, trong đó dấu phẩy thập phân được thay bằng dấu chấm thập phân. Ví dụ: 45.0 -256.45 +122.08 Cách 2: Viết số dưới dạng khoa học : 1.257E+01 (có gía trị = 1.257*101 = 12.57 ) 1257.0E-02 (có gía trị = 1257*10-2 = 12.57 ) Trong dạng này số gồm có hai phần, phần đứng trước E gọi là phần định trị, được viết theo cách 1, phần đứng sau E gọi là phần bậc, gồm dấu cộng hoặc trừ, tiếp đến là một số nguyên. Số viết theo cách 1 còn gọi là số có dấu chấm thập phân cố định, số viết theo cách 2 còn gọi là số có dấu chấm thập phân di động hay số dạng khoa học (Scientific). Ví dụ: Muốn khai báo hai biến x, y kiểu real, ta viết: Var x, y : Real; Ngoài kiểu Real ra, các số thực còn có 4 kiểu mở rộng nữa là Single, Double, Extended va?Comp. Bảng 6.4 nêu chi tiết về phạm vi gía trị và số byte dùng để lưu trữ trong bộ nhớ của từng kiểu số thực. Tên kiểu Phạm vi gía trị Số byte Real 2.9*10-39 1.7*1038 6 Single 1.5*10-45 3.4*1038 4 Double 5.0*10-324 1.7*10308 8 Extended 3.4*10-4932 1.1*104932 10 Comp -9.2*1018 9.2*1018 8 Bảng 6.4 Chú y? : Turbo Pascal thường chỉ làm việc với một kiểu Real. Muốn dùng 4 kiểu thực còn lại, phải chuyển sang mode 8087 bằ?g cách viết chỉ thị {$N+} ở ngay đầu chương trình.
6.3.2. Các phép toán trên số thực : Có 4 phép toán số học là nhân (*), chia (/), cộng (+) và trừ (-). Khi một trong các số hạng tham gia tính toán là kiểu thực thì kết qủa của phép toán cũng là một số thực. Phép toán DIV, MOD không dùng cho các số thực. Ví dụ: với hai biến x, y kiểu thực thì lệnh sau là bị lỗi vì biểu thức vế phải không hợp lệ: y:= x mod 10 ; Các phép toán so sánh (= , , >= ) cũng dùng được cho các số hạng là thực hay nguyên. 6.3.3. Các hàm có đối số nguyên hoặc thực : Hàm ABS(x): tính trị tuyệt đối của x : x . Kiểu dữ liệu của kết qủa cùng kiểu với đối số. Nếu x nguyên thì ABS(x) cũng nguyên, nếu x là số thực thì ABS(x) cũng là số thực. Ví dụ: Abs(5 - 8) = 3 Hàm SQR(x): tính bình phương của x: x2 . Kiểu dữ liệu của kết qủa cùng kiểu với đối số. Ví dụ: Sqr(4.0) = 16.0 Sqr(7 div 3) = 4 Trong các hàm dưới đây, đối số x có thể là nguyên hay thực, nhưng gía trị trả về?luôn luôn là kiểu thực: Hàm SQRT(x): tính , (x  0) Hàm EXP(x) : tính ex Hàm LN(x): tính lnx, (x > 0) Các hàm SIN(x), COS(x), và ARCTAN(x): tính sinx, cosx và arctgx. Hàm INT(x) : cho số thực bằng phần nguyên của x. Ví dụ : Int(12.55) = 12.0 Int(1+10/3)=4.0 Hàm FRAC(x) : cho số thực bằng phần lẻ của x. Ví dụ : Frac(12.55) = 0.55 Hai hàm đặc biệt dưới đây cho kết qủa là số nguyên: Hàm TRUNC(x): cho số nguyên là phần nguyên của x. Ví dụ :
Trunc(12.55) = 12 Trunc(-2.98) = -2 Hàm ROUND(x): cho số nguyên bằng cách làm tròn x. Ví dụ : Round(12.45) = 12 Round(-2.98) = -3 Chú ý rằng hàm Int(x) và hàm Trunc(x) cùng cho phần nguyên của x, chúng chỉ khác nhau về kiểu dữ liệu của gía trị trả về. Int(4.5)= 4.0 còn Trunc(4.5) = 4 (viết 4 thì hiểu đó là số nguyên, còn viết 4.0 thì hiểu đó là số thực). Ví dụ 6.3: Viết chương trình nhập số thực x bất kỳ, tính và in các gía trị y và z lên màn hình theo công thức: x x Trong Pascal không có hàm tính trực tiếp 2 và Log4(x), nên ta phải chuyển qua hàm e và Ln(x) như sau: , và Chương trình cụ thể như sau: PROGRAM VIDU63; Var x, y, z : Real; Begin Write(‘Nhap x: ‘); Readln(x); y:= ( sqrt (x*x+1) + sin(x)*sin(x) ) / ( 3*exp(2*x) + 1 ); z:= exp( x*Ln(2) ) + Ln(abs(x)+1) / Ln(4); Writeln(‘y= ‘, y:10:3 ); Writeln(‘z= ‘, z:10:3 ); Readln; End.
Chạy . Chép tập tin nguồn Khi chạy chương trình, nếu nhập x =0 thì kết qủa y=0.250 và z=1.000. 6.4. KIỂU KÝ TỰ (CHAR) 6.4.1. Ký tự và biến kiểu ký tự: Ký Mã Ký Mã Ký Mã tự ASCII tự ASCII tự ASCII 32 A 65 a 97 0 48 B 66 b 98 1 49 C 67 c 99 2 50 D 68 d 100 3 51 E 69 f 101 4 52 F 70 e 102 5 53 G 71 g 103 6 54 H 72 h 104 7 55 I 73 i 105 8 56 J 74 j 106 9 57 K 75 k 107 L 76 l 108 M 77 m 109 N 78 n 110 O 79 o 111 P 80 p 112 Q 81 q 113 R 82 r 114 S 83 s 115 T 84 t 116 U 85 u 117
V 86 v 118 W 87 w 119 X 88 x 120 Y 89 y 121 Z 90 z 122 Bảng 6.5 Các ký tự dùng trong máy tính điện tử được liệt kê đầy đủ trong bảng mã ASCII gồm 256 ký tự khác nhau và được đánh số thứ tự từ 0 đến 255. Số thứ tự của mỗi ký tự còn gọi là mã ASCII của ký tự đó. Biểu 6.5 liệt kê một phần của bảng mã ASCII gồm các chữ số và chữ cái kèm theo mã của chúng. Trong bảng 6.5, ký tự có mã bằng 32 là ký tự trắng (space). Tuy có 256 ký tự khác nhau song chỉ có 128 ký tự đầu tiên là hay dùng, còn lại là các ký tự mở rộng. Các ký tự có mã từ 0 đến 31 gọi là các ký tự điều khiển, không in ra được, được dùng để điều khiển các thiết bị ngoại vi, chẳng hạn ký tự có mã là 7 dùng để tạo một tiếng kêu bip, ký tự có mã là 13 dùng để chuyển con trỏ màn hình xuống đầu dòng dưới Mỗi ký tự trong bảng mã ASCII gọi là một hằng ký tự, chiếm độ dài 1 byte, và khi viết trong Pascal phải được đặt trong cặp nháy đơn: ‘0’, ‘1’, ‘A’, ‘B’, ‘$’, Giữa các ký tự, có một thứ tự mặc nhiên theo nguyên tắc : ký tự có mã nhỏ hơn thì nhỏ hơn. Tức là: Ký tự trắng < ‘0’< ‘1’< < ‘9’< ‘A’< ‘B’< ’Z’< ‘a’< ‘b’< < ‘z’ Biến nhận gía trị là các hằng ký tự gọi là biến kiểu ký tự, chúng được khai báo nhờ từ khóa CHAR, chẳng hạn như khai báo hai biến ch và ch1 dưới đây: Var ch, ch1: Char ; Khi đó có thể gán: ch:=‘A’; ch1:=‘$’; Ký tự ‘A’ gọi là gía trị của biến ch, còn ‘$’ là gía trị của biến ch1. Nhận xét: Từ bảng mã của các chữ cái ta suy ra: Mã chữ thường = Mã chữ hoa tương ứng + 32. (1) 6.4.2. Các hàm liên quan đến ký tự :
Hàm PRED(ch): cho ký tự đứng ngay trước ký tự ch trong bảng mã. Ví dụ: Pred(‘B’)=‘A’ Hàm SUCC(ch): cho ký tự đứng ngay sau ký tự ch trong bảng mã. Ví dụ: Succ(‘A’)=‘B’. Hàm UpCase(ch): đổi ký tự ch thành chữ hoa. Ví dụ: Upcase( ‘a’ ) = ‘A’, Upcase( ‘b’ ) = ‘B’, Upcase( ‘A’ ) = ‘A’ . Hàm ORD(ch) : cho mã của ký tự ch. Ví dụ: Ord (‘A’) = 65, Ord (‘a’) = 97 . Hàm CHR(k) : đối số k nguyên, 0 k  255, cho ký tự có mã bằ?g k. Ví dụ: Chr (65)= ‘A’ , Chr (97)= ‘a’, Chr(32) là ký tự trắng. Có một số ký tự không có trên bàn phím, để viết chúng lên màn hình ta phải dùng lệnh Write và hàm CHR. Ví dụ: Lệnh Writeln(Chr(201)) ; in ra ký tự : + Lệnh Writeln(Chr(187)) ; in ra ký tự : + Ký tự có mã là 7 gọi là ký tự BEL (chuông), và lệnh: Write( Chr(7) ) ; hay Write(#7) ; có tác dụng phát ra một tiếng kêu bip. Chú ý: Turbo Pascal ( TP ) cho phép viết gọn Chr(k) thành #k nếu k là hằng số. Ví dụ, hai lệnh sau cùng in lên màn hình chữ A : Write(#65); Write(Chr(65)); Trong TP không có hàm đổi chữ hoa ra chữ thường, nhưng có thể làm việc này nhờ công thức (1) và hai hàm Ord và Chr : Chữ thường := Chr ( Ord(chữ hoa) + 32 ) Ví dụ 6.4: Nhập vào một số nguyên k, 0 k  255, in ra ký tự có mã là k. Chương trình kết thúc khi nhập vào số 0 : PROGRAM VIDU64 ; Uses CRT; Var
k : Byte; Begin CLRSCR; Writeln(‘ Nhập số 0 để kết thúc :’); Repeat Write(‘ Nhập mã của ký tự : ‘); Readln(k); Writeln(‘ Ký tự có mã ‘, k, ‘ là ‘ , Chr(k) ); Until k=0; End. Chạy Chép tập tin nguồn Ví dụ 6.5: Nhập một ký tự, nếu là chữ hoa thì đổi ra chữ thường, nếu là chữ thường thì đổi ra chữ hoa. PROGRAM VIDU65; { Ðổi chữ hoa ra thường và ngược lại} Var ch, ch1 : Char; Begin Write(‘ Nhập một ký tự :’); Readln(ch); If (ch>=‘A’) and ( ch Chép tập tin nguồn
6.5. KIỂU LÔGIC (BOOLEAN) Kiểu boolean chỉ có hai gía trị là TRUE (đúng) và FALSE (sai), không phân biệt chữ hoa hay chữ thường. Về quan hệ thứ tự thì FALSE 1); thì gía trị của A= FALSE, thật vậy : Not (2*3=5) or (‘A’ 1)
= TRUE or TRUE and FALSE xor TRUE = TRUE or FALSE xor TRUE = TRUE xor TRUE = FALSE Biến chỉ nhận gía trị là TRUE hoặc FALSE gọi là biến kiểu lôgic. Khi khai báo biến kiểu lôgic ta dùng từ khóa Boolean, ví dụ : Var A, B : Boolean; Trong chương trình ta có thể gán : A:= true; B:=2*2 0 and N 0) and (N<10) Ví dụ 6.6: Nhập vào độ dài ba cạnh a,b,c của một tam giác, nếu a, b, c không phải là ba cạnh của tam giác thì in lên màn hình câu " không phải ba cạnh của tam gíac", ngược lại, nếu đúng là ba cạnh của một tam giác thì tính chu vi và diện tích tam giác đó theo công thức Hêrông: , với p là nửa chu vi:
Ta biết, điều kiện để a,b,c là ba cạnh của một tam giác là mỗi cạnh phải dương và tổng hai cạnh thì lớn hơn cạnh còn lại. Dưới đây là chương trình cụ thể : PROGRAM VIDU66; {Tính diện tích và chu vi tam giác theo 3 cạnh} Var a, b, c, P, S : Real; Tgiac: Boolean; Begin Write(‘ Nhap 3 canh cua tam giac : ‘); Readln(a, b, c); Tgiac:= (a>0) and (b>0) and (c>0) and (a+b>c) and (a+c>b) and (b+c>a); If Tgiac= FALSE then Writeln(‘ Khong phai ba canh cua tam giac !’) else begin P:=(a+b+c)/2; S:= Sqrt( P*(P-a)*(P-b)*(P-c) ); Writeln(‘ chu vi = ‘ , 2*P:10:2); Writeln(‘ dien tich S= ‘ , S:10:2); end; Readln; End. Chạy
Chép tập tin nguồn Khi chạy chương trình này, để nhập ba cạnh của tam giác, bạn gõ ba số cách nhau khoảng trắng rồi enter, chẳng hạn : Nhap 3 canh cua tam giac : 3 4 5 Kết qủa chu vi= 12.00, dien tich= 6.00. Nếu nhập ba cạnh là : 2 3 6 thì máy hiện câu: "Không phải ba cạnh của tam giác ! " (vì 2+3 ‘Tha’ là đúng vì ‘o’ > ‘a’ Nếu nội dung?của hai chuỗi giống nhau từ đầu đến hết chiều dài của chuỗi ngắn hơn thì chuỗi ngắn hơn là nhỏ hơn, ví dụ: Biểu thức ‘Tha’ < ‘Thang’ là đúng vì ‘Tha’ ngắn hơn ‘Thang’. Hai chuỗi bằng nhau nếu chúng dài bằng nhau và mọi cặp ký tự ở các vị trí tương ứng đều giống nhau. Ví dụ: Biểu thức ‘Pascal’ = ‘Pascal’ cho kết qủa là đúng Biểu thức ‘Pascal’ = ‘PAscal’ cho kết qủa là sai. Biến nhận giá trị là các hằng chuỗi gọi là biến kiểu chuỗi. Có thể khai báo hai biến chuỗi như sau: Var Ho_ten : String[20];
St : String; khi đó Ho_ten là biến chuỗi có thể chứa tối đa 20 ký tự, còn biến chuỗi St có thể chứa tối đa 255 ký tự, và ta có thể gán : Ho_ten := ‘Nguyen Van An’; St :=‘Thao chuong bang ngon ngu Pascal’; Chuỗi ‘Nguyen Van An’ gọi là gía trị của biến Ho_ten. Tương tự, chuỗi ‘Thao chuong bang ngon ngu Pascal’ là gia trị của biến St. 6.7. CÂU HỎI TRẮC NGHIỆM Câu 1: Cho khai báo biến : Var m, n : integer; x, y : Real; Lệnh nào sai : a) m := -4; b) n := 3.5; c) x := 6; d) y := +10.5; Câu 2: Ðể tính gía trị , chọn cách viết nào : a) x := -b/2a; b) x := -b/2*a; c) ; d) x := -b/2/a; Câu 3: Biểu thức : 25 div 3 + 5/2*3 có giá trị là : a) 8.0; b) 15.5; c) 9.5; d) 15.0; Câu 4: Cho phương trình : ax2 + bx + c = 0 . Giả sử a? 0 và Delta:= b*b- 4*a*c > 0 . Một nghiệm của phương trình là : a) X:= -b + SQRT(Delta) / (2*a);
b) X:= (-b + SQRT(Delta) ) /2*a; c) X:= (-b + SQRT(Delta) ) / (2*a); d) X:= (-b -SQR(Delta) ) /2/a; Câu 5: Cho ch là biến có kiểu Char. Lệnh nào đúng : a) ch:="a" b) ch:=65; c) ch:=chr(65); d) ch:='abcd'; Câu 6:Biến X được khai báo là kiểu integer. Lệnh nào sai : a) X:= round(275/3); b) X:= 210 div 4; c) X:= SQRT(49); d) X:= ABS(-453); Câu 7: Biểu thức nào sau đây có giá trị TRUE : a) (100 > 76) and ('B' 4 div 2); c) (49.5 + 2 < 5) and (2 < 4 div 2); d) 2*(3+5) < 18 div 4*4; Câu 8: Khi chạy chương trình : Var St, St1 : String; Begin St := '123'; St1 := '456'; Write(St + St1); End; Kết quả in ra là : a) '123456'; b) 123456; c) 579;
d) Câu a), b), c) đều sai; Câu 9: Sau phép gán : Ch := CHR( ORD('a')- 32 ); thì giá trị của Ch là : a) 65; b) A; c) 'A'; d) 'a'; Câu 10: Khi chạy chương trình : Var a, b, c, N : integer; Begin N:=546; a:=N div 100; b:=(N Mod 100) div 10; c:=(N Mod 100) Mod 10; Write(a+b+c); End. Kết quả in ra : a) 546; b) 5; c) 15; d) 6; 7.1. HẰNG, BIẾN và BIỂU THỨC 7.1.1. Khái niệm về biến và hằng : Trong phần trước ta đã biết mỗi kiểu dữ liệu có một tập các giá trị tương ứng. Các giá trị của kiểu nguyên hay kiểu thực là các số, như 40 hay 5.72, các gía trị của kiểu ký tự là các ký tự như ‘A’ hay ‘a’, còn kiểu lôgic thì chỉ có hai gía trị là True và False, Qúa trình xử lý trong máy tính đòi hỏi mỗi gía trị phải được lưu trữ ở một ô nhớ nào đó trong bộ nhớ của máy, và ô nhớ này được đặt một cái tên để gọi. Khi đó mọi việc tính toán hay xử lý liên quan đến mỗi gía trị được thực hiện gián tiếp thông qua tên của ô nhớ chứa giá trị đó. Ví dụ, nếu số
5.72 được lưu trong ô nhớ có tên là x, thì biểu thức 5.72*2 có thể được viết là x*2. Việc dùng tên x dễ nhớ và tiện hơn nhiều so với việc dùng và nhớ số 5.72. Như vậy, khi một ô nhớ được đặt tên thì tên này đồng nhất với giá trị của nó. Trong một chương trình, mỗi ô nhớ có một tên duy nhất nhưng giá trị của nó thì có thể thay đổi hoặc không. Nếu gía trị của ô nhớ có thể thay đổi được thì ô nhớ này là một biến, tên của ô nhớ là tên biến, ngược lại, nếu gía trị của ô nhớ không thể thay đổi, thì ô nhớ là một hằng, tên của ô nhớ là tên hằng. Các biến và hằng tham gia trong chương trình đều phải được khai báo. Việc khai báo có tác dụng báo trước cho máy dành sẵn các ô nhớ thích hợp trong bộ nhớ để sẵn sàng chứa dữ liệu. 7.1.2. Khai báo biến và khai báo hằng : Biến là đại lượng có gía trị thay đổi được trong chương trình. Cách khai báo biến như sau : Var Danhsáchtênbiến : TênKiểuDữliệu ; Tên biến là tự đặt, theo đúng quy tắc của một tên. Ví dụ : Var i, j : Integer; x, y : Real; Theo khai báo trên, ta có hai biến i và j cùng kiểu số nguyên (Integer), và hai biến x, y cùng kiểu số thực (Real). Hằng là một đại lượng có gía trị không đổi trong chương trình. Cách khai báo : Const Tên_hằng = gíatrị ; Tên hằng là tự đặt, theo đúng quy tắc của một tên. Ví dụ : Const N = 10; SoPi = 3.1416; SoE = 2.718; Turbo Pascal có sẵn một số hằ?g chuẩn cho phép sử dụng mà không phải khai báo, như : Pi, MaxInt . Hằng Pi có gía trị bằng số , còn MaxInt = 32767, là số Integer lớn nhất. Chẳng hạn, có thể dùng các lệnh sau: Writeln(‘Dien tich hinh tron ban kinh r=5 la: ‘ , Pi*5*5:8:3);
Writeln(‘So Integer lon nhat = ‘ , MaxInt); 7.1.3. Biểu thức : Biểu thức là một công thức gồm có một hay nhiều thành phần được kết nối với nhau bởi các phép toán. Mỗi thành phầ? (hay toán hạng) có thể là hằng, là biến hay là hàm. Khi các phép toán trong biểu thức được thực hiện thì ta nhận được một gía trị gọi là kết qủa của biểu thức. Kiểu dữ liệu của kết qủa gọi là kiểu dữ liệu của biểu thức. Ví dụ: 3* 5 div 2 + 7 mod 4 là biểu thức nguyên, có kết qủa là 10 2 + sin(pi/2) là biểu thức thực, có kết qủa là 3.0 Chr( ord(‘a’) - 32 ) là biểu thức ký tự, có kết qủa là ‘A’ (4+2=6) and (‘B’ , , >=, IN Bảng 7.1 Việc tính toán một biểu thức dựa theo hai quy tắc : Quy tắc 1: Phép toán có cấp ưu tiên nhỏ thì được tính trước, phép toán có cấp ưu tiên lớn thì được tính sau. Quy tắc 2: Ðối với các phép toán đứng liền nhau và có cùng cấp ưu tiên, thì cái nào đứng trước được tính trước.
Ví dụ : tính biểu thức số học : (4+5)*2 div 7 + sin(pi/6) = = 9 * 2 div 7 + 0.5 = 18 div 7 + 0.5 = 2 + 0.5 = 2.5 Ví dụ : tính biểu thức lôgic : ( 2 > 4 div 2) or Not ( 49.25 + 2 2) or Not ( 51.25 =0 then Writeln(k) else Writeln( -k) ; Hai hay nhiều lệnh đơn giản được gom lại và đặt giữa hai từ khóa BEGIN và END tạo thành một câu lệnh ghép, câu lệnh ghép cũng là lệnh có cấu trúc, ví dụ: