zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Đệ quy và thuật toán đệ quy

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

Báo xấu

348
lượt xem 109
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đệ quy (tiếng Anh: recursion) là phương pháp dùng trong các chương trình máy tính trong đó có một hàm tự gọi chính nó. rong toán học và khoa học máy tính, các tính chất (hoặc cấu trúc) được gọi là đệ quy nếu trong đó một lớp các đối tượng hoặc phương pháp được xác định bằng việc xác định một số rất ít các trường hợp hoặc phương pháp đơn giản (thông thường chỉ một) và sau đó xác định quy tắc đưa các trường hợp phức tạp về các trường hợp đơn giản....

Chủ đề:

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

Lưu

Nội dung Text: Đệ quy và thuật toán đệ quy

19/08/2011 Nội dung 1. Đệ quy và giải thuật đệ quy 2. Stack và đệ quy 3. Các loại đệ quy 4. Đệ quy và hình học fractal 5. Kỹ thuật tìm giải thuật đệ quy 7 Stack và đệ quy  Stack (chồng) là một cấu trúc dữ liệu đặc biệt có 2 thao tác cơ bản Push: đưa phần tử vào đầu stack  Pop: lấy phần tử đầu ra khỏi stack   Nguyên lý hoạt động: Last In First Out  Là linh hồn của đệ quy 4 3 2 1 8 Stack và đệ quy  Ví dụ đệ quy tính giai thừa: int Fact(int N) { if (N
19/08/2011 Các loại đệ quy  Đệ quy nhánh Bài toán tháp Hà Nội: chuyển 2 đĩa từ cột 1 sang cột 3  1 2 3 19 Các loại đệ quy  Đệ quy nhánh Bài toán tháp Hà Nội: chuyển 2 đĩa từ cột 1 sang cột 3  1 2 3 20 Các loại đệ quy  Đệ quy nhánh Bài toán tháp Hà Nội: chuyển N đĩa từ cột 1 sang cột 3  1 2 3 Company Logo 21 7
19/08/2011 Các loại đệ quy  Đệ quy nhánh Bài toán tháp Hà Nội: chuyển N đĩa từ cột 1 sang cột 3  1 2 3 Company Logo 22 Các loại đệ quy  Đệ quy nhánh Bài toán tháp Hà Nội (chuyển N đĩa từ cột x sang cột y)  void Chuyen(int N, int x, int y) { if (N == 1) cout
19/08/2011 Các loại đệ quy  Đệ quy phi tuyến Lời gọi đệ quy được thực hiện trong vòng lặp  vd: cho dãy được định nghĩa X0 = 1 Xn = n2X0 + (n-1)2X1+…+Xn-1 Yêu cầu: tính giá trị của Xn 25 Các loại đệ quy  Đệ quy phi tuyến Tính Xn = n2X0 + (n-1)2X1+…+Xn-1, biết X0 = 1  double X(int N) { if (N == 0) return 1; double s = 0; for (int i = 0; i < N; i++) s = s + (N – i)*(N – i)*X(i); return s; } 26 Các loại đệ quy  Đệ quy hỗ tương Lời gọi có sự xoay vòng lẫn nhau, như A gọi B, B gọi C, C  gọi A, … Đệ quy hỗ tương là đệ quy rất phức tạp nhưng có những  ứng dụng rất lý thú, chẳng hạn trong hình học fractal 27 9
19/08/2011 Nội dung 1. Đệ quy và giải thuật đệ quy 2. Stack và đệ quy 3. Các loại đệ quy 4. Đệ quy và hình học fractal 5. Kỹ thuật tìm giải thuật đệ quy 31 Đệ quy và hình học fractal  Đường Sierpinski tam giác  Đường Sierpinski hình vuông 32 Đệ quy và hình học fractal  Đường Sierpinski các dạng khác 33 11
19/08/2011 Đệ quy và hình học fractal 34 Nội dung 1. Đệ quy và giải thuật đệ quy 2. Stack và đệ quy 3. Các loại đệ quy 4. Đệ quy và hình học fractal 5. Kỹ thuật tìm giải thuật đệ quy 35 Kỹ thuật tìm giải thuật đệ quy  Thông số hóa bài toán Xác định tham số truyền cho hàm đệ quy  Xác định cấp (kích thước) của bài toán   Tìm mô hình tổng quát để thu nhỏ bài toán Thu nhỏ bài toán theo kích thước   Tìm điều kiện dừng của đệ quy Tìm điều kiện của trường hợp cho lời giải tầm thường  36 12
19/08/2011 Kỹ thuật tìm giải thuật đệ quy  Giải thuật minh họa int Sum(int A[], int N) { if (N == 0) return 0; return Sum(A, N – 1) + A[N – 1]; } 40 Kỹ thuật tìm giải thuật đệ quy  Ví dụ 3: áp dụng tư tưởng tìm kiếm nhị phân để tìm vị trí xuất hiện của số nguyên x trong mảng A gồm N phần tử nguyên Thông số hóa: mảng A, đầu mảng, cuối mảng, giá trị x  Mô hình tổng quát:  A[giữa] = x: tìm thành công A[giữa] < x: tìm từ đầu = giữa + 1 đến cuối x < A[giữa]: tìm từ đầu đến cuối = giữa - 1 Điều kiện dừng: đầu > cuối  41 Kỹ thuật tìm giải thuật đệ quy  Giải thuật minh họa int BinSearch(int A[], int l, int r, int x) { if (l > r) return -1; int m = (l + r)/2; if (A[m] == x) return m; if (A[m] < x) return BinSearch(A, m + 1, r, x); return BinSearch(A, l, m - 1, x); } 42 14
19/08/2011 Kỹ thuật tìm giải thuật đệ quy  Ví dụ 4: cho số nguyên dương N ≤ 1000. Viết hàm đệ quy biểu diễn nhị phân của N Thông số hóa: số nguyên N  Mô hình tổng quát:  Đưa giá trị N % 2 vào stack Gọi đệ quy với cấp N/2 Điều kiện dừng: N = 0  43 Kỹ thuật tìm giải thuật đệ quy  Giải thuật minh họa void BinConvert(int N) { if (N != 0) { BinConvert(N/2); cout

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.