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

Bài giảng Thuật toán: Chương 2 - GV. Nguyễn Thanh Cẩm

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:65

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

Chương 2 Chia để trị thuộc bài giảng thuật toán, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: thuật toán chia để trị tổng quát, một số thí dụ minh họa.

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 Thuật toán: Chương 2 - GV. Nguyễn Thanh Cẩm

  1. TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm
  2. Nội Dung C1 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP C2 CHIA ĐỂ TRỊ C3 QUY HOẠCH ĐỘNG C4 THUẬT TOÁN THAM LAM C5 THUẬT TOÁN QUAY LUI Nguyễn Thanh Cẩm
  3. CHIA ĐỂ TRỊ 2.1 Thuật toán chia để trị tổng quát 2.2 Một số thí dụ minh họa Nguyễn Thanh Cẩm
  4. 2.1 Thuật toán chia để trị tổng quát  Giả sử rằng, thuật toán phân chia một bài toán cỡ n thành a bài toán nhỏ. Trong đó mỗi bài toán nhỏ có cỡ n/b. Cũng vậy, ta giả sử rằng tổng các phép toán thêm vào khi thực hiện phân chia và tổng hợp lời giải của bài toán là g(n). Khi đó nếu f(n) là số các phép toán cần thiết để giải bài toán đã cho, thì f thỏa mãn hệ thức truy hồi sau đây:  F(n) = a.f(n/b) +g(n). Nguyễn Thanh Cẩm
  5. 2.1 Thuật toán chia để trị tổng quát Dưới đây là nội dung của thuật toán chia để trị: Main D_and_C(n) { Nếu n
  6. CHIA ĐỂ TRỊ 2.1 Thuật toán chia để trị tổng quát 2.2 Một số thí dụ minh họa Nguyễn Thanh Cẩm
  7. 2.2 Một số thí dụ minh họa 2.2.1 Bài toán tìm kiếm nhị phân 2.2.2 Bài toán phép nhân các số nguyên lớn 2.2.3 Bài toán nhân ma trận 2.2.4 Bài toán dãy con lớn nhất 2.2.5 Bài toán sắp xếp 2.2.6 Bài toán lũy thừa Nguyễn Thanh Cẩm
  8. 2.2.1 Bài toán tìm kiếm nhị phân  Bài toán: Cho số x và mảng A[1..n] các số nguyên được sắp xếp theo thứ tự không giảm. Tìm i sao cho A[i] = x. (Giả thiết i tồn tại).  Phân tích bài toán: Số x cho trước: + Hoặc là bằng phần tử nằm ở vị trí giữa mảng A + Hoặc là nằm ở nửa bên trái (x < phần tử ở giữa mảng A ) + Hoặc là nằm ở nửa bên phải (x > phần tử ở giữa mảng A ) Nguyễn Thanh Cẩm
  9. 2.2.1 Bài toán tìm kiếm nhị phân Từ nhận xét đó ta có giải thuật sau: Index location(index low, index hight) { Index mid; If (low > hight) return 0; Else { mid = (low  hight)/2 ; If (x == A[mid]) return mid Else If (x < A[mid]) return location(low, mid - 1) Else Return location (mid + 1, hight); } } Nguyễn Thanh Cẩm
  10. 2.2.1 Bài toán tìm kiếm nhị phân Thí dụ: Giả sử ta cần tìm x = 18 trong dãy A = {10, 12, 13, 14, 18, 20, 25, 27, 30, 35, 40, 45, 47}. ở đây n =13. Ta thực hiện như sau: Đầu tiên ta tính mid = (1 + 13)/2 = 7 => A[7] = 25 Vì x = 18 < 25 nên ta tìm trên dãy nhỏ A1 = {10, 12, 13, 14, 18, 20} Ta tìm số ở giữa mới đó là mid1 = (1 + 6)/2 = 3 => A1[3] = 13 Vì x = 18 > 13 nên ta tìm trên dãy lớn A12 = {14, 18, 20} Ta lại tiếp tục tìm phần tử giữa của dãy con mới mid2 = (4 + 6)/2 = 5 => A12[5] = 18 Thông báo chỉ số i = 5 và dừng thuật toán. Nguyễn Thanh Cẩm
  11. 2.2.1 Bài toán tìm kiếm nhị phân Độ phức tạp của thuật toán: Gọi T(n) là thời gian cần thiết để thực hiện thuật toán. Khi đó: 1 n 1  T ( n)   n T ( 2 )  1  n 1 Theo định lý thợ (xem phụ lục A) ta có T (n)  O(log 2 n) Nguyễn Thanh Cẩm
  12. 2.2 Một số thí dụ minh họa 2.2.1 Bài toán tìm kiếm nhị phân 2.2.2 Bài toán phép nhân các số nguyên lớn 2.2.3 Bài toán nhân ma trận 2.2.4 Bài toán dãy con lớn nhất 2.2.5 Bài toán sắp xếp 2.2.6 Bài toán lũy thừa Nguyễn Thanh Cẩm
  13. 2.2.2 Bài toán phép nhân các số nguyên lớn Thuật toán cổ điển để nhân hai số nguyên có n chữ số là O(n2). Năm 1962 A.A. Karatsuba đã khám phá bằng cách rút gọn phép nhân hai số nguyên n chữ số, xuống thành bốn phép nhân hai số nguyên n/2 chữ số như sau: Nguyễn Thanh Cẩm
  14. 2.2.2 Bài toán phép nhân các số nguyên lớn  Input: x  x n 1 x n  2 ...x1 x0 và y  y n 1 y n  2 ... y1 y 0  Output: z  x * y  z 2 n 1 z 2 n  2 ...z1 z 0  Ta biết rằng: n 1 x   xi * 10 i  x n 1 * 10 n 1  x n  2 * 10 n  2  ...  x1 * 101  x 0 *10 0 i 0 n 1 y   y i * 10 i  y n 1 * 10 n 1  y n  2 * 10 n  2  ...  y1 *101  y 0 * 10 0 i 0 2 n 1 n 1 n 1  z  x* y   z i * 10 i  ( xi * 10 i ) * ( y i * 10 i ) i 0 i 0 i0 Nguyễn Thanh Cẩm
  15. 2.2.2 Bài toán phép nhân các số nguyên lớn  Ví dụ: 207 = 2*102 + 0*101 + 7*100 702 = 7*102 + 0*101 + 2*100 207*702 = 145314 = 1*105 + 4*104 + 5*103 + 3*102 + 1*101 + 4*100  Bây giờ giả sử ta đặt: a  x n 1 x n  2 ...x n / 2 b  x ( n / 2 )1 x ( n / 2)  2 ...x 0 c  y n 1 y n  2 ... y n / 2 d  y ( n / 2 ) 1 y ( n / 2 ) 2 ...y 0 Khi đó: x  a * 10 n/2 b y  c * 10 n / 2  d  z  x * y  (a *10 n / 2  b)(c *10 n / 2  d )  (a * c) * 10 n  (a * d  b * c) *10 n / 2  (b * d ) Nguyễn Thanh Cẩm
  16. 2.2.2 Bài toán phép nhân các số nguyên lớn Ví dụ: với n = 4; x = 1026 và y = 3547 thì a = 10, b = 26, c = 35, d = 47 Khi đó x = 1026 = 10*102 + 26 = a*102 + b; y = 3547 = 35*102 + 47 = c*102 + d và z = x*y = (10*35)*104 + (10*47+26*35)*102 + (26*47) = 350*104 + 1380*102 + 1222 = 3.639.222 Nguyễn Thanh Cẩm
  17. 2.2.2 Bài toán phép nhân các số nguyên lớn  Khi đó ta có thời gian thực hiện thuật toán là: 1 n 1  T ( n)   n  4T ( )  cn n 1  2  Theo định lý thợ ta có độ phức tạp của thuật toán là . T ( n)  O (n 2 ) Nguyễn Thanh Cẩm
  18. 2.2.2 Bài toán phép nhân các số nguyên lớn  Nhân 981 với 1234. Tách từng toán hạng thành hai nửa: 0981 cho ra a = 09 và b = 81, 1234 thành c = 12 và d = 34. Lưu ý rằng 981 = 102a + b và 1234 = 102c + d. Do đó, tích cần tìm có thể tính được là 981 x 1234 = (102a + b)(102c + d) = 104ac + 102(ad + bc) + bd = 1080000 + 127800 + 2754 = 1210554 Thủ tục trên đến bốn phép nhân hai nửa: ac, ad, bc và bd. Nguyễn Thanh Cẩm
  19. 2.2.2 Bài toán phép nhân các số nguyên lớn  Hãy xét tích:  r = (a + b)(c + d) = ac + (ad + bc) + bd  p = ac = 09 * 12 = 108  q = bd = 81 * 34 = 2754  r = (a + b)(c+d) = 90 * 46 = 4140  và cuối cùng  981 x 1234 = 104p + 102(r – p – q) + q  = 1080000 + 127800 + 2754 = 1210554.  Như vậy tích của 981 và 1234 có thể rút gọn về ba phép nhân của hai số có hai chữ số (09*12, 81*34 và 90*46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10), phép cộng và phép trừ. Nguyễn Thanh Cẩm
  20. 2.2.2 Bài toán phép nhân các số nguyên lớn  Sau đây là mô hình cải tiến thuật toán nhân số nguyên lớn  Cải tiến để còn lại 3 phép nhân :  Từ đó ta đưa ra thuật toán nhân số nguyên lớn là: Nguyễn Thanh Cẩm
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
2=>2