tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán (Phần 2) - ĐH Phương Đông

Cùng nắm kiến thức trong bài giảng "Phân tích và thiết kế thuật toán (Phần 2)" thông qua việc tìm hiểu các nội dung sau: quy hoạch động, thuật toán đồ thị cơ bản. Mời các bạn xem qua và nắm được kiến thức đã trình bày trong bài giảng này thật hiệu quả. | Quy hoạch động Công thức truy hồi Ví dụ Cho số tự nhiên n 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các số nguyên dương các cách phân tích là hoán vị của nhau chỉ tính là một cách. n 5 có 7 cách phân tích L 5 1 14-1 14-1 2. 5 l l l 2 3 5 1 1 3 4. 5 1 2 2 55 1 4 6 5 2 3 7 5 5 Lưu ý n 0 vẫn coi là có 1 cách phân tích thành tổng các số nguyên dương 0 là tổng của dãy rỗng Để giải bài toán này trong chuyên mục trước ta đã dùng phương pháp liệt kê tất cả các cách phân tích và đếm số cấu hình. Bây giờ ta thử nghĩ xem cócáchnàotínhngayrasốlượngcáccách phântíchmàkhôngcầnphảiliệtkêhaykhông . Bởi vì khi số cách phân tích tương đối lớn phương pháp liệt kê tỏ ra khá chậm. n 100 có 190569292 cách phân tích . Nhận xét Nếu gọi F m v là số cách phân tích số v thành tổng các số nguyên dương m. Khi đó Các cách phân tích số v thành tổng các số nguyên dương m có thể chia làm hai loại Loại 1 Không chứa số m trong phép phân tích khi đó số cách phân tích loại này chính là số cách phân tích số v thành tổng các số nguyên dương m tức là 68 129 số cách phân tích số v thành tổng các số nguyên dương m - 1 và bằng F m -1 v . Loại 2 Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v -m thành tổng các số nguyên dương m Lưu ý điều này chỉ đúng khi không tính lặp lại các hoán vị của một cách . Có nghĩa là về mặt số lượng số các cách phân tích loại này bằng F m v - m Trong trường hợp m v thì rõ ràng chỉ có các cách phân tích loại 1 còn trong trường hợp m v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế F m v F m - 1 v nếu m v F m v F m - 1 v F m v - m nếu m v Ta có công thức xây dựng F m v từ F m - 1 v và F m v - m . Công thức này có tên gọi là công thứctruyhồiđưa việc tính F m v về việc tính các F m v với dữ liệu nhỏ hơn. Tất nhiên cuối cùng ta sẽ quan tâm đến F n n Số các cách phân tích n thành tổng các số nguyên dương n. Nhìn vào bảng F ta thấy rằng F m v được tính

• Kỹ thuật lập trình
• Ngôn ngữ lập trình
• Tự học lập trình
• Thiết kế thuật toán
• Phân tích thuật toán
• Lập trình máy tính
• Phân tích và thiết kế thuật toán
• Ngôn ngữ lập trình C
• giáo trình Ngôn ngữ lập trình C
• bài giảng Ngôn ngữ lập trình C
• tài liệu Ngôn ngữ lập trình C
• lý thuyết Ngôn ngữ lập trình C
• hướng dẫn lập trình C
• Bài giảng Ngôn ngữ lập trình C++
• Ngôn ngữ lập trình C++
• Lập trình C
• Lập trình C++
• Lập trình mạng
• Học lập trình C
• Lập trình Mobile
• Lý thuyết ngôn ngữ lập trình
• Bài giảng lý thuyết ngôn ngữ lập trình
• Đề thi Ngôn ngữ lập trình C++
• Ngân hàng đề thi Ngôn ngữ lập trình C++
• Trắc nghiệm Ngôn ngữ lập trình C++
• Ôn thi Ngôn ngữ lập trình C++
• kinh nghiệm lập trình
• giáo trình Ngôn ngữ lập trình C#
• bài giảng Ngôn ngữ lập trình C#
• tài liệu Ngôn ngữ lập trình C#
• lý thuyết Ngôn ngữ lập trình C#
• hướng dẫn lập trình C#
• ngôn ngữ C++
• kỹ thuật phần mềm
• chương trình lập trình
• lập trình căn bản
• tài liệu lập trình
• ngôn ngữ lập trình bậc cao
• giáo trình Ngôn ngữ lập trình
• bài giảng Ngôn ngữ lập trình
• tài liệu Ngôn ngữ lập trình
• hướng dẫn lập trình
• Công cụ lập trình C
• Tìm hiểu ngôn ngữ lập trình C
• Giới thiệu ngôn ngữ C
• Ngôn ngữ C
• Các ngôn ngữ lập trình bậc cao
• Lịch sử ngôn ngữ C
• Lớp và đối tượng
• Đề thi Ngôn ngữ lập trình C
• Ngân hàng đề thi Ngôn ngữ lập trình C
• Trắc nghiệm Ngôn ngữ lập trình C
• Ôn thi Ngôn ngữ lập trình C
• Câu hỏi Ngôn ngữ lập trình C
• Nguyên lý ngôn ngữ lập trình
• Bài giảng Nguyên lý ngôn ngữ lập trình
• Ngôn ngữ lập trình hàm
• Hàm toán học
• Lập trình hàm
• Bản chất của lập trình hàm
• Ngôn ngữ LISP