zunia.vn

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

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Chương 2: Giải thuật đệ quy

Chia sẻ: Thanh Hoa | Ngày: | Loại File: PDF | Số trang:2

Báo xấu

191
lượt xem 9
download

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

Bài giảng "Chương 2: Giải thuật đệ quy" cung cấp cho người đọc các kiến thức về: Khái niệm đệ quy, giải thuật đệ quy, thiết kế giải thuật đệ quy, hiệu lực của đệ quy. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Chương 2: Giải thuật đệ quy

27/02/12 NỘI DUNG Chương 2  Khái niệm đệ quy Giải thuật đệ quy GIẢI THUẬT ĐỆ QUY   Thiết kế giải thuật đệ quy  Hiệu lực của đệ quy 2 2.1 KHÁI NIỆM ĐỆ QUY 2.2 GIẢI THUẬT ĐỆ QUY  Một đối tượng được gọi là đệ quy nếu nó bao gồm chính  Nếu lời giải của của một bài toán T được giải bằng lời nó như một bộ phận hoặc được định nghĩa bởi chính nó. giải của một bài toán T1, có dạng giống như T thì lời giải  Ví dụ : Số tự nhiên đó được gọi là lời giải đệ quy. Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. +1 là số tự nhiên.  Ở đây T1 có dạng giống T nhưng theo một nghĩa nào đó + n là số tự nhiên nếu n-1 là số tự nhiên. T1 phải “nhỏ” hơn T. Giai thừa của số n (n!)  Chẳng hạn với bài toán tính n!, thì tính n! là bài toán T + 0! = 1 còn tính (n -1)! là bài toán T1 ta thấy T1 cùng dạng với T nhưng nhỏ hơn (n -1 < n). + Nếu n>0 thì n! = n*(n-1)! 3 4 2.3 THIẾT KẾ GIẢI THUẬT ĐỆ QUY Ví dụ 1  Khi bài toán đang xét hoặc dữ liệu đang xử lý được định  Hàm n! nghĩa dưới dạng đệ quy thì việc thiết kế các giải thuật đệ 1 nÕu n  0 quy tỏ ra rất thuận lợi. Hầu như nó phản ánh rất sát nội Factorial (n)   n * Factorial( n - 1) nÕu n  0 dung của định nghĩa đó  Giải thuật đệ quy được viết dưới dạng hàm như sau  Không có giải thuật đệ quy vạn năng cho tất cả các bài int Factorial (int n) toán đệ quy, nghĩa là mỗi bài toán cần thiết kế một giải { if (n==0) return 1; thuật đệ quy cho phù hợp else return n*Factorial(n-1); } 5 6 1
27/02/12 Ví dụ 2 Đặc điểm của giải thuật đệ quy  Bài toán dãy số FIBONACI  Trong hàm đệ quy có lời gọi đến chính hàm đó 1 nÕu n  2 F (n)    Sau mỗi lần có lời gọi đệ quy thì kích thước của bài F(n - 2)  F(n - 1) nÕu n  2 (Với n>0) toán được thu nhỏ hơn trước. int Fibonaci (int n)  Có it nhất một trường hợp suy biến xảy ra. Khi đó bài { if (n

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.