Giáo trình môn Kỹ thuật lập trình nâng cao

Trong nhiều tình huống việc mô tả các bài toán, các giải thuật, các sự kiện, các sự vật các quá trình, các cấu trúc, . . . sẽ đơn giản và hiệu quả hơn nếu ta nhìn được nó dưới góc độ mang tính đệ qui. Mô tả mang tính đệ qui về một đối tượng là mô tả theo cách phân tích đối tượng thành nhiều thành phần mà trong số các thành phần có thành phần mang tính chất của chính đối tượng được mô tả. Tức là mô tả đối tượng qua chính nó. Phương...
Nội dung trích xuất từ tài liệu:
Giáo trình môn Kỹ thuật lập trình nâng cao TRƯỜNG ĐẠI HỌC ĐÀ LẠT TRUNG TÂM TIN HỌC B&T SƯU TẦM GIÁO TRÌNH KỸ THUẬT LẬP TRÌNH NÂNG CAO TRẦN HOÀNG THỌ 2002 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 1-3- 2. Tiên đề gán (The Assignement Axiom) .....................................................................61 3. Các luật về các cấu trúc điều khiển . ........................................................................61 III. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH KHÔNG CÓ VÒNG LẶP. .............................64 IV. KIỂM CHỨNG ĐOẠN CHƯƠNG TRÌNH CÓ VÒNG LẶP. ...........................................68 1. Bất biến......................................................................................................................68 2. Lý luận quy nạp và chứng mi ...