intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Kỹ thuật lập trình: Các thuật toán thông dụng - Nguyễn Minh Huy

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

Thêm vào BST
Báo xấu
11
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Kỹ thuật lập trình: Các thuật toán thông dụng, được biên soạn gồm các nội dung chính sau Thuật toán sắp xếp; Thuật toán quy hoạch động. Mời các bạn cùng tham khảo!

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 Kỹ thuật lập trình: Các thuật toán thông dụng - Nguyễn Minh Huy

  1. Các thuật toán thông dụng GV. Nguyễn Minh Huy Kỹ thuật lập trình - Nguyễn Minh Huy 1
  2. Nội dung Thuật toán sắp xếp. xếp. Thuật toán quy hoạch động. động. Kỹ thuật lập trình - Nguyễn Minh Huy 2
  3. Nội dung Thuật toán sắp xếp. xếp. Thuật toán quy hoạch động. động. Kỹ thuật lập trình - Nguyễn Minh Huy 3
  4. Thuật toán sắp xếp Khái niệm sắp xếp: xếp: Bài toán: toán: Cho mảng N phần tử. tử. Bố trí các phần tử theo thứ tự. tự. N! cách bố trí! trí! Các thuật toán: toán: Độ phức tạp Không gian Thuật toán Tốt Xấu Trung bình bộ nhớ Interchange Sort N2 N2 N2 1 Selection Sort N2 N2 N2 1 Merge Sort N logN N logN N logN N Quick Sort N logN N2 N logN logN Kỹ thuật lập trình - Nguyễn Minh Huy 4
  5. Thuật toán sắp xếp Sắp xếp đổi chỗ (Interchange Sort): Ý tưởng: tưởng: Mảng có thứ tự không có nghịch thế! thế! Duyệt tất cả cặp phần tử. tử. Đổi chỗ nếu phát hiện nghịch thế. thế. Cài đặt: đặt: interchange_sort( interchange_sort( mảng A, kích thước N ) { for ( int i = 0; i < N – 1; i++ ) for ( int j = i + 1; j < N; j++ ) if ( a[ j ] < a[ i ] ) // Phát hiện nghịch thế. thế. swap( swap( a[ i ], a[ j ] ); } Kỹ thuật lập trình - Nguyễn Minh Huy 5
  6. Thuật toán sắp xếp Sắp xếp chọn (Selection Sort): Ý tưởng: tưởng: Tìm phần tử nhỏ nhất đưa lên đầu. đầu. Lặp lại với phần còn lại của mảng. mảng. Cài đặt: đặt: selection_sort( selection_sort( mảng A, kích thước N ) { for ( int i = 0; i < N – 1; i++ ) { int min = i; for (int j = i + 1; j < N; j++ ) (int if ( a[ j ] < a[ min ] ) min = j; swap( swap( a[ i ], a[ min ] ); } } Kỹ thuật lập trình - Nguyễn Minh Huy 6
  7. Thuật toán sắp xếp Sắp xếp trộn (Merge Sort): Bài toán trộn 2 mảng có thứ tự: tự: a 1 4 5 7 9 c 1 2 3 4 5 6 7 8 9 b 2 3 6 8 Quyết đinh chọn phần tử ở mảng kết quả: quả: // i, ia, ib lần lược là vị trí đang xét ở mảng c, a, b. ia, if ( a[ ia ] < b[ ib ] ) c[ i ] = a[ ia++ ]; ia++ else c[ i ] = b[ ib++ ]; ib++ c[ i ] = (a[ ia ] < b[ ib ]) ? a[ ia++ ] : b[ ib++ ]; ia++ ib++ Kỹ thuật lập trình - Nguyễn Minh Huy 7
  8. Thuật toán sắp xếp Sắp xếp trộn (Merge Sort): Dùng kỹ thuật chia để trị: trị: merge_sort( merge_sort( mảng A, kích thước N ) { if ( N == 1 ) Kết thúc; thúc; else { Chia đôi A thành A1 và A2; merge_sort(A merge_sort(A1, kích thước A1 ); merge_sort(A merge_sort(A2, kích thước A2 ); merge_array(A merge_array(A1, kích thức A1, A2, kích thước A2, A ); } } Kỹ thuật lập trình - Nguyễn Minh Huy 8
  9. Nội dung Thuật toán sắp xếp. xếp. Thuật toán quy hoạch động. động. Kỹ thuật lập trình - Nguyễn Minh Huy 9
  10. Thuật toán quy hoạch động Khái niệm quy hoạch động: động: Lời giải đệ quy: quy: Trường hợp cơ bản: giải tường minh. bản: Suy biến bài toán về trường hợp đơn giản hơn. hơn. Nếu nhiều trường hợp suy biến trùng lặp? lặp? Xây dựng bảng tra lời giải cho các trường hợp. hợp. Quy hoạch động = Quy hoạch bảng tra lời giải. giải. Bài toán Fibonacci - F(0) = 1, F(1) = 1 - F(n) = F(n – 1) + F(n – 2) n=0 1 n=1 1 n=2 2 n=3 3 Kỹ thuật lập trình - Nguyễn Minh Huy 10
  11. Thuật toán quy hoạch động Khái niệm quy hoạch động: động: Khi nào dùng quy hoạch động? động? Bài toán đệ quy. quy. Có thể suy biến về trường hợp cơ bản. bản. Các trường hợp suy biến trùng lắp nhau. nhau. Có thể dùng bảng tra để lưu lời giải. giải. Không quá nhiều trường hợp suy biến. biến. Có thể lưu trữ bảng tra. tra. fibo(n) fibo(n) fibo(n-1) fibo(n-2) fibo(n-1) fibo(n-2) fibo(n-2) fibo(n-3) fibo(n-3) fibo(n-4) fibo(n-3) fibo(n-4) … … … … … … Kỹ thuật lập trình - Nguyễn Minh Huy 11
  12. Thuật toán quy hoạch động Phân loại quy hoạch động: động: Quy hoạch từ trên xuống (top-down): (top- Quy hoạch bảng tra cho trường hợp tổng quát trước. trước. Gọi đệ quy đến trường hợp đơn giản hơn. hơn. Gặp trường hợp đã giải thì truy xuất bảng tra. tra. solve_top_down( solve_top_down( trường hợp N, bảng tra lời giải T ) { if ( đã giải trường hợp N ) return T[ N ]; ]; // Giải trường hợp N và đưa vào bảng tra. tra. if ( N cơ bản ) T[ N ] = lời giải cơ bản; bản; else T[ N ] = solve_top_down( N – 1, T ); solve_top_down( } Kỹ thuật lập trình - Nguyễn Minh Huy 12
  13. Thuật toán quy hoạch động Phân loại quy hoạch động: động: Quy hoạch từ dưới lên (bottom-up): (bottom- Quy hoạch bảng tra cho trường hợp cơ bản trước. trước. Dùng vòng lặp tính trường hợp tổng quát dựa vào bảng tra. tra. Cách thức khử đệ quy. quy. solve_bottom_up( solve_bottom_up( trường hợp N ) { Khai báo bảng tra T; Khởi tạo T với các trường hợp cơ bản; bản; for (int i = trường hợp tổng quát đầu tiên; i
  14. Tóm tắt Thuật toán sắp xếp: xếp: Interchange Sort. Selection Sort. Merge Sort. Thuật toán quy hoạch động: động: Quy hoạch bảng tra lời giải. giải. Phân loại: loại: Top- Top-down: tổng quát trước, dùng đệ quy. trước, quy. Bottom- Bottom-up: cơ bản trước, dùng vòng lặp. trước, lặp. Kỹ thuật lập trình - Nguyễn Minh Huy 14
  15. Bài tập Bài tập 10.1: Viết chương trình C cài đặt sắp xếp trộn trên danh sách liên kết đơn. đơn. Kỹ thuật lập trình - Nguyễn Minh Huy 15
  16. Bài tập Bài tập 10.2: Viết chương trình C dùng quy hoạch động (cả 2 cách top-down và top- bottom- bottom-up) để tìm dãy con tăng không liên tục dài nhất trong dãy N phần tử. tử. Ví dụ: dụ: Cho dãy AN = { 1 5 9 2 4 7 8 } Dãy con tăng không liên tục dài nhất SN = { 1 2 4 7 8 } Kỹ thuật lập trình - Nguyễn Minh Huy 16
  17. Bài tập Bài tập 10.3: Viết chương trình C dùng quy hoạch động (cả 2 cách top-down và top- bottom- bottom-up) để giải bài toán sau: sau: - Cho N loại tiền mệnh giá { T0, T1, …, TN } - Tìm cách đổi số tiền M ra các tờ tiền có mệnh giá được cho. cho. - Các tờ tiền được dùng để đổi là ít nhất. nhất. Ví dụ 1: Cho các loại tiền mệnh giá { 5 10 20 40 } Số tiền cần đổi 90 = 40 + 40 + 10. Ví dụ 2: Cho các loại tiền mệnh giá { 10 50 60 90 } Số tiền cần đổi 110 = 50 + 60. Kỹ thuật lập trình - Nguyễn Minh Huy 17
  18. Bài tập Bài tập 10.4: Viết chương trình C dùng quy hoạch động (cả 2 cách top-down và top- bottom- bottom-up) để giải bài toán sau: sau: - Tìm cách biểu diễn số nguyên N bằng tổng các số nguyên tố. tố. - Các số nguyên tố dùng để biểu diễn là ít nhất. nhất. Ví dụ: dụ: 6 = 3 + 3 (ít hơn 2 + 2 + 2) (ít 8=3+5 38 = 31 + 7 Kỹ thuật lập trình - Nguyễn Minh Huy 18
  19. Bài tập Bài tập 10.5: Viết chương trình C dùng quy hoạch động (cả 2 cách top-down và top- bottom- bottom-up) để giải bài toán sau: sau: Một lâu đài cổ có M tầng lầu, mỗi tầng lầu có N phòng. Tại mỗi lầu, phòng. phòng của lâu đài đều có 3 cái thang thông với 3 phòng của tầng lầu phía trên gồm: phòng ngay bên trên, phòng trên bên trái và phòng trên gồm: trên, bên phải. Trong mỗi phòng có một rương tiền với giá trị nhất định. phải. định. Một người săn kho báu xuất phát từ tầng trệt của lâu đài. Anh ta đài. vào một phòng bất kỳ rồi từ đó đi lên các phòng ở tầng trên. Mỗi tầng trên. anh ta chỉ ghé qua một phòng. phòng. Hãy tìm lộ trình phòng ở mỗi tầng mà người săn kho báu ghé qua để thu được số tiền nhiều nhất. nhất. Kỹ thuật lập trình - Nguyễn Minh Huy 19
ADSENSE

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.

 

Đồng bộ tài khoản
3=>0