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

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ả
Nội dung trích xuất từ tài liệu:
Thiết kế thuật toán 1 Thi t k thu t toán Lê S VinhB 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 nh2. Gi i các bài toán có kích thư c nh3. 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 FibonacciDã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 Fibonacciint fib[N];for (int i = 0; i C u trúc chung c a phương pháp quy ho ch ñ ng1. ðưa ra cách tính nghi m c a các bài toán con ñơn gi n2. 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 con3. Thi t k b ng ñ lưu nghi m c a các bài toán4. Tính nghi m c a các bài toán t nh ñ n l n5. 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 balô 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, Mnguyên dương nh hơn 1001.Ví dN = 4, M = 10i 1 2 3 4wi 5 4 6 3ti 1 4 3 5 Ví d : Dãy con chungCho hai dãy s A = (a1,…,an) và B = (b0,..,bm), tìm dãy s C = (c0,..,ck) saocho 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 tCho 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 oCó 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 saocho chênh l nh gi a t ng s k o c a hai ñ ng là ít nh t. Lưu ý là không ñư cchia nh các gói k o ra.Ví d :N =513495Chia thành: 1 9 và 3 4 5