Tel: 024.7300.7989 - Phone: 1800.6947 (Thời gian hỗ trợ từ 7h đến 22h)

Giỏ hàng của tôi
Trang chủ
Luyện thi đại học môn toán

Xâu nhị phân là xâu chỉ chứa ký tự 0 hoặc 1. Gọi $a_{n}$ là số lượng xâu nhị phân có n ký

Câu hỏi số 955116:
Vận dụng

Xâu nhị phân là xâu chỉ chứa ký tự 0 hoặc 1. Gọi $a_{n}$ là số lượng xâu nhị phân có n ký tự và không chứa xâu con 00.

Đúng Sai
a) Ta có $a_{3} = 4$.
b) Xâu nhị phân có 11 ký tự không chứa xâu con 00 và có tận cùng bên phải bằng $1 = a_{10}$.
c) Tồn tại giá trị $n$ sao cho $a_{n + 2} < a_{n + 1} + a_{n}$.

Đáp án đúng là: S; Đ; S

Quảng cáo

Xem lời giải
Câu hỏi:955116
Phương pháp giải

Thiết lập hệ thức truy hồi cho dãy số $(a_{n})$ bằng cách chia các xâu thỏa mãn thành hai loại dựa vào ký tự cuối cùng.

Dựa vào hệ thức truy hồi để tính các giá trị cụ thể và kiểm tra tính đúng sai của từng mệnh đề.

Giải chi tiết

Xét các xâu nhị phân độ dài n không chứa xâu con 00.

Với $n = 1$, các xâu thỏa mãn là 0, 1. Suy ra $a_{1} = 2$.

Với $n = 2$, các xâu thỏa mãn là 01, 10, 11. Suy ra $a_{2} = 3$.

Với $n \geq 3$, một xâu nhị phân độ dài $n$ không chứa xâu con 00 có thể có ký tự tận cùng là 1 hoặc 0.

Nếu xâu có ký tự tận cùng là 1, thì $n - 1$ ký tự trước đó tạo thành một xâu độ dài $n - 1$ không chứa xâu con 00. Số lượng xâu như vậy là $a_{n - 1}$.

Nếu xâu có ký tự tận cùng là 0, thì để không xuất hiện xâu con 00, ký tự liền trước nó bắt buộc phải là 1. Tức là xâu kết thúc bằng 10. Khi đó, $n - 2$ ký tự trước đó tạo thành một xâu độ dài $n - 2$ không chứa xâu con 00. Số lượng xâu như vậy là $a_{n - 2}$.

Do đó, ta có hệ thức truy hồi: $a_{n} = a_{n - 1} + a_{n - 2}$ với mọi $n \geq 3$.

Xét mệnh đề a): Ta có $a_{3} = a_{2} + a_{1} = 3 + 2 = 5$.

Vậy mệnh đề a) Sai.

Xét mệnh đề b): Số lượng xâu nhị phân có 11 ký tự không chứa xâu con 00 và có tận cùng bên phải bằng 1 chính là trường hợp thứ nhất khi $n = 11$.

Theo chứng minh trên, số lượng xâu này bằng số lượng xâu hợp lệ có độ dài $11 - 1 = 10$, tức là bằng $a_{10}$.

Vậy mệnh đề b) Đúng.

Xét mệnh đề c): Từ hệ thức truy hồi $a_{n} = a_{n - 1} + a_{n - 2}$ với mọi $n \geq 3$, ta suy ra $a_{n + 2} = a_{n + 1} + a_{n}$ với mọi $n \geq 1$.

Do đó không tồn tại giá trị $n$ nào để $a_{n + 2} < a_{n + 1} + a_{n}$.

Vậy mệnh đề c) Sai.

Đáp án cần chọn là: S; Đ; S

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>>  2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.

Hỗ trợ - Hướng dẫn

  • 024.7300.7989
  • 1800.6947 free

(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com

Đăng ký nhận tư vấn