zunia.vn

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

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Chương 3 Các phương pháp tìm kiếm và sắp xếp

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

Báo xấu

91
lượt xem 5
download

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

Vấn đề tìm kiếm và sắp xếp dữ liệu đề kiế và xế dữ liệu Nội dung Nội 1 2 3 4 Đệ qui Tìm kiếm đệ qui Các phương pháp tìm kiếm Các phương pháp sắp xếp. Tìm kiếm và sắp xếp dữ liệu là hai thao tác thường xuyên được thực hiện trong khai thác thông tin Tùy thuộc vào cấu trúc lưu trữ của dữ liệu các thuật toán được xây dựng có mức độ hiệu quả khác nhau Có thể chia thành hai nhóm: các thuật toán thao tác trên bộ nhớ chính (RAM) và trên bộ...

Chủ đề:

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

Lưu

Nội dung Text: Chương 3 Các phương pháp tìm kiếm và sắp xếp

Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Vấn đề tìm kiếm và sắp xếp dữ liệu đề kiế và xế dữ liệ Tìm kiếm và sắp xếp dữ liệu là hai thao tác Nội dung Nội thường xuyên được thực hiện trong khai thác thông tin 1 Đệ qui Tùy thuộc vào cấu trúc lưu trữ của dữ liệu các 2 Tìm kiếm đệ qui thuật toán được xây dựng có mức độ hiệu quả 3 khác nhau Các phương pháp tìm kiếm Có thể chia thành hai nhóm: các thuật toán thao 4 Các phương pháp sắp xếp tác trên bộ nhớ chính (RAM) và trên bộ nhớ ngoài (các ổ đĩa) 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Đệ qui Đệ qui Khái niệm Khá niệ Khái niệm Khá niệ Một đối tượng X gọi là được định nghĩa đệ qui nếu nghĩ đệ trong phát biểu của X có dùng chính đối tượng X Một chương trình đệ qui là chương trình gọi đến Ví dụ: “Người giàu là người có nhiều tài sản hoặc có cha chính nó trong các câu lệnh, chương trình đệ qui mẹ là người giàu” – trực tiếp bắt buộc phải có điều kiện dừng “Gà Trứng Gà” – gián tiếp Nhược điểm của đệ qui Định nghĩa bằng đệ quy có ưu điểm: Không phải bài toán nào cũng dùng đệ qui được Sáng sủa Sử dụng nhiều bộ nhớ để lưu trữ tạm thời các biến Dễ hiểu trong lúc chạy đệ qui Nêu bật được vấn đề 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Hàm đệ qui đệ Đệ qui Một hàm đệ quy về căn bản luôn gồm 2 phần. Khái niệm Khá niệ Phần dừng: Chứa các tác động của hàm ứng với 1 số giá trị ban đầu của tham số Một định nghĩa đệ qui thường có 2 thành phần Phần hạ bậc: Chứa lời gọi thực hiện hàm với tham số Thành phần cố định (điều kiện dừng) : không có lời có phạm vi nhỏ hơn. gọi đệ qui Ví dụ: Xây dựng hàm tính n! theo đệ Ví dụ: Tính UCLN(x,y) theo thuật toán Ví dụ: 0! = 1! = 1 qui. Euclide Thành phần đệ qui : ứng với tham số có lời gọi đệ long giaithua(int n) int ucln(int x, int y) qui đến tham số khác, dần tiến về thành phần cố định { { if (n == 0 || n == 1) return 1; if (y == 0) return x; Ví dụ: n! = n*(n-1)! Nếu n > 1 else return (n * giaithua(n-1)); else return (ucln(y, x % y)); } } 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Tìm kiếm đệ qui kiế đệ Hàm tìm kiếm đệ qui tì kiế đệ /* Xác định thành phần xi bằng đệ quy */ Xây dựng dần các thành phần của một lời giải hay một cấu dự dầ cá thà phầ củ mộ lờ giả mộ cấ void Try( int i ) hình bằng cách thử tất cả các khả năng. bằ cá thử cả khả năng. { int j; If (i > N) < ghi nhận 1 cấu hình>; Ví dụ: liệt kê các dãy nhị phân có độ dài n bit liệ cá nhị có độ else { Với n=3 Bit 2 Bit 1 Bit 0 for (j thuộc tập khả năng đề cử ) 0 0 0 if < chấp nhận khả năng ( j )> then 0 0 1 3 bit ~ 8 khả năng { < Xác định xi theo khả năng ( j ) > 0 1 0 ; 0 1 1 Một “cấu hình” Try( i+1); 1 0 0 < bỏ việc ghi nhận khả năng ( j ) đã chọn cho xi >; 1 0 1 } 1 1 0 } 1 1 1 } 3/11/2010 www.lhu.edu.vn 3/11/2010 www.lhu.edu.vn
Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Chương 3 Các phương pháp tìm kiếm và sắp xếp Cá pháp tì kiế và xế Ví dụ: Liệt kê các dãy nhị phân có độ dài n. CTDL: Mảng byte: char X[20]; chứa dãy nhị phân tối đa 20 bit Một số ví dụ cơ bản về đệ qui số bả về đệ Khả năng đề cử cho 1 thành phần (1 bit) X[i] là: 0 và 1 Bài toán Tháp Hà Nội void Try(int i) { int j; Bài toán liệt kê hoán vị if ( i > n ) InKetqua; Bài toán 8 quân Hậu else for (j =0; j

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.