Bài giảng Cấu trúc dữ liệu và giải thuật: Thuật toán đệ quy

Bài giảng Cấu trúc dữ liệu và giải thuật - Thuật toán đệ quy gồm có những nội dung chính sau đây: Định nghĩađệquy, thuật toánđệquy, phân tích thuật toánđệquy, đệquy có nhớ, thuật toán quay lui (backtracking algorithm). Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Thuật toán đệ quy 1/10/2011 REVIEW Xácđịnhmốiquanhệgiữacáccặphàm và sau đây .a 3 1 , 6b 3 1 , .c 2 , THUẬTTOÁNĐÊQUYNộidung Địnhnghĩađệquy  Đốitượngbaogồmchínhnó  Địnhnghĩađệquy hoặcđượcđịnhnghĩadưới dạngchínhnó.  Thuậttoánđệquy VD.Địnhnghĩamộtcôngthứchợp  Phântíchthuậttoánđệquy lệ củacácbiến,sốvàcácphéptoán , ,∗,/, ^  Đệquycónhớ  làcôngthứchợplệnếu là  Thuậttoánquaylui(backtrackingalgorithm) biếnhoặcsố  Nếu , làcôngthứchợplệthì , , ∗ , / , ^ cũnglàcôngthứchợplệ 1 1/10/2011Hàmđượcđịnhnghĩađệquy Địnhnghĩađệquy  Mọiđịnhnghĩađệquyđềugồm2phần 1 ế 0  !  Mộttrườnghợpcơsở(nhỏnhất)cóthểxửlýtrựctiếpmàkhông 1 ! ế 0 cầnđệquy,và  Mộtphươngthứctổngquátmàbiếnđổimộttrườnghợpcụthểvề cáctrườnghợpnhỏhơn.Dođóbiếnđổicáctrườnghợpchođến 1 ế 1, 2 khivềtrườnghợpcơsở.  1 2 ế 2 0 ế 0  1 ế 1 2 1 2 ế 1 Danh sách banđầuThuậttoánđệquy Chia lần 1Thuậttoáncóchứalờigọiđệquyđếnchínhnóvớiđầuvàokíchthướcnhỏhơn. Chia lần 2 VD.Sắpxếptrộn– MergeSort MergeSort(intA[],intstart,intend) { Chia lần 3 if(start 1/10/2011Thuậttoánđệquy Phântíchthuậttoánđệquy Môtảthờigianthựchiệncủathuậttoánđệquybằng côngthứcđệquy  GiảicôngthứcđệquyđểtìmΘ hoặcΟ bằng: VD.MergeSortcó Ο 1 ế 1  Phươngphápthaythế 2 Ο ế 1  Phươngphápcâyđệquy 2  Dùngđịnhlýthợ Bỏqua vớicácgiátrịnnhỏ(coilàhằng).Tacóthểviếtlại là 2 Ο 2 Phươngphápthaythế ...