- Giáo trình KỸ THUẬT LẬP TRÌNH NÂNG CAO (Dành cho hệ Đại học) TP.HCM, tháng 9 năm 2013 1 MỤC LỤC CHƯƠNG 1. - TỔNG QUAN KỸ THUẬT LẬP TRÌNH. - 5 1.1 Tổng quan về kỹ thuật lập trình. - 5 1.1.1 Phong cách lập trình. - 5 1.1.2 Một số kỹ thuật và phong cách lập trình căn bản. - 12 1.2.2 Thời gian thực hiện của chương trình. - KỸ THUẬT XỬ LÝ MẢNG. - 22 2.1 Kỹ thuật xử lý mảng một chiều. - 22 2.1.1 Thuật toán lặp tổng quát. - 26 2.1.3 Thuật toán đếm. - 29 2.1.4 Thuật toán tìm phần tử đầu tiên. - 30 2.1.5 Thuật toán tìm tất cả các phần tử. - 30 2.1.6 Thuật toán tìm min, max. - 31 2.1.7 Thuật toán sắp xếp. - 42 2.2.4 Một số bài toán đặc biệt. - KỸ THUẬT ĐỆ QUY. - 51 3.2 Các dạng đệ quy. - 52 3.2.1 Đệ quy tuyến tính (Linear Recursion. - 52 3.2.2 Đệ quy nhị phân (Binary Recursion. - 53 3.2.3 Đệ quy phi tuyến (NonLinear Recursion. - 54 3.2.4 Đệ quy lồng (Nested Recursion. - 55 3.2.5 Đệ quy tương hỗ (Mutual Recursion. - 58 3.2.6 Những ưu nhược điểm của kỹ thuật đệ quy. - 59 3.3 Các bước tìm giải thuật đệ quy cho một bài toán. - 60 3.3.1 Thông số hóa bài toán. - 60 3.3.3 Phân rã bài toán tổng quát theo phương thức đệ quy. - 60 3.4 Một số bài toán đệ quy thông dụng. - 61 3.4.1 Bài toán tìm tất cả hoán vị của một dãy phần tử. - 61 3.4.2 Bài toán sắp xếp mảng bằng phương pháp trộn (Merge Sort. - 63 2 3.4.3 Bài toán chia thưởng. - 65 3.4.4 Bài toán tháp Hà Nội. - 67 3.5 Khử đệ quy. - 70 3.5.1 Khử đệ quy đơn giản bằng vòng lặp. - 71 3.5.2 Khử đệ quy dùng stack. - KỸ THUẬT XỬ LÝ CHUỖI. - 80 4.1 Một số khái niệm. - 82 4.2.1 Thuật toán Brute Force. - THIẾT KẾ THUẬT TOÁN. - 90 5.1 Kỹ thuật chia để trị - Divide to Conquer. - 90 5.1.2 Một số bài toán minh họa. - 91 5.2 Kỹ thuật tham ăn – Greedy Technique. - 95 5.2.1 Giới thiệu bài toán tối ưu tổ hợp. - 95 5.2.2 Nội dung kỹ thuật tham ăn. - 95 5.2.3 Một số bài toán minh họa. - 95 5.3 Kỹ thuật nhánh cận - Branch and Bound. - 102 5.3.2 Bài toán tìm đường đi của người giao hàng. - 102 5.4 Kỹ thuật quy hoạch động - Dynamic programming. - 103 5.4.2 Một số bài toán minh họa. - 104 5.4.3 Bài toán ba lô. - 118 3 LỜI NÓI ĐẦU “Algorithm + Data structure = Program” (“Giải thuật + Cấu trúc dữ liệu = Chương trình”) Câu nói nổi tiếng của Niklaus Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông. - Qua đó chúng ta thấy vai trò quan trọng của giải thuật và kỹ thuật lập trình để xây dựng các giải thuật nhằm tìm đáp án tối ưu nhất cho các bài toán lập trình. - Môn học Kỹ thuật lập trình nâng cao được bố trí sau 2 môn học Kỹ thuật lập trình và Cấu trúc dữ liệu trong chương trình đào tạo cho sinh viên chuyên ngành Công nghệ thông tin. - Môn học nhằm giới thiệu cho sinh viên những kiến thức cơ bản, những kỹ thuật chủ yếu của việc phân tích và xây dựng các giải thuật, để tìm ra các cách giải tối ưu nhất có thể cho bài toán. - Các kỹ thuật được trình bày ở đây là những kỹ thuật cơ bản, phổ biến và được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt các chương trình. - Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh viên khi phải giải quyết một vấn đề thực tế. - Chương 1: Tổng quan kỹ thuật lập trình - Chương 2: Xử lý cấu trúc mảng - Chương 3: Kỹ thuật đệ qui - Chương 4: Xử lý chuỗi - Chương 5: Thiết kế thuật toán Các vấn đề được trình bày chi tiết với những ví dụ rõ ràng. - Chúng tôi xin cảm ơn và hy vọng rằng giáo trình này sẽ giúp cho việc giảng dạy và học môn “Kỹ thuật lập trình nâng cao” đạt hiệu quả tốt hơn. - TỔNG QUAN KỸ THUẬT LẬP TRÌNH 1.1 Tổng quan về kỹ thuật lập trình 1.1.1 Phong cách lập trình Một chương trình nguồn được xem là tốt không chỉ được đánh giá thông qua thuật giải đúng và cấu trúc dữ liệu thích hợp, mà còn phụ thuộc vào phong cách và kỹ thuật mã hoá (coding) của người viết chương trình. - Nếu một người lập trình viết một chương trình dù thực hiện đúng yêu cầu đặt ra nhưng mã nguồn quá lộn xộn và phong cách lập trình cẩu thả, thì mã nguồn này sẽ gây khó khăn không chỉ cho những người khác muốn đọc hiểu nó, mà còn cho chính người lập trình khi muốn chỉnh sửa hoặc cải tiến. - Đôi khi người mới lập trình không quan tâm đến vấn đề này do ban đầu chỉ làm việc với chương trình nhỏ. - Tuy nhiên, vấn đề phát sinh khi họ phải làm việc với dự án lớn và chương trình lúc này không còn đơn giản vài chục dòng lệnh nữa. - Nếu không rèn luyện một phong cách và trang bị một số kỹ thuật lập trình tốt thì người lập trình đối mặt với nhiều khó khăn… Trong chương đầu tiên xin giới thiệu một số kỹ thuật và phong cách lập trình cơ bản, ít nhiều giúp cho người học viết chương trình được tốt hơn. - 1.1.2 Một số kỹ thuật và phong cách lập trình căn bản. - Cách đặt tên biến Thông thường tùy theo ngôn ngữ và môi trường lập trình, người viết chương trình thường chọn cho mình một phong cách nhất quán trong việc đặt tên các định danh. - Nếu đặt quá ngắn gọn như c cho biến đếm, hay w cho khối lượng thì sau này khi nhìn vào chương trình sẽ rất khó hiểu ý nghĩa của chúng. - để chỉ các số bất kỳ, sẽ làm dư thừa, rườm rà trong chương trình. - Tên phải xác định được kiểu dữ liệu lưu trữ: phong cách lập trình tốt là khi người đọc nhìn vào một biến nào đó thì xác định ngay được kiểu dữ liệu và tên đối tượng mà biến đó lưu trữ. - Giả sử có biến đếm số lần thì ta có thể đặt iNumber, trong đó i là kiểu của dữ liệu, strContent là kiểu chuỗi, CPoint là lớp Point…Có nhiều cú pháp quy ước đặt tên biến, người lập trình có thể chọn cho mình một quy ước thích hợp. - Có thể tham khảo một số quy ước trong phần bên dưới. - Bảng 1.1 bên dưới là một số tiền tố quy ước được nhiều lập trình viên sử dụng. - Các công ty phần mềm thường có các quy ước về cách đặt tên biến cho 5 đội ngũ lập trình viên. - Tuy nhiên điều này cũng không bắt buộc tùy theo ngôn ngữ lập trình. - Ngoài ra hàm có chức năng thực hiện một nhiệm vụ nào đó, cho nên tên chúng là động từ hoặc cụm động từ, thường bắt đầu bằng các động từ chính: get, set, do, is, make… Ví dụ 1.2: string setName. - Phong cách viết mã nguồn – Sử dụng tab để canh lề chương trình : khi soạn thảo mã nguồn nên dùng tab với kích thước là 4 hay 8 khoảng cách để canh lề. - Thói quen này giúp cho chương trình được rõ ràng và dễ đọc, dễ quản lý. - Sử dụng khoảng trắng : chương trình sẽ dễ nhìn hơn Không nên Nên int iCount =0 . - for(int i=0;i x.ms. - Đôi khi còn làm cho chương trình khó nhìn hơn. - cout a[j] cũng tốn O(1) thời gian, do đó lệnh (3) tốn O(1) thời gian. - Vòng lặp (2) lặp có i chạy từ 1 đến n-1 nên thời gian thực hiện của vòng. - Trong trường hợp xấu nhất (tất cả các phần tử của mảng a đều khác x) thì vòng lặp (2) thực hiện n lần, vậy ta có T(n. - 1.2.4.3 Độ phức tạp của chương trình có gọi chương trình con không đệ qui Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của các chương trình con không gọi các chương trình con khác. - Sau đó chúng ta tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời gian thực hiện của chúng đã được tính. - Chúng ta tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất cả các chương trình con mà nó gọi đã được đánh giá. - Cuối cùng ta tính thời gian cho chương trình chính. - Giả sử ta có một hệ thống các chương trình gọi nhau theo sơ đồ sau: 16 Chương trình A gọi hai chương trình con là B và C, chương trình B gọi hai chương trình con là B1 và B2, chương trình B1 gọi hai chương trình con là B11 và B12. - Ðể tính thời gian thực hiện của A, ta tính theo các bước sau. - Bước 1: Tính thời gian thực hiện của C, B2, B11 và B12. - Vì các chương trình con này không gọi chương trình con nào cả. - Bước 2: Tính thời gian thực hiện của B1. - Vì B1 gọi B11 và B12, thời gian thực hiện của B11 và B12 đã được tính ở bước 1. - Bước 3: Tính thời gian thực hiện của B. - Vì B gọi B1 và B2, thời gian thực hiện của B1 đã được tính ở bước 2 và thời gian thực hiện của B2 đã được tính ở bước 1. - Bước 4: Tính thời gian thực hiện của A. - Vì A gọi B và C, thời gian thực hiện của B được tính ở bước 3 và thời gian thực hiện của C đã được tính ở bước 1. - Ví dụ 1.12: Ta có thể viết lại chương trình sắp xếp bubble theo dạng gọi hàm con swap (hoán đổi giá trị 2 phần tử) như sau: void BubbleSort (int a. - Trong cách viết trên, chương trình Bubble gọi chương trình con Swap, do đó để tính thời gian thực hiện của Bubble, trước hết ta cần tính thời gian thực hiện của Swap. - Thời gian thực hiện của Swap là O(1) vì nó chỉ bao gồm 3 lệnh gán . - Lệnh (1) thực hiện n-1 lần nên. - Những đoạn mã nguồn sau đây đã viết tối ưu có thể chưa? Các chuẩn về chú thích, định danh… đã hợp lý chưa? Nếu chưa thì sửa như thế nào? //Khai báo các cấu trúc trong chương trình typedef struct structtag_Date { int day