Hướng dẫn giải của Nhân 17

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Nhân 17

Hướng tiếp cận

Nhận xét rằng $17 N = 16 N + 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

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

Thuật toán

Đọc xâu nhị phân $s$ biểu diễn $N$ .
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)
Cộng $a$ và $b$ từng bit từ phải sang trái, xử lý nhớ.
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)$ .

Bình luận

Không có bình luận tại thời điểm này.