Cơ bản về cấu trúc dữ liệu và giải thuật – Phần một: Đệ quy

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

  1. trungndm

    trungndm VIP Members

    Tham gia: 24/08/16, 09:08 PM
    Bài viết: 4
    Đã được thích: 5
    Điểm thành tích:
    3
    Cấu trúc dữ liệu và giải thuật đóng vai trò quan trọng trong việc kết hợp thuật toán để đưa ra cách giải quyết bài toán. Một bài toán bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên những đối tượng đó. Do đó cần phải xây dựng lên một cấu trúc dữ liệu phù hợp trên các đối tượng nhằm phản ánh quan hệ giữa các đối tượng và hình thành giải thuật là các thao tác trên các đối tượng dữ liệu.

    Giải thuật đệ quy
    Đệ quy (Recursion) là một trong những giải thuật rất quen thuộc trong lập trình. Một số bài toán buộc phải dùng đệ quy mới giải quyết được (như bài toán duyệt cây). Đệ quy là một giải thuật chứa thao tác gọi lại chính nó. Điều này giúp mô tả một dãy lớn các thao tác bằng một số thao tác ngắn gọn trong đó chứa thao tác gọi lại chính nó.

    Hôm nay, chúng ta sẽ cùng tìm hiểu một số khái niệm cơ bản về giải thuật đệ quy và một số bài toán kinh điển sử dụng đệ quy.

    Định nghĩa hàm đệ quy
    Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.
    Một hàm đệ quy f(n) được xác định dựa trên giản đồ sau:
    Phần cơ bản: Điều kiện thoát khỏi đệ quy, bao gồm một giá trị hoặc một tập giá trị ban đầu: f(0),f(1),..
    Phần đệ quy: Tính f(n+1) dựa trên một giá trị f(k) đã biết trước đó
    Ví dụ:
    Tính n! = (n-1)! * n
    Dãy fibonacy: f(n) = f(n-1)+ f(n-2)

    Giải thuật đệ quy
    Là thuật toán gọi lại chính nó với tham số nhỏ hơn.
    Phù hợp để xử lý các đối tượng định nghĩa đệ quy
    Ngôn ngữ lập trình cấp cao cho phép người lập trình thiết kế các hàm và thủ tục đệ quy.
    Thuật toán: RecAlg(n)
    Giả sử giá trị f(một),f(2),..f(k) ban đầu đã biết
    If n
     
    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
  2. Leukocytes

    Leukocytes New Member

    Tham gia: 03/11/17, 06:11 PM
    Bài viết: 2
    Đã được thích: 1
    Điểm thành tích:
    3
    bài này chưa được hoàn thiện ạ?
     
    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
    tmnt53 thích bài này.
  3. tmnt53

    tmnt53 Moderator Thành viên BQT

    Tham gia: 25/04/15, 09:04 AM
    Bài viết: 91
    Đã được thích: 71
    Điểm thành tích:
    18
    Thanh niên @trungndm đâu ấy nhỉ sao bài chưa viết xong này :v
     
    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
    Leukocytes thích bài này.