Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu
lượt xem 8
download
Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu trình bày những nội dung về đệ qui (recurve), khái niệm đệ qui, thuật giải quay lui (back tracking), kỹ thuật nhánh cận. Mời các bạn tham khảo.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật giải - Tạ Thúc Nhu
- Một số vấn đề cơ sở của Tin học Buổi 3: Cấu trúc dữ liệu và thuật giải Giáo viên: Tạ Thúc Nhu Khoa CNTT trường ĐH Lạc Hồng
- ĐỆ QUI RECURVE 2 Mã hóa
- Khái niệm Đệ Qui Một đối tượng được gọi là đệ qui nếu nó hoặc 1 phần của nó được định nghiã thông qua khái niệm về chính nó. Ví dụ: Định nghiã phép toán giai thừa, ký hiệu: N! • (a) Nếu N = 0, thì N! = 1 • (b) nếu N > 0 thì N! = N*(N-1)! Ví dụ: Định nghiã UCLN của 2 số x và y, ký hiệu: UCLN(x, y) • (a)UCLN(x,y) = x nếu y = 0 • (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y0 3 Mã hóa
- Chương trình đệ qui • Một chương trình là đệ qui nếu trong chương trình có lời gọi đến chính nó. Ví dụ: Định nghĩa hàm tính N! theo đệ qui. int GiaiThua(int N) { if (N == 0) return 1; return N * GiaiThua(N - 1); } 4 Mã hóa
- Một định nghiã đệ qui phải có 2 thành phần: • Thành phần dừng: Không chứa khái niệm đang định nghiã Ví dụ: N! = 1 • Thành phần đệ qui: có chứa khái niệm đang định nghiã 5 Mã hóa
- Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide • (a)UCLN(x,y) = x nếu y = 0 • (b)UCLN(x,y) = UCLN(y, phần dư của x/y) nếu y0 int UCLN(int x, int y) { if (y == 0) return x; return UCLN(y, x % y); } 6 Mã hóa
- THUẬT GIẢI QUAY LUI BACK TRACKING 7 Mã hóa
- Tổng quan thuật giải Quay lui (Back Tracking) • Dùng giải bài toán liệt kê các cấu hình • Mỗi cấu hình được xác định bằng cách xây dựng tuần tự từng thành phần trong cấu hình. • Mỗi thành phần được xác định bằng cách chọn lựa dữ liệu trong tập khả năng được đề xuất. Cấu hình một lời giải X1 X2 X3 … Xn Tập khả năng K1 K2 … … Km 8 Mã hóa
- Mô hình thuật giải quay lui: Xác định phần tử Xi bằng đệ quy void Try( int i ) { If (Xi là phần tử cuối cùng trong cấu hình) < Thông báo cấu hình tìm được>; else for ( mọi Kj thuộc tập khả năng đề cử cho Xi) [ if ( Chấp nhận Kj ) ] { Thử chọn Kj cho Xi; Try( i+1); //Gọi đệ quy để xác định phần tử Xi+1 Bỏ ghi nhận Kj đã chọn cho Xi để chọn khả năng khác; } } 9 Mã hóa
- Hai điểm mấu chốt quyết định độ phức tạp của bài toán là: 1. Xác định tập khả năng đề cử: Phụ thuộc vào việc phân tích nhu cầu dữ liệu của từng thành phần trong cấu hình 2. Kiểm tra khả năng đề cử phải phù hợp với thành phần cần xác định. 10 Mã hóa
- Bài toán: Liệt kê các dãy nhị phân có độ dài n Phân tích: • Biểu diến cấu hình dãy nhị phân dưới dạng: X[1..n] • Tập khả năng đề cử cho mỗi phần tử Xi là {0, 1} • Thuật giải xác định phần tử Xi của dãy nhị phân như sau: void Try(int i) { if ( i > n ) ; else for (int j =0; j
- Mã đi tuần: chỉ ra hành trình của quân Mã xuất phát từ một ô trên bàn cờ đi qua tất cả các ô còn lại của bàn cờ, mỗi ô đúng 1 lần. Phân tích: • Cấu hình lời giải là BC[1..n][1..n] chứa số thứ tự hành trình của 2 (u, v) quân Mã. • Tập khả năng chứa các giá trị dùng tính tọa độ các ô kế tiếp 1 (x, y) dx[1..8] = {-2,-1, 1, 2, 2, 1, -1, -2} dy[1..8] = { 1, 2, 2, 1, -1, -2, -2, -1} • Điều kiện chọn khả năng cho bước đi thứ i là Ô được chọn phải : – Thuộc bàn cờ – Và chưa đi qua 12 Mã hóa
- Thuật giải xác định bước đi thứ i của quân Mã void Try(int i) { int j,u,v; if (i > n*n) ; else for ( j =1; j = 1 && u = 1 && v
- Bài toán: Liệt kê các hoán vị của dãy số {1, 2, .., n} • Biểu diễn cấu hình một hoán vị: X[1..n] • Tập khả năng đề cử: { 1, 2, .., n } • Nhưng do Xi Xj với i j. Nên phải kiểm tra giá trị đề cử cho Xi phải khác với các giá trị đã chọn cho các thành phần trước đó. Hướng giải quyết chung là tổ chức các biến trạng thái lưu trữ thông tin phục vụ cho việc kiểm tra: Dùng mảng F[1..n] để ghi nhớ tình trạng sử dụng của từng khả năng trong tập S={1, 2, .., n}, với qui ước: F[ j ] = 0 nếu j chưa sử dụng F[ j ] = 1 nếu j đã sử dụng 14 Mã hóa
- Thuật giải xác định phần tử Xi của một hoán vị void Try(int i) { if ( i > n ) ; else for (int j = 1; j
- Ví dụ: Liệt kê các tập con k phần tử của tập S = {1, 2, .., n}. Trong đó (k
- Thuật giải xác định phần tử Xi của một tập con void Try(int i) { if ( i > K ) ; else for (int j = 1; j
- Một cách giải khác của bài toán tập con Đưa ra điều kiện cho mỗi tập con là : 1
- Thuật giải xác định phần tử Xi của một tập con void Try(int i) { if ( i > K ) ; else for (int j = X[i-1]+1; j
- KỸ THUẬT NHÁNH CẬN 20 Mã hóa
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu cơ bản và giải thuật - Chương 1
9 p | 258 | 29
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 176 | 17
-
Bài giảng Cấu trúc dữ liệu: Chương 10 - Nguyễn Xuân Vinh
31 p | 95 | 10
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 81 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 117 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 87 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 61 | 7
-
Bài giảng Cấu trúc dữ liệu: Chương Giới thiệu - Nguyễn Xuân Vinh
8 p | 112 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 170 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu
10 p | 69 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 107 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 70 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các khái niệm cơ bản
23 p | 48 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 52 | 2
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