Cơ bản về cấu trúc dữ liệu và giải thuật – Đệ quy (P2)

Thảo luận trong 'ACM/Programming' bắt đầu bởi trungndm, 27/02/17, 09:02 AM.

  1. trungndm

    trungndm VIP Members

    Tham gia: 24/08/16, 09:08 PM
    Bài viết: 7
    Đã được thích: 6
    Điểm thành tích:
    3
    Hôm nay, chúng ta sẽ tìm hiểu sâu hơn về 2 kỹ thuật đệ quy nâng cao hơn. Đó là Đệ quy có nhớ Quay lui (Backtracking)

    Đệ quy có nhớ:
    Xét bài toán tính C(k,n) đã trình bày giải thuật ở phần trước
    Ta có sơ đồ như sau với C(3,5)
    [​IMG]

    Ở đây có thể thấy có 1 vài công thức bị lặp lại như C(2,3), C(1,2),…
    Nếu dùng đệ quy để tính lại các công thức này sẽ mất rất nhiều thời gian
    Để giảm bớt thời gian tính toán, ta có thể lưu lại các giá trị đã biết vào 1 mảng để sau này khi gặp lại chỉ việc lấy giá trị ra chứ không cần tính lại.
    Như ví dụ trên có thể lưu vào 1 mảng 2 chiều n*n :

    Giải thuật mới :
    Mã:
    long D[100][100] ;
    long C( int k , int n ) {
         if ( k == 0 | | k == n ) D[k][n] = 1 ;
    else {
         if (D[k][n]
     
    Chỉnh sửa cuối: 30/11/17, 02:11 PM
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
    avnh thích bài này.