Cùng làm bài xâu Fibonacci

[TuanNguyen (Tuấn Nguyễn)]

Cùng làm bài XÂU FIBONACCI nhé cả nhà

XÂU FIBONACCI

Xét dãy các xâu F₁, F₂, F₃, …, F_N, … trong đó:

F₁ = ‘A’
F₂ = ‘B’
F_K+1 = F_K + F_K-1 (K > 2).

Ví dụ:

F₁ = ‘A’
F₂ = ‘B’
F₃ = ‘BA’
F₄ = ‘BAB’
F₅ = ‘BABBA’
F₆ = ‘BABBABAB’
F₇ = ‘BABBABABBABBA’
F₈ = ‘BABBABABBABBABABBABAB’
F₉ = ‘BABBABABBABBABABBABABBABBABABBABBA’

Cho xâu S độ dài không quá 25, chỉ bao gồm các ký tự ‘A’ và ‘B’. Hãy xác định số lần xuất hiện xâu S trong xâu F_N, N < 35. Chú ý: hai lần xuất hiện của S trong F_N không nhất thiết phải là các xâu rời nhau hoàn toàn.

Dữ liệu: vào từ file văn bản FIBISTR.INP, bao gồm nhiều dòng, mỗi dòng có dạng N S. Giữa N và S có đúng 1 dấu cách. Dữ liệu vào là chuẩn, không cần kiểm tra.

Kết quả: Đưa ra file văn bản FIBISTR.OUT, mỗi dòng dữ liệu ứng với một dòng kết quả ra

Ví dụ:

FIBISTR.INP	FIBISTR.OUT
3 A 3 AB 8 BABBAB 9 ABABB	1 0 4 4

[nguyen2812 (Bùi Đình Nguyên)]

Bộ 3 A thì output phải là 2 chứ sao lại 1 nhỉ?
Mới nghĩ được loại các xâu đầu vào có 2 A hoặc 3 B liên tiếp trở lên

[rogp10]

@TuanNguyen

F₃ = ‘BA’

mà có 1 chữ A thôi.

[nguyen2812 (Bùi Đình Nguyên)]

Ơ còn F1 không được tính ạ?

[Vo_Tan_Khoa (Võ Tấn Khoa)]

xuất hiện của S trong FN chứ không phải là từ xâu F1->FN nhé bạn