Nhân 17

Lời giải: Nhân 17

Hướng tiếp cận

Nhận xét rằng $17N=16N+N$. Trong hệ nhị phân, nhân với $16=2^4$ tương đương với dịch trái 4 bit (thêm 4 chữ số 0 vào cuối). Do đó, ta chỉ cần cộng hai số nhị phân: $N$ và $N$ dịch trái 4 bit.

Nhận xét quan trọng

1. $17=16+1=2^4+2^0$, nên $17N=N·2^4+N$.
2. Phép cộng hai số nhị phân thực hiện từ phải sang trái, mang nhớ khi tổng $\ge 2$.
3. Kết quả có tối đa $1000+5=1005$ chữ số nhị phân.

Thuật toán

1. Đọc xâu nhị phân $s$ biểu diễn $N$.
2. Tạo hai xâu cần cộng:
   • $a=s$ (căn phải, thêm số 0 dẫn đầu cho đủ độ dài)
   • $b=s+"0000"$ (dịch trái 4 bit)
3. Cộng $a$ và $b$ từng bit từ phải sang trái, xử lý nhớ.
4. Bỏ các số 0 dẫn đầu rồi in kết quả.

Độ phức tạp

• Thời gian: $O(L)$ với $L$ là số chữ số nhị phân của $N$.
• Bộ nhớ: $O(L)$.