Giáo trình Kỹ thuật lập trình 2 - ĐH KTCN

Học phần kỹ thuật lập trình 2 được thiết kế dành cho sinh viên khoa côngnghệ 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ậptrì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....
Nội dung trích xuất từ tài liệu:
Giáo trình Kỹ thuật lập trình 2 - ĐH KTCN Giáo trình Kỹthuật lập trình 2Giá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 .............................................................. ...