Tài liệu Kỹ thuật lập trình nâng cao

MỤC LỤC
LỜI NÓI ĐẦU 4
PHẦN I 5
CHƯƠNG I .5
I. MỞ ĐẦU .5
1. Mô tả đệ quy 5
2. Các loại đệ quy 6
II. MÔ TẢ ĐỆ QUY CÁC CẤU TRÚC DỮ LIỆU .7
III. MÔ TẢ ĐỆ QUY GIẢI THUẬT 7
1. Giải thuật đệ quy 7
2. Chương trình con đệ quy 8
3. Mã hóa giải thuật đệ qui trong các ngôn ngữ lập trình 11
4. Một số dạng giải thuật đệ quy đơn giản thường gặp .13
CHƯƠNG II .16
I. CÁC NỘI DUNG CẦN LÀM ĐỂ TÌM GIẢI THUẬT ĐỆ QUY CHO MỘT BÀI TOÁN 16
1. Thông số hoá bài toán .16
2. Phát hiện các trường hợp suy biến (neo) và tìm giải thuật cho các trường hợp này.16
3. Phân rã bài toán tổng quát theo phương thức đệ quy .16
II. MỘT SỐ BÀI TOÁN GIẢI BẰNG GIẢI THUẬT ĐỆ QUY ĐIỂN HÌNH .17
1. Bài toán tháp Hà Nội 17
2. Bài toán chia thưởng 19
3. Bài toán tìm tất cả các hoán vị của một dãy phần tử .21
4. Bài toán sắp xếp mảng bằng phương pháp trộn (Sort-Merge) 24
5. Bài toán tìm nghiệm xấp xỉ của phương trình f(x)=0 25
CHƯƠNG III 28
I. CƠ CHẾ THỰC HIỆN GIẢI THUẬT ĐỆ QUY 28
II. TỔNG QUAN VỀ VẤN ĐỀ KHỬ ĐỆ QUY .32
III. CÁC TRƯỜNG HỢP KHỬ ĐỆ QUY ĐƠN GIẢN 33
1. Các trường hợp khử đệ quy bằng vòng lặp .33
2. Khử đệ quy hàm đệ quy arsac 41
3. Khử đệ quy một số dạng thủ tục đệ quy thường gặp 45
Phần II 52
CHƯƠNG IV 52
I. CÁC GIAI ĐOẠN TRONG CUỘC SỐNG CỦA MỘT PHẦN MỀM .52
1) Đặc tả bài toán 52
2) Xây dựng hệ thống 52
3) Sử dụng và bảo trì hệ thống 53
II. ĐẶC TẢ .53
1. Đặc tả bài toán .53
2. Đặc tả chương trình (ĐTCT) .54
3. Đặc tả đoạn chương trình 55
III. NGÔN NGỮ LẬP TRÌNH 57
CHƯƠNG V 59
I. CÁC KHÁI NIỆM VỀ TÍNH ĐÚNG .59
II. HỆ LUẬT HOARE (HOARES INFERENCE RULES) 59
1. Các luật hệ quả (Consequence rules) .60