Chào mừng bạn đến với Selfomy Hỏi Đáp, hãy Hỏi bài tập hoặc Tham gia ngay
0 phiếu
824 lượt xem
trong Toán lớp 11 bởi trannhat900 ● Ban Quản Trị Phó giáo sư (52.9k điểm)
Có bao nhiêu xâu nhị phân có độ dài n trong đó không có hai bit 1 đứng cạnh nhau?

1 Câu trả lời

0 phiếu
bởi trannhat900 ● Ban Quản Trị Phó giáo sư (52.9k điểm)
được bầu chọn là câu hỏi hay nhất bởi trannhat900 ● Ban Quản Trị
 
Hay nhất

 Gọi \(c_n\) là số xâu nhị phân có độ dài \(n\) thỏa mãn điều kiện đề bài.

Ta có: \(c_1=2; \ c_2=3.\)

Xét xâu nhị phân có độ dài \(n\) thỏa mãn điều kiện đề bài có dạng \(a_{n}a_{n-1}a_{n-2}...a_{2}a_{1}.\)

Có hai trường hợp:

TH1: \(a_n=1. \) Khi đó \(a_{n-1}=0\) và \(a_{n-2}...a_2a_1\) có thể chọn là một xâu bất kỳ độ dài \(n-2\) thỏa điều kiện. Có \(c_{n-2}\) xâu như vậy, suy ra trường hợp này có \(c_{n-2}\) xâu.

TH2: \(a_n=0\). Khi đó \(a_{n-1}...a_2a_1\) có thể chọn là một xâu bất kỳ độ dài \(n-1\) thỏa điều kiện. Có \(c_{n-1}\) xâu như vậy, suy ra trường hợp này có \(c_{n-1}\) xâu.

Vậy tổng cộng xây dựng được \(c_{n-1}+c_{n-2}\) xâu hay \(c_n=c_{n-1}+c_{n-2}.\)

\(\Rightarrow c_n=\dfrac{\sqrt5-2}{\sqrt5} \begin{pmatrix} \dfrac{1-\sqrt5}{2} \end{pmatrix}^{n-1}+\dfrac{2-\sqrt5}{\sqrt5} \begin{pmatrix} \dfrac{1+\sqrt5}{2}\end{pmatrix}^{n-1}\)

Các câu hỏi liên quan

0 phiếu
3 câu trả lời 172 lượt xem
biết độ dài mỗi cạnh của tam giác tỉ lệ vs 3,4,5,.Ti8nh độ dài mỗi cạnh của cạnh của tam giác biết cạnh dài hơn cạnh còn lại 6m
đã hỏi 5 tháng 11, 2017 trong Toán lớp 7 bởi my phan
0 phiếu
3 câu trả lời 236 lượt xem
Câu 4: Cho tam giác ABC vuông tại A có AB=18cm, BC=30cm. Vẽ Ah vuông góc với BC tại H. Tính độ dài AH.Câu nào sau đây đúng: A.AH=14,4cm B.AH=15,4cm C.AH=16cm D.A,B,C đều sai
đã hỏi 14 tháng 5, 2021 trong Toán lớp 7 bởi tngnhatganh117 Cử nhân (3.3k điểm)
0 phiếu
2 câu trả lời 141 lượt xem
Câu 2: Cho ba tam giác có độ dài như sau: ΔABC: 7,2cm; 9,6cm; 13cm ΔHIK: 9cm; 12cm; 16cm ΔEFD: 12cm; 16cm; 20cm Trong ba tam giác đã cho, tam giác nào là tam giác vuông: A.ΔABC B.ΔHIK C.ΔEFD D.Không có tam giác nào vuông
đã hỏi 14 tháng 5, 2021 trong Toán lớp 7 bởi tngnhatganh117 Cử nhân (3.3k điểm)
+2 phiếu
1 trả lời 156 lượt xem
Kim giờ của một đồng hồ dài bằng 3434 kim phút . Tìm tỉ số giữa tốc độ góc của hai kim và tỉ số giữa tốc độ dài của đầu mút hai kim  
đã hỏi 4 tháng 8, 2019 trong Vật lý lớp 10 bởi Teemo- Tiến sĩ (19.6k điểm)
+1 thích
1 trả lời 869 lượt xem
Có bao nhiêu số tự nhiên có 7 chữ số khác nhau từng đôi một, trong đó chữ số 2 đứng liền giữa hai chữ số 1 và 3?
đã hỏi 6 tháng 1, 2021 trong Toán lớp 11 bởi trannhat900 ● Ban Quản Trị Phó giáo sư (52.9k điểm)
0 phiếu
1 trả lời 1.5k lượt xem
Cho hai lực đồng quy có độ lớn F1=16, F2=12N a) Hợp lực của chúng có thể có độ lớn 30 N hoặc 3,5 N được không ? b) Cho biết độ lớn của hợp lực F = 20 N . Hãy tím góc giữa lực  và 
đã hỏi 30 tháng 6, 2018 trong Vật lý lớp 10 bởi anhthh_823 ● Cộng Tác Viên Tiến sĩ (15.4k điểm)
0 phiếu
1 trả lời 398 lượt xem
Câu 1: Cho tam giác MNP vuông tại M, MN=4,5cm, NP =7,5cm. TInh độ dài MP A.5,5cm B.7,5cm C.4,5cm D.6cm
đã hỏi 14 tháng 5, 2021 trong Toán lớp 7 bởi tngnhatganh117 Cử nhân (3.3k điểm)
+1 thích
4 câu trả lời 300 lượt xem
+1 thích
1 trả lời 138 lượt xem
đã hỏi 9 tháng 7, 2018 trong Khác bởi supersmart2005 Cử nhân (2.6k điểm)

HOT 1 giờ qua

  1. nguyenmanh04102009212

    166 Điểm

  2. tnk11022006452

    160 Điểm

  3. hoconghung031007464

    80 Điểm

Phần thưởng hằng tháng
Hạng 1: 200.000 đồng
Hạng 2: 100.000 đồng
Hạng 3: 50.000 đồng
Hạng 4-10: 20.000 đồng
Bảng xếp hạng cập nhật 30 phút một lần
...