Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2

Đăng ngày | Thể loại: | Lần tải: 0 | Lần xem: 0 | Page: 68 | FileSize: M | File type: PDF
of x

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2. Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2 Thuật toán đệ quy với các nội dung chính như: Khái niệm đệ quy, thuật toán đệ quy, phân tích thuật toán đệ qui, chứng minh tính đúng đắn của thuật toán đệ qui. Giống những tài liệu khác được bạn đọc giới thiệu hoặc do sưu tầm lại và giới thiệu lại cho các bạn với mục đích học tập , chúng tôi không thu tiền từ thành viên ,nếu phát hiện tài liệu phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho website ,Ngoài tài liệu này, bạn có thể tải bài giảng miễn phí phục vụ nghiên cứu Một số tài liệu download mất font không hiển thị đúng, thì do máy tính bạn không hỗ trợ font củ, bạn tải các font .vntime củ về cài sẽ xem được.

https://tailieumienphi.vn/doc/bai-giang-cau-truc-du-lieu-va-thuat-toan-chuong-2-01obuq.html

Nội dung


Chương 2: Thuật toán đệ quy
Trịnh Anh Phúc, Nguyễn Đức Nghĩa
1 Bộ

1

môn Khoa Học Máy Tính, Viện CNTT & TT,
Trường Đại Học Bách Khoa Hà Nội.

Ngày 14 tháng 7 năm 2015

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015
Ngày 14 tháng

1 / 67

Giới thiệu
1

Khái niệm đệ quy
Hàm đệ qui
Tập hợp được xác định đệ qui

2

Thuật toán đệ qui

3

Một số ví dụ minh họa

4

Phân tích thuật toán đệ qui

5

Chứng minh tính đúng đắn của thuật toán đệ qui

6

Thuật toán quay lui
Bài toán xếp hậu
Bài toán mã tuần

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015
Ngày 14 tháng

2 / 67

Khái niệm đệ quy

Thuật toán đệ qui

Khái niệm đệ qui
Trong thực tế chúng ta thường gặp những đối tượng đệ quy bao gồm
chính nó hoặc được định nghĩa bởi chính nó. Ta nói các đối tượng đó được
xác định một cách đệ qui
Điểm quân số
Các hàm được định nghĩa đệ qui
Tập hợp được định nghĩa đệ qui
Định nghĩa đệ qui về cây
Fractal ....

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015
Ngày 14 tháng

3 / 67

Khái niệm đệ quy

Hàm đệ qui

Hàm đệ qui (resursive functions)

Định nghĩa
Các hàm đệ qui được xác định bởi số nguyên không âm n theo sơ đồ
Bước cơ sở (Basic step) : Xác định giá trị hàm tại thời điểm n = 0
hay f (0)
Bước đệ qui (Recursive step) : Cho giá trị của hàm f (k) tại k ≤ n
đưa ra qui tắc tính giá trị của f (n + 1).

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015
Ngày 14 tháng

4 / 67

Khái niệm đệ quy

Hàm đệ qui

Hàm đệ qui (resursive functions)
VD1 :
f (0) = 3 n = 0
f (n + 1) = 2f (n) + 3 n > 0
VD2 :
f (0) = 1
f (n + 1) = f (n) × (n + 1)

VD3 : Định nghĩa đệ qui tổng sn =

n
i=1 ai

s 1 = a1
sn = sn−1 + an

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 7 năm 2015
Ngày 14 tháng

5 / 67

1116934

Tài liệu liên quan


Xem thêm