Giáo trình nhập môn tin học - Phần II Thuật toán

Phân tích bài toán và xây dựng giải thuật: thiết lập cấu trúc dữ liệu, cách lưu trữ, tìm kiếm, chọn phương pháp và cách giải - xây dựng sơ đồ tổng thể và các thuật toán chi tiết cho bài toán hoặc viết Code của chương trình.
Nội dung trích xuất từ tài liệu:
Giáo trình nhập môn tin học - Phần II Thuật toán Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm TRƯỜNG ĐẠI HỌC XÂY DỰNG KHOA CÔNG NGHỆ THÔNG TIN ------------  ------------ GIÁO TRÌNH MÔN HỌC: NHẬP MÔN TIN HỌC PHẦN II – THUẬT TOÁN Giảng viên: ĐÀO TĂNG KIỆM Bộ môn : TIN HỌC XÂY DỰNG Hà nội 2011 ---------- 1 Bộ môn Tin học Xây dựng Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm PHẦN 2 GIẢI BÀI TOÁN TRÊN MÁY TÍNH – THUẬT TOÁN I. CẤC BƯỚC XÂY DỰNG CHƯƠNG TRÌNH VÀ GIẢI BÀI TOÁN TRÊN MÁY TÍNH 1. Thu thập dữ liệu để thiết kế chương trình (User Requirement): yêu cầu của bài toán về đầu vào, đầu ra, giao diện, hệ thống, người sử dụng, nội dung cần tính toán, xử lý … 2. Phân tích bài toán và xây dựng giải thuật (Algorithm- Analyze -Code): thiết lập cấu trúc dữ liệu, cách lưu trữ, tìm kiếm, chọn phương pháp và cách giải -> xây dựng sơ đồ tổng thể và các thuật toán chi tiết cho bài toán hoặc viết Code của chương trình. 3. Chọn ngôn ngữ lập trình và viết chương trình (Write Program): giải quyết bài toán theo sơ đồ thuật toán đã lập. 4. Kiểm tra sự đúng đắn của chương trình (Test): thử nghiệm chương trình với các dữ liệu khác nhau có thể xảy ra trong bài toán để kiểm tra độ tin cậy của chương trình. Trong phần này có thể có một số giai đoạn : Kiểm tra từng mô đun trong chương trình ; Móc nối các mô đun với nhau. 5. Vận hành - Bảo trì ( Maintenance): Chương trình được đem ra xử dụng thực tế và nhận sự phản hồi của người sử dụng, khách hàng. Tùy thuộc vào chất lượng của chương trình nó có thể được kiểm tra và đăng ký bản quyền hoặc phải sửa chữa. II. KHÁI NIỆM VỀ THUẬT TOÁN VÀ GIẢI THUẬT 1. Khái niệm về thuật toán Thuật toán là một chuỗi các phép xử lý thông tin, đưa ra phương pháp và trình tự giải một bài toán trên máy tính. ThuËt to¸n ®­îc hiÓu lµ c¸c b­íc, c¸c mÑo, luËt ®Ó thùc hiÖn c¸c qu¸ tr×nh xö lý th«ng tin. 2. Các đặc trưng cơ bản: - Các qui định thể hiện sơ đồ thuật toán phải thống nhất và theo qui định chung nên mọi người đều có thể hiểu được sơ đồ thuật toán. 3. Đặc điểm : - Thuật toán chỉ có nghĩa với người lập trình, máy tính không hiểu được. 2 Bộ môn Tin học Xây dựng Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm - Cùng một vấn đề có thể có nhiều phương án lập sơ đồ thuật toán khác nhau. - Thuật toán có thể mô tả các bước chính của bài toán (TT tổng quát) hoặc chi tiết từng bước giải của vấn đề (thuật toán chi tiết). - Thuật toán hay, cách giải ngắn, kết quả chính xác … phụ thuộc vào phương pháp giải, trình độ và kinh nghiệm của người lập trình. 4. Các cấu trúc cơ bản của thuật toán - Cấu trúc tuần tự - Cấu trúc rẽ nhánh - Cấu trúc lặp 5. Cách biểu diễn sơ đồ thuật toán Thông thường có 2 cách thể hiện sơ đồ thuật toán : theo sơ đồ khối và sơ đồ tuyến. Sơ đồ khối : là các bước lưu trữ, các phép xử lý thông tin được đặt trong các khối. Các khối nối với nhau bằng các đường liên lạc, đường phân chia, hợp, nối tiếp … Sơ đồ tuyến :là tất cả các bước lưu trữ, xử lý TT … được ghi trên một đường liên tục từ trên xuống dưới. Ví dụ: Cấu trúc Sơ đồ khối Cấu trúc Sơ đồ tuyến 3 Bộ môn Tin học Xây dựng Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 6. Ký hiệu cơ bản dùng trong sơ đồ thuật toán : Khối bắt đầu, kết thúc Khối nhập dữ liệu từ bàn phím- xuất dữ liệu ra màn hình Khối tính toán Khối kiểm tra- So sánh Khối nối tiếp Các đường liên lạc Ký hiệu chương trình con Các thiết bị xuất kết quả ra đĩa, giấy in 7. Các bước cần chuẩn bị trước khi viết sơ đồ thuật toán:  Tổ chức dữ liệu cho chương trình : + Xác định những số liệu nào cần nhập vào chương trình (là các dữ liệu do đầu bài cung cấp) + Xác định các dữ liệu phát sinh trung gian trong quá trình tính toán, dữ liệu cần xuất kết quả (dựa theo yêu cầu của bài toán) + Mỗi loại dữ liệu cần xác định các thông tin: - Số lượng biến - Cấu trúc dữ liệu: Loại biến ( đơn, mảng, bản ghi …) - Kiểu dữ liệu: nguyên, thực, bản ghi, kiểu mới tự đặt . . . - Tên của dữ liệu: tên biến, hằng, kiểu, bản ghi … ( người dùng tự đặt, nên đặt ngắn, viết tắt ý nghĩa của biến )  Xác định các công thức tổng quát cần tính (chú ý nằm ngoài chu trình hoặc trong chu trình).  Trình tự các bước cần thực hiện: với những bài toán phức tạp cần thể hiện 2 loại sơ đồ: Sơ đồ thuật toán tổng quát (các khối thực hiện chính); Sơ đồ thuật toán chi tiết: diễn giải các bước thực hiện cho từng khối chính 4 Bộ môn Tin học Xây dựng Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm III. CÁC DẠNG THUẬT TOÁN CƠ BẢN 1. Dạng thuật toán đơn giản – cấu trúc tuần tự  Khái niệm: Thuật toán đơn giản là các bước ( nhập dữ liệu, tính toán, xử lý, xuất kết quả) ...