Một dãy các con số $0$ và $1$ có độ dài $32$ được kí hiệu là $1$ xâu. Ta kí hiệu các xâu $A$, $B$, $C$ như sau
$A=(a_1;a_2;...;a_n)$
$B=(b_1;b_2;...;b_n)$
$C=(c_1;c_2;...;c_n)$
với $a_i,b_i,c_i=0$ hay $1$; $i=1,2,...,32$
Giá trị của một xâu là số các con số $1$ có trong xâu đó.
Một máy tính có thể xử lí các xâu bằng 2 phép biến đổi sau :
- Phép dịch chuyển các phần tử của $A$ đi $k$ cij trí, $1\leq k\leq 32$ theo quy tắc.
$(a_1,a_2,...,a_{32})\Rightarrow (a_k,a_{k+1},...,a_{31},a_{32},a_1,a_2,...,a_{k-1})$
- Phép so sánh hai xâu $A$ và $B$ để được một xâu mới $C$ theo quy tắc $A$&$B$ $\Rightarrow C$
với $c_i=1$ nếu $(a_i=1;b_i=0)$ hay $(a_i=b_i=1)$
và $c_i=0$ nếu $(a_i=0;b_i=1)$ hay $(a_i=b_i=0)$
Cho xâu $A$ có giá trị bằng $16$ và $B$ là một xâu tuỳ ý. Chứng minh rằng bằng cách dịch chuyển $A$ đi $k$ vị trí thích hợp và so sánh kết quả với $B$ ta sẽ được xâu $C$ có giá trị không nhỏ hơn $16$
p/s : tiêu đề em gõ sai rồi mong mod nào đọc rồi sửa giùm
Bài viết đã được chỉnh sửa nội dung bởi namsub: 16-04-2013 - 17:27
