Thiết kế thuật toán 1

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

132
lượt xem 46
download

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

Tham khảo tài liệu 'thiết kế thuật toán 1', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Thiết kế thuật toán 1

Thi t k thu t toán Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com
Chia ð Tr (Divide and Conquer) 1. Chia bài toán l n thành các bài toán có kích thư c nh 2. Gi i các bài toán có kích thư c nh 3. K t h p nghi m c a các bài toán có kích thư c nh ñ gi i bài toán l n
Ví d : Dãy s Fibonacci Dãy Fibonacci: 0 1 2 3 5 8 13… f(0) = 0 f(1) = 1 f(k) = f(k-1) + f(k-2) Fibonacci_DAC (k) { if (k == 0) return 0 else if (k == 1) return 1 else return Fibonacci _DAC (k-1) + fibonacci_DAC (k-2) } Nh n xét: Các bài toán nh ñư c gi i quy t d a vào nh ng bài toán nh hơn gi ng nhau.
Quy ho ch ñ ng (Dynamic programming) • Gi ng phương pháp ‘chia-ñ -tr ’ (divide-and-conquer) là gi i quy t bài toán l n d a vào k t qu các bài toán con. • ði m khác bi t là quy ho ch ñ ng lưu l i nghi m c a t t c các bài toán con, m i bài toán con ch ph i tính toán 1 l n. • Quy hoach ñ ng thư ng ñư c dùng ñ gi i quy t nh ng bài toán liên quan ñ n t i ưu hóa (tìm nghi m t t nh t).
Ví d : Dãy s Fibonacci int fib[N]; for (int i = 0; i
C u trúc chung c a phương pháp quy ho ch ñ ng 1. ðưa ra cách tính nghi m c a các bài toán con ñơn gi n 2. Tìm công th c xây d ng nghi m c a bài toán thông qua nghi m c a các bài toán con 3. Thi t k b ng ñ lưu nghi m c a các bài toán 4. Tính nghi m c a các bài toán t nh ñ n l n 5. Xây d ng nghi m c a bài toán c n tìm t b ng
Ví d : Bài toán cái ba lô Có N ñ v t, ñ v t i có kh i lư ng wi và giá tr ti . M t tên tr m có 1 chi c ba lô có th mang ñư c không qúa M kg. Hãy tìm cách mang m t s ñ v t ñ t ng giá tr l y ñư c là l n nh t. Bi t r ng, wi nguyên dương nh hơn 101, M nguyên dương nh hơn 1001. Ví d N = 4, M = 10 i 1 2 3 4 wi 5 4 6 3 ti 1 4 3 5
Ví d : Dãy con chung Cho hai dãy s A = (a1,…,an) và B = (b0,..,bm), tìm dãy s C = (c0,..,ck) sao cho C là dãy con c a c A và B, và C dài nh t có th . Ví d : A = (3, 5, 1, 3, 5, 5, 3) B = (1, 5, 3, 5, 3, 1) C = (5, 3, 5, 3) ho c (1, 3, 5, 3) ho c (1, 5, 5, 3)
Ví d : Dãy con li n nhau t ng l n nh t Cho dãy s A = (a1,…,an), tìm dãy con li n nhau (ai, ai+1,…,aj-1, aj) v i t ng l n nh t. Ví d : A = (-3, 5, -4, 3, 2, -4, 1) Dãy con li n nhau t ng l n nh t: (5, -4, 3, 2)
Ví d : Chia k o Có N gói k o, gói k o i có ai cái. Hãy chia N gói k o trên thành 2 ñ ng sao cho chênh l nh gi a t ng s k o c a hai ñ ng là ít nh t. Lưu ý là không ñư c chia nh các gói k o ra. Ví d : N =5 13495 Chia thành: 1 9 và 3 4 5