Seminar " giải bài toán đếm bằng cách sử dụng công thức truy hồi"

[ngoctuansp]

Chào các bạn.
Seminar tuần tới diễn ra vào ngày 10/10/2010 đúng vào ngày đại lễ 1000 năm Thăng Long Hà Nội, mình xin giới thiệu với các bạn phương pháp giải quyết bài toán đếm bằng công thức truy hồi. Một trong những ví dụ nổi tiếng sử dụng phương pháp này là bài toán "Tháp Hà Nội". Ý tưởng giải bài toán đếm bằng phương pháp truy hồi đưa bài toán đếm từ n đối tượng về bài toán đếm với ít đối tượng hơn và do đó độ phức tạp của bài toán cũng giảm đi. Theo cá nhân mình đầy là chủ đề khá thú vị, các bạn có ví dụ gì hay thì đóng góp cho chủ đề này nhé. Để khởi động minh đưa ra hai bài toán sau:

Bài 1. Có bao nhiều xâu nhị phân độ dài 8 trong đó ba bit 1 không được đứng cạch nhau?

Bài 2. Cho hình bát giác đều ABCDEFGH. Một con ếch xuất phát từ A. Tại bất kỳ một đỉnh nào trừ đỉnh E, con ếch có thể nhảy tới một trong hai đỉnh kề nó. Nếu con ếch nhảy tới E thì dừng lại. Hỏi con ếch có bao nhiều đường đi gồm n bước từ A đến E?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]