Chữ số cuối là số dư khi chia cho 2
Xét số nguyên n≥0. Với n≥2, số dư n%2 là chữ số cuối của biểu diễn nhị phân; phần đầu là biểu diễn của thương n//2. Vì thương nhỏ hơn n, có thể tính phần đầu bằng đệ quy rồi ghép số dư vào bên phải.
Với n=13, chia lấy thương và dư cho bảng:
| n | n//2 | n%2 |
|---|---|---|
| 13 | 6 | 1 |
| 6 | 3 | 0 |
| 3 | 1 | 1 |
| 1 | 0 | 1 |
Đọc cột dư từ dưới lên được 1101. Cột dư từ trên xuống chưa phải thứ tự các chữ số của kết quả.
Dừng riêng ở số 0 và số 1
```python
def binary(n):
if n == 0:
return '0'
if n == 1:
return '1'
return binary(n // 2) + str(n % 2)
```
Hàm nhận số nguyên không âm và trả xâu không có số 0 thừa ở đầu. Với n=13, các lời gọi đi qua 13,6,3,1; cơ sở trả `'1'`, rồi các bước ghép tạo `'11'`, `'110'`, `'1101'`. Hàm dừng tại n=1, tương ứng chữ số đầu trong bảng. Nếu đầu vào ban đầu là 0 thì trả `'0'`.
str(n%2) đổi số dư thành kí tự để nối với xâu phần đầu. Không cộng trực tiếp một số nguyên vào xâu.
Đầu ra là danh sách thì ghép danh sách
```python
def binary_list(n):
if n == 0:
return [0]
if n == 1:
return [1]
return binary_list(n // 2) + [n % 2]
```
Với 13, kết quả là [1,1,0,1]. Phần `[n%2]` là danh sách một phần tử, nên phép + ghép hai danh sách. Với 0, hàm trả [0], biểu diễn một chữ số 0; không trả [] vì đó là không có chữ số nào.
Bỏ một cơ sở có thể làm đổi dạng kết quả
Nếu bỏ nhánh n==1 nhưng giữ n==0 trả `'0'`, lời gọi với n=2 đi qua 2,1,0 rồi ghép thành `'010'`. Xâu ấy vẫn có giá trị nhị phân bằng 2, nhưng có số 0 thừa ở đầu so với dạng `'10'` đang yêu cầu.
Nếu đổi cơ sở n==0 thành xâu rỗng thì các số dương có thể được ghép đúng dạng, nhưng riêng đầu vào 0 lại nhận xâu rỗng. Hai cơ sở 0 và 1 ở bản đang dùng xử lí thống nhất cả trường hợp 0 lẫn số dương.
Bài luyện
Hàm binary trong bài trả kết quả nào khi n=13?
Các chữ số từ bảng dư được ghép theo thứ tự từ dưới lên.
Đó là đọc cột dư từ trên xuống.
Biểu diễn nhị phân chỉ dùng chữ số 0 và 1.
Đây còn là cách viết thập phân của đầu vào.
Lời giải
Cơ sở n=1 trả '1'. Với n=3 ghép 1 thành '11'; với n=6 ghép 0 thành '110'; với n=13 ghép 1 thành '1101'.
Bài luyện
Vì sao bản binary cần str(n%2), còn binary_list cần [n%2]?
[n%2] chỉ là danh sách một phần tử.
Phép + nối hai xâu hoặc ghép hai danh sách.
Hai hàm đang tạo biểu diễn, không cộng giá trị thập phân.
str tạo xâu; danh sách được tạo bằng ngoặc vuông ở đây.
Lời giải
binary trả xâu nên chữ số mới phải được đổi thành xâu bằng str. binary_list trả danh sách nên chữ số mới được đặt trong danh sách một phần tử; khi đó + ghép đúng hai đối tượng cùng loại.
Bài luyện
Với đầu vào 0, cặp kết quả của binary và binary_list trong bài là gì?
Số 0 không được đổi thành số 1.
Hai hàm trả xâu/danh sách, không trả số nguyên.
Cả hai đều biểu diễn một chữ số 0, với hai kiểu dữ liệu khác nhau.
Đó là không có chữ số nào, khác yêu cầu biểu diễn số 0.
Lời giải
Hai nhánh cơ sở n==0 trả '0' và [0]. Nhờ vậy số 0 vẫn có một chữ số trong biểu diễn, thay vì nhận xâu hoặc danh sách rỗng.
Bài luyện
Bỏ nhánh n==1 của binary nhưng giữ n==0 trả '0'. Với n=2, kết luận nào đúng?
Nhánh n=1 đã bị bỏ nên sẽ ghép thêm từ cơ sở 0.
Các lời gọi đang chờ vẫn ghép số dư.
Thương nguyên giảm tới 0 nên vẫn đạt cơ sở.
Các bước ghép từ cơ sở 0 tạo 0,01,010.
Lời giải
Lời gọi với 2 chuyển sang 1 rồi 0. Cơ sở trả '0'; bước n=1 ghép 1 thành '01', bước n=2 ghép 0 thành '010'. Giá trị vẫn là 2, nhưng chưa đúng dạng không có số 0 thừa ở đầu.
Đang học