Giáo trình Kỹ thuật lập trình nâng cao: Phần 1 - Trường ĐH Công nghiệp Thực phẩm TP. HCM

Giáo trình Kỹ thuật lập trình nâng cao: Phần 1 cung cấp cho người học những kiến thức như: tổng quan kỹ thuật lập trình; kỹ thuật xử lý mảng; kỹ thuật đệ quy. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Giáo trình Kỹ thuật lập trình nâng cao: Phần 1 - Trường ĐH Công nghiệp Thực phẩm TP. HCM TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THỰC PHẨM TP.HCM KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM  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. ....................................... 5 1.2 Phân tích đánh giá giải thuật ........................................................................ 12 1.2.1 Sự cần thiết phân tích thuật giải ............................................................... 12 1.2.2 Thời gian thực hiện của chương trình ....................................................... 12 1.2.3 Tỷ suất tăng và độ phức tạp của thuật toán ............................................... 13 1.2.4 Cách tính độ phức tạp .............................................................................. 14 CHƯƠNG 2. 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........................................................................... 24 2.1.2 Thuật toán tính tổng và tích...................................................................... 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 ................................................................................... 33 2.2 Kỹ thuât xử lý mảng hai chiều ..................................................................... 34 2.2.1 Mảng hai chiều (ma trận) ......................................................................... 34 2.2.2 Thuật toán cơ bản trên mảng hai chiều ..................................................... 36 2.2.3 Ma trận vuông.......................................................................................... 42 2.2.4 Một số bài toán đặc biệt ........................................................................... 46 CHƯƠNG 3. KỸ THUẬT ĐỆ QUY .......................................................................... 51 3.1 Khái niệm .................................................................................................... 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.2 Tìm các trường hợp cơ bản (phần cơ sở) cùng giải thuật tương ứng cho các trường hợp này. .................................................................................................. 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............................................................................. 73 CHƯƠNG 4. KỸ THUẬT XỬ LÝ CHUỖI ............................................................... 80 4.1 Một số khái niệm ......................................................................................... 80 4.1.1 Chuỗi kí tự ............................................................................................... 80 4.1.2 Nhập/ xuất chuỗi kí tự.............................................................................. 80 ...