TAILIEUCHUNG - ASP.NET 2.0 - PART 6

Đây là giáo trình kỹ thuật lập trình bằng tiếng Anh dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin tham khảo. | Chapter 11 Dynamic Programming 124 We can fully parenthesized them in two ways 1. A1 A2 A3 100 x 5 x 50 10 100 50 75000 2. A1 A2 A3 10 x 100 x 5 10 x 5 x 50 7500 10 times better See how the cost of multiplying these 3 matrices differ significantly. The cost truly depend on the choice of the fully parenthesization of the matrices. However exhaustively checking all possible parenthesizations take exponential time. Now let s see how MCM problem can be solved using DP. Step 1 characterize the optimal sub-structure of this problem. Let i j denote the result of multiplying AiAi . can be obtained by splitting it into and Ak and then multiplying the subproducts. There are j-i possible splits . k i . j-1 Within the optimal parenthesization of a the parenthesization of must be optimal b the parenthesization of Ak must be optimal Because if they are not optimal then there exist other split which is better and we should choose that split and not this split. Step 2 Recursive formulation Need to find A1 n Let m i j minimum number of scalar multiplications needed to compute Since can be obtained by breaking it into Ak we have m i j 0 if i j min i k j m i k m k 1 j pi-1pkpj if i j let s i j be the value k where the optimal split occurs. Step 3 Computing the Optimal Costs Matric-Chain-Order p n length p -1 Chapter 11 Dynamic Programming 125 for i 1 to n do m i i 0 for l 2 to n do for i 1 to n-l 1 do j i l-1 m i j infinity for k i to j-1 do q m i k m k 1 j pi-1 pk pj if q m i j then m i j q s i j k return m and s Step 4 Constructing an Optimal Solution Print-MCM s i j if i j then print Ai else print Print-MCM s 1 s i j Print-MCM s s i j 1 j Note As any other dp solution MCM also can be solved using Top Down recursive algorithm using memoization. Sometimes if you cannot visualize the Bottom Up approach just modify your original Top Down recursive solution by including memoization. You ll save a lot of time by avoiding .

• Kỹ thuật lập trình
• lập trình căn bản
• lập trình C++
• thủ thuật lập trình
• tài liệu lập trình
• giáo trình lập trình
• Bài giảng Lập trình căn bản
• Lập trình căn bản Chương 1
• Khái niệm lập trình
• Chương trình máy tính
• Ngôn ngữ lập trình
• chương trình lập trình
• ngôn ngữ Visual Basic
• điều khiển thông dụng
• kiểu dữ liệu căn bản
• thiết kế biểu mẫu dùng điều khiển
• Giáo trình Lập trình căn bản
• Cấu trúc điều khiển
• Lập trình căn bản Pascal
• Kỹ thuật lập trình C
• Kỹ thuật lập trình
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao
• Mã giải và lưu đồ
• Môi trường lập trình
• Lập trình căn bản Chương 2
• Cấu trúc chương trình
• Khai báo dữ liệu
• Chương trình PASCAL
• Các kiểu cấu trúc dữ liệu
• Các thao tác trên tệp
• Ứng dụng lập trình căn bản
• Giáo trình Lập trình C căn bản
• Lập trình C
• Ngôn ngữ lập trình C
• Phương pháp lập trình
• Các thành phần trong ngôn ngữ C
• ngôn ngữ C
• hướng dẫn lập trình
• Làm quen lập trình C
• Thành phần trong ngôn ngữ C
• Ngôn ngữ lập trình C++
• Kiểu dữ liệu
• Lập trình căn bản Chương 5
• Chương trình con
• Biến cục bộ
• Biến Đệ quy
• Hướng dẫn lập trình căn bản PLS Master K
• Lập trình căn bản PLS Master K
• Giới thiệu PLC Master K
• Chương trình PLC
• Kiểu dữ liệu cơ bản
• Môi trường Turbo C
• Lập trình Turbo C
• Bài giảng kỹ thuật lập trình căn bản
• Lập trình căn bản Chương 3
• Phát biểu điều khiển
• Phát biểu gán
• Phát biểu ghép BEGIN END
• Lập trình căn bản Chương 4
• Dữ liệu do người dùng định nghĩa
• Dữ liệu rời rạc
• Giải thuật trên array
• Quản trị mạng máy tính
• Làm quen ngôn ngữ lập trình
• Dữ liệu kiểu chuỗi
• mẹo lập trình
• kỹ thuật máy tính
• kinh nghiệm lập trình
• kỹ thuật phần mềm
• code lập trình
• lập trình java
• lập trình html
• thẻ html
• cấu trúc của một file HTML
• Lập Trình Nhúng Căn Bản
• phần mềm máy tính
• Cấu trúc dữ liệu
• Chương trình dịch
• Thành phần ngôn ngữ C
• Chương trình C
• Hàm toán học
• Truyền tham số cho hàm