Kỳ thi chọn học sinh giỏi cấp tỉnh Lớp 12 THPT môn Tin học (Vòng 1) - Sở GD&ĐT Đồng Tháp (Có hướng dẫn chấm)

(Bản scan)

Bài 3: (6,0 điểm) XÂU NHỊ PHÂN
Xét các xâu nhị phân độ dài N được thành lập như sau:
- _ Bắt đầu là xâu gồm N bit 0.
- _ Xâu nhị phân tiếp theo được tạo thành từ xâu nhị phân trước đó bằng cách tìm bit 0 đầu
tiên tính từ phải sang trái đổi thành bit 1 và đổi tắt cả các bit bên phải bịt vừa thay đổi đó
thành bit 0. Ví đụ xâu tiếp theo của xâu 01001 11 là xâu 0101000.
- _ Lặp lại cho đến khi tắt cả N bit đều là bịt 1. .
Ví dụ: Với N= 3, ta có: 000 —> 001 — 010 —> 011 —> 100 —> 101 —> 110 —> H1
Sắp xếp các xâu N bit này theo thứ tự từ điển và đánh số thứ tự từ 0 đến hết. ¬
Thứ tự từ điển được tính như sau:

Với hai xâu nhị phân A và B có độ dài N:

- Xâu A được gọi là nhỏ hơn xâu B nếu như bit khác nhau đầu tiên tính từ trái sang phải
của xâu Á là nhỏ hơn của xâu B.

- Xâu A và xâu B là bằng nhau nếu tắt cả các bit của hai xâu tương ứng là như nhau.