Tìm công thức truy hồi cho bài toán

#1

Mọi người cho e hỏi công thức truy hồi của bài toán sau ạ: Với 2 số nguyên dương N và K (1<K<N) đếm xem có bao nhiêu xâu nhị phân độ dài N không chưa k bit 1 liên tiếp

#2

Với K = 3 thì 1110, 11110, 111110, … đều không được :smiley: vậy bạn có nhận xét gì?

2 Likes
#3

vẫn dc chứ ông, Theo tôi sẽ là công thức (n-k)*2^(n-k) xâu

#4

như thế vẫn có trường hợp dư bạn à, ví dụ nhé chuỗi A1111B đi
Thì nó đã được tính 2 lần, 1 lần là tính cho 3 số 1 đầu, 1 lần tính cho 3 số 1 cuối, tức là A111-1B và A1-111B.

#5

bit thì ông ghi 1 & 0 thôi chứ nhĩ

1 Like
#6

cái này tôi nhớ môn kiến trúc máy tính hồi học đại học nè, có trừ trường hợp trùng nữa nhĩ

#7

trường hợp trùng vẫn phải trừ bạn ơi

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?