intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Đệ quy nâng cao - Nguyễn Minh Huy

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST
Báo xấu
7
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Đệ quy nâng cao, được biên soạn gồm các nội dung chính sau Nhận xét về đệ quy; Các bài toán kinh điển. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình: Đệ quy nâng cao - Nguyễn Minh Huy

  1. Đ quy nâng cao GV. Nguy n Minh Huy K thu t l p trình - Nguy n Minh Huy 1
  2. N i dung Nh n xét v đ quy. quy. Các bài toán kinh đi n. n. K thu t l p trình - Nguy n Minh Huy 2
  3. N i dung Nh n xét v đ quy. quy. Các bài toán kinh đi n. n. K thu t l p trình - Nguy n Minh Huy 3
  4. Nh n xét v đ quy Khái ni m Call Stack: void main() main() { Vùng nh lưu tr ng thái A(); các hàm đang th c hi n. n. D(); } Thông tin tr ng thái: thái: Tham s hàm. hàm. void A() void C() { { Bi n c c b . B(); V trí dòng l nh hi n hành. hành. C(); } } D void B() void D() STACK { { B B B C D(); A A A A A A A D } } M M M M M M M M M M M Th i gian K thu t l p trình - Nguy n Minh Huy 4
  5. Nh n xét v đ quy L i Stack Overflow: Tràn b nh Call Stack. Không th g i hàm thêm n a!! a!! Nguyên nhân: nhân: Công th c đ quy không h i t . S bư c đ quy quá l n. n. Kh đ quy: quy: Dùng vòng l p. p. Dùng ngăn x p. p. K thu t l p trình - Nguy n Minh Huy 5
  6. Nh n xét v đ quy Khái ni m Call Tree: Th hi n liên h gi a các hàm. hàm. main Giúp hình dung các bư c g i hàm. hàm. S nút: t ng s l i g i hàm. nút: hàm. Chi u cao: kích thư c Call Stack. cao: A D B C D K thu t l p trình - Nguy n Minh Huy 6
  7. Nh n xét v đ quy Ưu đi m đ quy: quy: L i gi i đ quy nêu b n ch t v n đ : Thu t toán rõ ràng, sáng s a. ràng, a. Chương trình ng n g n, d hi u. n, u. Nhi u bài toán ph c t p n u không dùng đ quy. quy. Gi m th i gian suy nghĩ. nghĩ. Đơn gi n hóa l p trình. trình. K thu t l p trình - Nguy n Minh Huy 7
  8. Nh n xét v đ quy Khuy t đi m đ quy: quy: Các hàm đ quy l ng nhau: nhau: Gây khó khăn cho vi c debug. T n b nh lưu tr hàm. hàm. T c đ x lý ch m. m. Nhi u v n đ cài đ t đ quy không hi u qu . Nhi u bài toán không th gi i b ng đ quy. quy. Không nên l m d ng đ quy!! quy!! K thu t l p trình - Nguy n Minh Huy 8
  9. N i dung Nh n xét v đ quy. quy. Các bài toán kinh đi n. n. K thu t l p trình - Nguy n Minh Huy 9
  10. Các bài toán kinh đi n Tháp Hà N i: i: Bài toán: toán: Có 3 c t A, B, C. C t A có N đĩa theo th t l n dư i, nh trên. i, trên. Hãy chuy n N đĩa t c t A sang c t C: M i l n chuy n 1 đĩa. đĩa. Đĩa nh luôn trên đĩa l n.n. Có th dùng c t trung gian. gian. 1 2 N C t ngu n A C t trung gian B C t đích C K thu t l p trình - Nguy n Minh Huy 10
  11. Các bài toán kinh đi n Tháp Hà N i: i: Áp d ng k thu t chia đ tr : Chuy n( N đĩa, A -> C, B trung gian ) n( đĩa, { if ( N == 1 ) L y A b qua C; else { // Chia làm 2 ph n: N – 1 đĩa nh và 1 đĩa l n. n: n. Chuy n( N – 1 đĩa, A -> B, C trung gian ); n( đĩa, L y A b qua C; Chuy n( N – 1 đĩa, B -> C, A trung gian ); n( đĩa, } } K thu t l p trình - Nguy n Minh Huy 11
  12. Các bài toán kinh đi n Tám H u: u: Bài toán: toán: Cho bàn c vua 8 x 8 ô. Hãy đ t 8 quân H u lên bàn c . Sao cho các quân H u không ăn l n nhau: nhau: Không cùng dòng. dòng. Không cùng c t. t. Không cùng đư ng chéo xuôi. xuôi. Không cùng đư ng chéo ngư c.c. K thu t l p trình - Nguy n Minh Huy 12
  13. Các bài toán kinh đi n Tám H u: u: Phân tích: tích: Ch có th đ t H u vào ô chưa b ki m soát. soát. Đ t H u vào ô (i, j), nh ng ô nào s b ki m soát? (i soát? Nh ng ô b ki m soát có liên h gì v i (i, j)? C tj Dòng i Chéo xuôi i + j - n Chéo ngư c i – j + n K thu t l p trình - Nguy n Minh Huy 13
  14. Các bài toán kinh đi n Tám H u: u: Áp d ng k thu t l n ngư c: c: Th đ t( ô (i, j), dòng, c t, chéo xuôi, chéo ngư c ) t( (i dòng, t, xuôi, { if ( ô (i, j) đã b ki m soát ) (i return; C p nh t ki m soát; soát; if ( i là dòng cu i ) Xu t k t qu ; else for (int k = 0; k < 7; k++) (int Th đ t( ô (i + 1, k), dòng, c t, chéo xuôi, chéo ngư c ); t( (i k), dòng, t, xuôi, Quay lui ki m soát; soát; } K thu t l p trình - Nguy n Minh Huy 14
  15. Các bài toán kinh đi n Mã đi tu n: n: Bài toán: toán: Cho bàn c vua 8 x 8 ô. Đ t 1 quân mã 1 ô b t kỳ.kỳ. Hãy tìm l trình đi quân mã: mã: Đi theo lu t c vua. vua. M i ô đi qua đúng m t l n. n. Đi qua t t c các ô bàn c . 5 6 4 7 3 8 2 1 K thu t l p trình - Nguy n Minh Huy 15
  16. Các bài toán kinh đi n Mã đi tu n: n: Phân tích: tích: Ch có th đi Mã vào nh ng ô chưa đi qua. Đ t Mã t i ô (i, j), nh ng ô nào có th đi qua? (i Nh ng ô có th đi qua có liên h gì v i (i, j)? 1: (i + 2, j + 1) (i 2: (i + 2, j – 1) (i 3: (i + 1, j – 2) (i 5 6 4: (i – 1, j – 2) (i 4 7 5: (i – 2, j – 1) (i 6: (i – 2, j + 1) (i 3 8 7: (i – 1, j + 2) (i 2 1 8: (i + 1, j + 2) (i K thu t l p trình - Nguy n Minh Huy 16
  17. Các bài toán kinh đi n Mã đi tu n: n: Áp d ng k thu t l n ngư c: c: Th đi( ô (i, j), bàn c , bư c ) đi( (i { if ( đã đi ô (i, j) ) (i return; C p nh t tr ng thái bàn c ; if ( bư c cu i ) Xu t k t qu ; else Th đ t( ô (i + 2, j + 1), bàn c , bư c + 1 ); t( (i 1), Th đ t( ô (i + 2, j – 2), bàn c , bư c + 1 ); t( (i 2), Quay lui tr ng thái bàn c ; } K thu t l p trình - Nguy n Minh Huy 17
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2