Giáo trình Kỹ thuật lập trình nâng cao ( Trần Hoàng Thọ - ĐH Đà Lạt )

Giáo trình được viết theo nội dung môn học Kỹ thuật lập trình nâng cao với mục đích làm tài liệu tham khảo chính cho môn học. Giáo trình gồm 2 phần chính và một phụ lục : Trình bày về chủ đề đệ quy trong lập trình bao gồm các nội dung sau : Khái niệm đệ quy và vai trò của nó trong lập trình. Cách xây dựng một giải thuật cho một bài toán bằng phương pháp đệ quy.....
Nội dung trích xuất từ tài liệu:
Giáo trình Kỹ thuật lập trình nâng cao ( Trần Hoàng Thọ - ĐH Đà Lạt ) TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT GIAÙO TRÌNH KYÕ THUAÄT LAÄP TRÌNH NAÂNG CAO TRAÀN HOAØNG THOÏ 2002 Kyõ thuaät laäp trình naâng cao -2- MUÏC LUÏC LÔØI NOÙI ÑAÀU ........................................................................................................................ 4 PHAÀN I.................................................................................................................................... 5 CHÖÔNG I ............................................................................................................................. 5 I. MÔÛ ÑAÀU ........................................................................................................................... 5 1. Moâ taû ñeä quy ................................................................................................................ 5 2. Caùc loaïi ñeä quy ............................................................................................................ 6 II. MOÂ TAÛ ÑEÄ QUY CAÙC CAÁU TRUÙC DÖÕ LIEÄU................................................................... 7 III. MOÂ TAÛ ÑEÄ QUY GIAÛI THUAÄT ........................................................................................ 7 1. Giaûi thuaät ñeä quy.......................................................................................................... 7 2. Chöông trình con ñeä quy.............................................................................................. 8 3. Maõ hoùa giaûi thuaät ñeä qui trong caùc ngoân ngöõ laäp trình. ............................................. 11 4. Moät soá daïng giaûi thuaät ñeä quy ñôn giaûn thöôøng gaëp . .............................................. 13 CHÖÔNG II ........................................................................................................................... 16 I. CAÙC NOÄI DUNG CAÀN LAØM ÑEÅ TÌM GIAÛI THUAÄT ÑEÄ QUY CHO MOÄT BAØI TOAÙN. ..... 16 1. Thoâng soá hoaù baøi toaùn. .............................................................................................. 16 2. Phaùt hieän caùc tröôøng hôïp suy bieán (neo) vaø tìm giaûi thuaät cho caùc tröôøng hôïp naøy.16 3. Phaân raõ baøi toaùn toång quaùt theo phöông thöùc ñeä quy. .............................................. 16 II. MOÄT SOÁ BAØI TOAÙN GIAÛI BAÈNG GIAÛI THUAÄT ÑEÄ QUY ÑIEÅN HÌNH. .......................... 17 1. Baøi toaùn thaùp Haø Noäi . ............................................................................................... 17 2. Baøi toaùn chia thöôûng. ................................................................................................. 19 3. Baøi toaùn tìm taát caû caùc hoaùn vò cuûa moät daõy phaàn töû................................................. 21 4. Baøi toaùn saép xeáp maûng baèng phöông phaùp troän (Sort-Merge). ................................. 24 5. Baøi toaùn tìm nghieäm xaáp xæ cuûa phöông trình f(x)=0 . ............................................... 25 CHÖÔNG III .......................................................................................................................... 28 I. CÔ CHEÁ THÖÏC HIEÄN GIAÛI THUAÄT ÑEÄ QUY................................................................ 28 II. TOÅNG QUAN VEÀ VAÁN ÑEÀ KHÖÛû ÑEÄ QUY..................................................................... 32 III. CAÙC TRÖÔØNG HÔÏP KHÖÛ ÑEÄ QUY ÑÔN GIAÛN. ......................................................... 33 1. Caùc tröôøng hôïp khöû ñeä quy baèng voøng laëp . ............................................................ 33 2. Khöû ñeä quy haøm ñeä quy arsac .................................................................................. 41 3. Khöû ñeä quy moät soá daïng thuû tuïc ñeä quy thöôøng gaëp. ............................................... 45 Phaàn II .................................................................................................................................. 52 CHÖÔNG IV.......................................................................................................................... 52 I. CAÙC GIAI ÑOAÏN TRONG CUOÄC SOÁNG CUÛA MOÄT PHAÀN MEÀM ................................. 52 1) Ñaëc taû baøi toaùn .......................................................................................................... 52 2) Xaây döïng heä thoáng .................................................................................................... 52 3) Söû duïng vaø baûo trì heä thoáng ...................................................................................... 53 II. ÑAËC TAÛ ......................................................................................................................... 53 1. Ñaëc taû baøi toaùn........................................................................................................... 53 2. Ñaëc taû chöông trình (ÑTCT)....................................................................................... 54 3. Ñaëc taû ñoaïn chöông trình .......................................................................................... 55 III. NGOÂN NGÖÕ LAÄP TRÌNH.............................................................................................. 57 CHÖÔNG V.......................................................................................................................... 59 I. CAÙC KHAÙI NIEÄM VEÀ TÍNH ÑUÙNG. ................................................................................ 59 II. HEÄ LUAÄT HOARE (HOARES INFERENCE RULES). ................................................... 59 1. Caùc lua ...