tài liệu giáo khoa chuyên tin (quyển 1)

Hå sÜ ®µm (Chñ biªn)<br /> ®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïng<br /> <br /> tµi liÖu gi¸o khoa<br /> <br /> chuyªn tin<br /> quyÓn 1<br /> <br /> Nhµ xuÊt b¶n gi¸o dôc viÖt nam<br /> <br /> C«ng ty Cæ phÇn dÞch vô xuÊt b¶n Gi¸o dôc Hµ Néi - Nhµ xuÊt b¶n Gi¸o dôc ViÖt Nam<br /> gi÷ quyÒn c«ng bè t¸c phÈm.<br /> <br /> 349-2009/CXB/43-644/GD<br /> 2<br /> <br /> M4 sè : 8I746H9<br /> <br /> LỜI NÓI ðẦU<br /> Bộ Giáo dục và ðào tạo ñã ban hành chương trình chuyên tin học cho các<br /> lớp chuyên 10, 11, 12. Dựa theo các chuyên ñề chuyên sâu trong chương trình<br /> nói trên, các tác giả biên soạn bộ sách chuyên tin học, bao gồm các vấn ñề cơ<br /> bản nhất về cấu trúc dữ liệu, thuật toán và cài ñặt chương trình.<br /> Bộ sách gồm ba quyển, quyển 1, 2 và 3. Cấu trúc mỗi quyển bao gồm: phần<br /> lí thuyết, giới thiệu các khái niệm cơ bản, cần thiết trực tiếp, thường dùng nhất;<br /> phần áp dụng, trình bày các bài toán thường gặp, cách giải và cài ñặt chương<br /> trình; cuối cùng là các bài tập. Các chuyên ñề trong bộ sách ñược lựa chọn mang<br /> tính hệ thống từ cơ bản ñến chuyên sâu.<br /> Với trải nghiệm nhiều năm tham gia giảng dạy, bồi dưỡng học sinh chuyên tin<br /> học của các trường chuyên có truyền thống và uy tín, các tác giả ñã lựa chọn,<br /> biên soạn các nội dung cơ bản, thiết yếu nhất mà mình ñã sử dụng ñể dạy học<br /> với mong muốn bộ sách phục vụ không chỉ cho giáo viên và học sinh chuyên<br /> PTTH mà cả cho giáo viên, học sinh chuyên tin học THCS làm tài liệu tham khảo<br /> cho việc dạy và học của mình.<br /> Với kinh nghiệm nhiều năm tham gia bồi dưỡng học sinh, sinh viên tham gia<br /> các kì thi học sinh giỏi Quốc gia, Quốc tế Hội thi Tin học trẻ Toàn quốc,<br /> Olympiad Sinh viên Tin học Toàn quốc, Kì thi lập trình viên Quốc tế khu vực<br /> ðông Nam Á, các tác giả ñã lựa chọn giới thiệu các bài tập, lời giải có ñịnh<br /> hướng phục vụ cho không chỉ học sinh mà cả sinh viên làm tài liệu tham khảo<br /> khi tham gia các kì thi trên.<br /> Lần ñầu tập sách ñược biên soạn, thời gian và trình ñộ có hạn chế nên chắc<br /> chắn còn nhiều thiếu sót, các tác giả mong nhận ñược ý kiến ñóng góp của bạn<br /> ñọc, các ñồng nghiệp, sinh viên và học sinh ñể bộ sách ñược ngày càng hoàn<br /> thiện hơn .<br /> Các tác giả<br /> <br /> 3<br /> <br /> 4<br /> <br /> Chuyên ñề 1<br /> <br /> THUẬT TOÁN<br /> VÀ PHÂN TÍCH THUẬT TOÁN<br /> 1. Thuật toán<br /> Thuật toán là một trong những khái niệm quan trọng nhất trong tin học. Thuật ngữ<br /> thuật toán xuất phát từ nhà khoa học Arập Abu Ja'far Mohammed ibn Musa al<br /> Khowarizmi. Ta có thể hiểu thuật toán là dãy hữu hạn các bước, mỗi bước mô tả<br /> chính xác các phép toán hoặc hành ñộng cần thực hiện, ñể giải quyết một vấn ñề.<br /> ðể hiểu ñầy ñủ ý nghĩa của khái niệm thuật toán chúng ta xem xét 5 ñặc trưng sau<br /> của thuật toán:<br /> •<br /> <br /> ðầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào ñó.<br /> <br /> •<br /> <br /> ðầu ra (Output): Với mỗi tập các dữ liệu ñầu vào, thuật toán ñưa ra các<br /> dữ liệu tương ứng với lời giải của bài toán.<br /> <br /> •<br /> <br /> Chính xác: Các bước của thuật toán ñược mô tả chính xác.<br /> <br /> •<br /> <br /> Hữu hạn: Thuật toán cần phải ñưa ñược ñầu ra sau một số hữu hạn (có<br /> thể rất lớn) bước với mọi ñầu vào.<br /> <br /> •<br /> <br /> ðơn trị: Các kết quả trung gian của từng bước thực hiện thuật toán ñược<br /> xác ñịnh một cách ñơn trị và chỉ phụ thuộc vào ñầu vào và các kết quả<br /> của các bước trước.<br /> <br /> •<br /> <br /> Tổng quát: Thuật toán có thể áp dụng ñể giải mọi bài toán có dạng<br /> ñã cho.<br /> <br /> ðể biểu diễn thuật toán có thể biểu diễn bằng danh sách các bước, các bước ñược<br /> diễn ñạt bằng ngôn ngữ thông thường và các kí hiệu toán học; hoặc có thể biểu<br /> diễn thuật toán bằng sơ ñồ khối. Tuy nhiên, ñể ñảm bảo tính xác ñịnh của thuật<br /> toán, thuật toán cần ñược viết bằng các ngôn ngữ lập trình. Một chương trình là sự<br /> biểu diễn của một thuật toán trong ngôn ngữ lập trình ñã chọn. Trong tài liệu này,<br /> chúng ta sử dụng ngôn ngữ tựa Pascal ñể trình bày các thuật toán. Nói là tựa<br /> Pascal, bởi vì nhiều trường hợp, ñể cho ngắn gọn, chúng ta không hoàn toàn tuân<br /> <br /> 5<br /> <br />