tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán: Hàm sinh và ứng dụng - Phạm Thế Bảo

Nội dung chính của bài giảng "Phân tích và thiết kế thuật toán: Hàm sinh và ứng dụng" gồm có: Chuỗi lũy thừa, dùng hàm sinh giải hệ thức truy hồi, hàm sinh của dãy xác suất. . | 27 03 2008 HÀM SINH VÀ ỨNG DỤNG Phạm Thế Bảo Khoa Toán - Tin học Trường Đại học Khoa học Tự nhiên Giới thiệu Bài toán có 12 trái táo chia cho 03 bạn A B C. Theo qui định A lấy ít nhất 04 trái B và C lấy ít nhất 02 trái C không lấy quá 05 trái. Vậy có bao nhiêu cách chia Giải gọi a b c là số táo của các bạn A B C được chia. Ta có a b c 12 a 4 b 2 .5 c 2 Số cách chia táo chính là số nghiệm của phương trình Phạm Thế Bảo 1 27 03 2008 Hay gọi G a b c 12 a 4 b 2 5 c 2 . Thì G số lời giải. Ta đặt H xa b c a b ceN xa b c x12 a 4 b 2 5 c 2 thì G H - cần tìm H - chính là hệ số của x12 trong phương trình f x x4 x5 . x2 x3 . x2 . x5 2 xa b c 2 akxk 4 a ra k 8 2 b x 2 c 5 Khi k 12 thì ak chính là giá trị cần tìm - mục tiêu của bài toán là tìm khai triển của f x . Phạm Thế Bảo Chuỗi lũy thừa Xét chuỗi lũy thừa Ễanz vđi àn G C nếu n 0 n Sn z akzk hội tụ ve G z thì chuỗi hội tụ và k 0 X G z E àZ 2 0 Cho dãy số an zn0. Hàm sinh của dãy này là chuỗi 52 an z n . n 0 Phạm Thế Bảo 2 27 03 2008 Quay lại bài toán chia táo. Thay vì 4 a và 2 b w ta cũng có thể viết 4 a 8 và 2 b 6. Thì f z z VjL . 7k b 2 b z 7 zc _ _4 2 _3 _4 2 2 _3 _4 2 2 _3 z 1 z z z z z 1 z z z z z 1 z z z _ 8 2342 23 z 1 z z z z 1 z z z z8 í 5- 2 í k 1 - z 7 k 1 - z 7 _ _8 5 2 4 1 z 1 - z 1 - z K X 3 1 - z can xác định hệ số của z4 trong 1 z5 2 1 z4 1 1 - z 3 Phạm Thế Bảo Theo chuôi lũy thừa ta có 1 1 - z 3 Nên ta có hệ số của z4 trong chuôi này là í 6V 6 4 5 6 4 . -1 . -1 -------1 14 4 4 2 2 í í 3 ì í 4 2 z . í k 2 ì 4 k 1 z . 1 z k k1 k 2 k k 7 7 Vậy có 14 cách giải bài toán chia táo. Phạm Thế Bảo