Giáo Trình : Kĩ Thuật Lập Trình Nâng Cao

MỤC LỤC
Mục lục 1
Lời nói đầu 3
Chương 1 Một số kỹ thuật – phong cách lập trình tốt 4
1.1 Cách đặt tên cho biến hàm 4
1.2 Phong cách viết mã nguồn 6
1.3 Tối ưu sự thực thi mã nguồn 8
Chương 2 Kỹ thuật đệ quy 16
2.1 Kỹ thuật đệ quy 16
2.2 Xây dựng một chương trình đệ quy 20
2.3 Các ví dụ đệ quy 21
2.4 Khử đệ quy 27
2.4.1 Tìm hiểu cơ chế thực hiện hàm đệ quy 27
2.4.2 Các trường hợp khử đệ quy đơn giản 29
2.4.3 Khử đệ quy dùng stack 31
Chương 3 Bài toán liên quan tổ hợp 37
3.1 Phương pháp sinh (kế tiếp) 37
3.1.1 Bài toán sinh dãy nhị phân độ dài n 37
3.1.2 Bài toán liệt kê tập con k phần tử 39
3.1.3 Bài toán liệt kê các hoán vị 42
3.2 Thuật toán quay lui (Back Tracking) 45
3.2.1 Thuật toán quay lui liệt kê dãy nhị phân n 47
3.2.2 Thuật toán quay lui liệt kê tập con k phần tử 48
3.2.3 Thuật toán quay lui liệt kê hoán vị n phần tử 50
3.2.4 Bài toán sắp xếp quân Hậu 51
3.2.5 Bài toán mã đi tuần 57
Chương 4 Tìm kiếm và Sắp xếp 63
4.1 Tìm kiếm 63
4.1.1 Mô tả bài toán tìm kiếm trong tin học 63
4.1.2 Tìm kiếm tuyến tính 64
4.1.3 Tìm kiếm nhị phân 65
4.1.4 Kết luận 67
4.2 Bài toán sắp xếp 67
4.3 Một số phương pháp sắp xếp cơ bản 67
4.3.1 Phương pháp chọn 67
4.3.2 Phương pháp sắp xếp nổi bọt 68
4.3.3 Phương pháp sắp xếp chèn 68
4.3.4 Phương pháp đổi chỗ trực tiếp 69
4.3.5 Phương pháp ShellSort 73
4.3.6 Phương pháp phân đoạn QuickSort 76
4.3.7 Phương pháp cơ số RadixSort 80
Chương 5 Stack - Queue 84
5.1 Giới thiệu Stack – ngăn xếp 84
5.1.1 Cài đặt Stack dùng CTDL mảng 85
5.1.2 Các ứng dụng stack 87
5.1.3 Các ví dụ minh họa 88
5.2 Giới thiệu Queue – hàng đợi 103
5.2.1 Cài đặt Queue dùng CTDL mảng 105
5.2.2 Các ứng dụng Queue 106
BÀI TẬP 114
TÀI LIỆU THAM KHẢO 121

(((

Lời nói đầu

Học phần kỹ thuật lập trình 2 được thiết kế dành cho sinh viên khoa công nghệ thông tin ĐH Kỹ Thuật Công Nghệ, là phần tiếp nối với môn kỹ thuật lập trình 1. Mục đích của môn học là bổ sung những kỹ thuật lập trình đệ quy, khử đệ quy, các bài toán trên tập hợp, phương pháp sinh, kỹ thuật quay lui, tìm kiếm và sắp xếp trên mảng, ngăn xếp và hàng đợi…Song song với phần lý thuyết là các ví dụ minh họa cụ thể, cho phép sinh viên hiểu rõ vấn đề hơn.
Ngoài những kỹ thuật lập trình, giáo trình còn đề cập tới phương diện phong cách lập trình trong chương 1. Việc sớm làm quen với phong cách lập trình sẽ hỗ trợ sinh viên hoàn thiện kỹ năng viết chương trình.
Bài giảng được viết lần đầu tiên nên sẽ không tránh khỏi những sai sót. Kính mong sự đóng góp của các giảng viên và sinh viên nhằm hoàn thiện phần bài giảng này trong lần tái bản sau.
Tất cả những ý kiến đóng góp điều được trân trọng.
Xin chân thành cảm ơn!

Tác giả
Chương 1
Một số kỹ thuật – phong cách lập trình tốt

(((

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 tuy 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 cho chính người lập trình!
Đôi khi người mới lập trình không quan tâm đến vấn đề này do ban