Giáo trình Nhập môn Tin học: Phần 2 - ThS. Đào Tăng Kiệm

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