Giới thiệu
Xâu nhị phân là chuỗi các kí tự chỉ bao gồm hai số 0 và 1. Dựa trên luật cộng hai số 0 và 1 trong phép toán nhị phân, người ta có thể xác định được chuỗi nhị phân kế tiếp.
Mô tả về giải thuật
Dãy đầu tiên sẽ là 0 0 ... 0.
Dãy cuối cùng là 1 1 ... 1.
Giả sử b1 b2 ... bn là dãy đang có.
Nếu dãy này gồm toàn số 1 thì kết thúc thuật toán.
Trái lại, dãy kế tiếp nhận được bằng cách cộng thêm 1 (theo modun 2, có nhớ) vào dãy hiện tại.
Từ đó ta có qui tắc sinh dãy kế tiếp như sau:
Tìm i đầu tiên (theo thứ tự i=n, n-1, ..., 1) thoả mãn bi = 0.
Gán lại bi = 1 và bj = 0 với tất cả j > i. Dãy mới thu được sẽ là dãy cần tìm.
Ví dụ minh họa
Xét dãy nhị phân độ dài 10: b = 1101011111.
Xét với chỉ số i bắt đầu là 1, ta có i = 5.
Do đó, đặt b5 = 1, và bi = 0, j = 6, 7, 8, 9, 10, ta thu được xâu nhị phân kế tiếp là 1101100000.
Bạn có thể đánh giá bài học này ở đây