Giáo trình Turbo Pascal

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....
Nội dung trích xuất từ tài liệu:
Giáo trình Turbo Pascal Giáo trình Turbo Pascal Trang 1/286 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” Trang 2/286 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 Trang 3/286 12.2. HÀM (FUNCTION)   12.3. THỦ TỤC (PROCED   URE   ) 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ỆM13.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. Trang 4/286 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 ...