Dãy bit tiếp sau của dãy 10010011 trong thuật toán liệt kê tất cả các xâu nhị phân có độ dài 8 bằng phương pháp sinh.
Trả lời:
Đáp án đúng: D
Thuật toán sinh xâu nhị phân độ dài n hoạt động bằng cách bắt đầu từ xâu "00...0" (n số 0) và lặp lại các bước sau cho đến khi đạt đến xâu "11...1" (n số 1):
1. **Tìm vị trí bit 0 cuối cùng**: Duyệt xâu từ phải sang trái, tìm vị trí `i` đầu tiên mà bit tại vị trí đó là 0.
2. **Đổi bit 0 thành 1**: Đặt bit tại vị trí `i` thành 1.
3. **Đặt các bit sau vị trí i thành 0**: Tất cả các bit từ vị trí `i+1` đến cuối xâu đều được đặt thành 0.
Áp dụng vào bài toán:
Dãy bit hiện tại là 10010011.
1. Tìm vị trí bit 0 cuối cùng: Duyệt từ phải sang trái, ta thấy vị trí bit 0 cuối cùng là vị trí thứ 2 từ phải sang (tức là vị trí thứ 7 từ trái sang).
2. Đổi bit 0 thành 1: Dãy bit trở thành 10010111.
3. Đặt các bit sau vị trí i thành 0: Không có bit nào sau vị trí i.
Vậy, dãy bit tiếp theo là 10010100 (A).
