Giáo trình Kỹ thuật lập trình 2

Một chương trình nguồn được xem là tốt không chỉ được đánh giá thông qua thuậtgiả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 ranhư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âykhó khăn cho chính người lập trình!...
Nội dung trích xuất từ tài liệu:
Giáo trình Kỹ thuật lập trình 2 Giáo trìnhKỹ thuật lập trình 2  Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN MỤC LỤCMục lục ............................................................................................................................... 1Lời nói đầu .......................................................................................................................... 3Chươ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..................................................................................... 8Chươ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 .................................................................................... 31Chươ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 .......................................................................................... 57Chươ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 .................................................... ...