Giả sử bạn muốn chuyển đổi một số nguyên thành một chuỗi trong một số cơ sở giữa nhị phân và thập lục phân. Ví dụ: chuyển đổi số nguyên 10 thành biểu diễn chuỗi của nó ở dạng thập phân là "10" hoặc thành biểu diễn chuỗi ở dạng nhị phân là "1010". Mặc dù có nhiều thuật toán để giải quyết vấn đề này, bao gồm cả thuật toán được thảo luận trong phần ngăn xếp, nhưng công thức đệ quy của vấn đề rất tao nhã
Hãy xem một ví dụ cụ thể sử dụng cơ số 10 và số 769. Giả sử chúng ta có một dãy ký tự tương ứng với 10 chữ số đầu tiên, như convString = "0123456789". Thật dễ dàng để chuyển đổi một số nhỏ hơn 10 thành chuỗi tương đương của nó bằng cách tra cứu nó trong chuỗi. Ví dụ: nếu số là 9, thì chuỗi là convString[9] hoặc "9". Nếu chúng ta có thể sắp xếp để chia số 769 thành ba số có một chữ số là 7, 6 và 9, thì việc chuyển đổi nó thành một chuỗi rất đơn giản. Một số nhỏ hơn 10 nghe có vẻ là một trường hợp cơ sở tốt
Biết cơ sở của chúng tôi là gì gợi ý rằng thuật toán tổng thể sẽ bao gồm ba thành phần
Rút gọn số ban đầu thành dãy số có một chữ số
Chuyển đổi số có một chữ số thành chuỗi bằng tra cứu
Nối các chuỗi một chữ số lại với nhau để tạo thành kết quả cuối cùng
Bước tiếp theo là tìm ra cách thay đổi trạng thái và tiến tới trường hợp cơ bản. Vì chúng ta đang làm việc với một số nguyên, hãy xem xét những phép toán nào có thể làm giảm một số. Các ứng cử viên có khả năng nhất là chia và trừ. Mặc dù phép trừ có thể hiệu quả, nhưng không rõ chúng ta nên trừ cái gì. Phép chia số nguyên có dư cho ta hướng đi rõ ràng. Hãy xem điều gì sẽ xảy ra nếu chúng ta chia một số cho cơ số mà chúng ta đang cố chuyển đổi thành
Dùng phép chia số nguyên chia 769 cho 10 ta được 76 dư 9. Điều này mang lại cho chúng tôi hai kết quả tốt. Đầu tiên, phần còn lại là một số nhỏ hơn cơ sở của chúng tôi có thể được chuyển đổi thành một chuỗi ngay lập tức bằng cách tra cứu. Thứ hai, chúng tôi nhận được một số nhỏ hơn số ban đầu của chúng tôi và đưa chúng tôi đến trường hợp cơ sở có một số nhỏ hơn cơ sở của chúng tôi. Bây giờ công việc của chúng ta là chuyển 76 về dạng biểu diễn chuỗi của nó. Một lần nữa, chúng ta sẽ sử dụng phép chia số nguyên cộng với phần dư để có kết quả lần lượt là 7 và 6. Cuối cùng, chúng tôi đã giảm vấn đề thành chuyển đổi 7, điều mà chúng tôi có thể thực hiện dễ dàng vì nó thỏa mãn điều kiện trường hợp cơ sở của \[n < base\], trong đó \[base = 10\]. Chuỗi thao tác chúng ta vừa thực hiện được minh họa trong hình 3. Lưu ý rằng các số chúng ta muốn ghi nhớ nằm trong các hộp còn lại dọc theo bên phải của sơ đồ
Hình 3. Chuyển đổi một số nguyên thành một chuỗi trong cơ sở 10
ActiveCode 1 hiển thị mã Python thực hiện thuật toán được nêu ở trên cho bất kỳ cơ sở nào từ 2 đến 16
Lưu ý rằng trong dòng 3, chúng tôi kiểm tra trường hợp cơ sở trong đó n nhỏ hơn cơ sở mà chúng tôi đang chuyển đổi thành. Khi chúng tôi phát hiện trường hợp cơ sở, chúng tôi ngừng đệ quy và chỉ cần trả về chuỗi từ chuỗi convertString. Ở dòng 6, chúng ta thỏa mãn cả luật thứ hai và luật thứ ba – bằng cách thực hiện lời gọi đệ quy và bằng cách giảm kích thước bài toán – sử dụng phép chia
Hãy theo dõi thuật toán một lần nữa;
hinh 4. Chuyển đổi Số 10 thành Biểu diễn Chuỗi Cơ sở 2 của nó
Hình 4 cho thấy rằng chúng tôi nhận được kết quả mà chúng tôi đang tìm kiếm, nhưng có vẻ như các chữ số bị sai thứ tự. Thuật toán hoạt động chính xác bởi vì chúng tôi thực hiện cuộc gọi đệ quy đầu tiên trên dòng 6, sau đó chúng tôi thêm biểu diễn chuỗi của phần còn lại. Nếu chúng tôi đảo ngược việc trả về tra cứu convertString và trả về cuộc gọi toStr, thì chuỗi kết quả sẽ bị đảo ngược. Nhưng bằng cách trì hoãn thao tác nối cho đến sau khi lệnh gọi đệ quy quay lại, chúng tôi nhận được kết quả theo đúng thứ tự. Điều này sẽ nhắc bạn về cuộc thảo luận của chúng ta về ngăn xếp trong chương trước
Tự kiểm tra
Viết hàm nhận một chuỗi làm tham số và trả về True nếu chuỗi là một palindrome, ngược lại là False. Hãy nhớ rằng một chuỗi là một palindrome nếu nó được đánh vần giống nhau cả về phía trước và phía sau. Ví dụ. radar là một palindrome. đối với điểm thưởng, palindromes cũng có thể là cụm từ, nhưng bạn cần xóa dấu cách và dấu chấm câu trước khi kiểm tra. Ví dụ. thưa bà, tôi là adam là một palindrome. Palindromes vui nhộn khác bao gồm
Hệ thống số thập phân có cơ số 10 vì nó sử dụng 10 chữ số từ 0 đến 9. Trong hệ thập phân, các vị trí kế tiếp bên trái dấu thập phân biểu thị hàng đơn vị, hàng chục, hàng trăm, hàng nghìn, v.v.
Nhị phân sử dụng hai chữ số, 0 và 1. Còn được gọi là hệ thống số cơ số 2 Mỗi vị trí trong một số nhị phân đại diện cho một lũy thừa 0 của cơ số [2]. Vị trí cuối cùng trong một số nhị phân biểu thị lũy thừa x của cơ số [2]
Số bát phân sử dụng tám chữ số, 0,1,2,3,4,5,6,7. Còn được gọi là hệ thống số 8 cơ sở. Mỗi vị trí trong một số bát phân đại diện cho một lũy thừa 0 của cơ số [8]. Vị trí cuối cùng trong một số bát phân biểu thị lũy thừa x của cơ số [8]
Hệ thống số thập lục phân sử dụng 10 chữ số và 6 chữ cái, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F Các chữ cái đại diện cho các số bắt đầu từ 10. một = 10. B = 11, C = 12, D = 13, E = 14, F = 15 Còn được gọi là hệ cơ số 16