Các khóa học
Viết code HTML

Ôn thi HSG Tin học THPT – Bài 12: Các hệ đếm và xử lý số nguyên lớn

1. Mục tiêu

  • Hiểu rõ khái niệm và nguyên tắc của các hệ đếm cơ số, đặc biệt là hệ nhị phân (cơ số 2), hệ thập phân (cơ số 10) và hệ thập lục phân (cơ số 16).
  • Nắm vững và cài đặt được các thuật toán để chuyển đổi một số giữa các hệ đếm khác nhau.
  • Nhận thức và vận dụng được ưu điểm của ngôn ngữ Python trong việc tự động xử lý các phép toán với số nguyên lớn mà không bị tràn số.
  • Áp dụng các kiến thức đã học để giải quyết các bài toán lập trình thi đấu liên quan đến xử lý và chuyển đổi số ở các hệ đếm khác nhau.

2. Bài toán dẫn nhập

Trong khoa học máy tính, mọi dữ liệu, bao gồm cả các con số, đều được lưu trữ và xử lý dưới dạng một chuỗi các bit 0 và 1, tức là ở hệ nhị phân. Tuy nhiên, con người lại quen thuộc với hệ thập phân trong đời sống hàng ngày. Vậy, làm thế nào để máy tính biểu diễn số 2025 dưới dạng nhị phân và ngược lại, làm thế nào để chuyển một chuỗi bit như 11111101001 về lại dạng thập phân mà chúng ta hiểu được?

Mặt khác, trong các bài toán như tính giai thừa của một số lớn (ví dụ 100!) hoặc các bài toán trong lĩnh vực mật mã học, kết quả có thể là một số nguyên có hàng trăm chữ số, vượt xa khả năng lưu trữ của các kiểu dữ liệu số nguyên 32-bit hay 64-bit trong các ngôn ngữ lập trình như C++ hay Pascal. Vấn đề đặt ra là làm thế nào để thực hiện các phép toán trên những số khổng lồ này một cách chính xác.

Bài học này sẽ trình bày nguyên lý của các hệ đếm và các thuật toán chuyển đổi qua lại, đồng thời giới thiệu cách Python giải quyết bài toán số nguyên lớn một cách hiệu quả.

3. Nguyên lý thuật toán

3.1. Ý tưởng cốt lõi

Mọi hệ đếm đều tuân theo một nguyên tắc chung gọi là biểu diễn theo vị trí (positional notation). Một số trong hệ cơ số b được biểu diễn dưới dạng một chuỗi các chữ số d_n d_{n-1} … d_1 d_0. Giá trị của số này được tính bằng công thức tổng quát sau:

Giá trị = d_n × b^n + d_{n-1} × b^{n-1} + ... + d_1 × b^1 + d_0 × b^0

Trong đó:

  • b là cơ số của hệ đếm (ví dụ b = 10 cho hệ thập phân, b = 2 cho hệ nhị phân).
  • d_i là chữ số ở vị trí thứ i (0 ≤ d_i < b).

Dựa trên nguyên lý này, ta có hai thuật toán chính để chuyển đổi:

  • Chuyển đổi từ hệ cơ số b sang hệ thập phân (cơ số 10): Áp dụng trực tiếp công thức khai triển đa thức ở trên.
  • Chuyển đổi từ hệ thập phân (cơ số 10) sang hệ cơ số b: Thực hiện lặp đi lặp lại phép chia lấy phần dư. Lấy số thập phân cần chuyển đổi chia cho cơ số b, ta được một thương và một số dư. Số dư này chính là chữ số cuối cùng trong biểu diễn ở hệ cơ số b. Tiếp tục lấy phần thương chia cho b và lặp lại quá trình cho đến khi thương bằng 0. Chuỗi các số dư thu được, đọc theo thứ tự ngược lại, chính là biểu diễn của số đó trong hệ cơ số b.

3.2. Minh họa các bước thực thi

  • Ví dụ 1: Chuyển số nhị phân 1101 (hệ 2) sang hệ thập phân (hệ 10).
    • Số 1101 trong hệ 2 có 4 chữ số. Áp dụng công thức khai triển:
    • Giá trị = 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰
    • Giá trị = 8 + 4 + 0 + 1 = 13.
    • Vậy, (1101)_2 = (13)_{10}.
  • Ví dụ 2: Chuyển số thập phân 25 (hệ 10) sang hệ nhị phân (hệ 2).
    • Thực hiện phép chia lặp lại cho cơ số 2:
      • 25 chia 2 = 12, dư 1
      • 12 chia 2 = 6, dư 0
      • 6 chia 2 = 3, dư 0
      • 3 chia 2 = 1, dư 1
      • 1 chia 2 = 0, dư 1
    • Đọc các số dư từ dưới lên trên, ta được chuỗi 11001.
    • Vậy, (25)_{10} = (11001)_2.

4. Cài đặt thuật toán

Một trong những ưu điểm lớn của Python là khả năng xử lý số nguyên lớn một cách tự động. Kiểu dữ liệu int trong Python có độ chính xác tùy ý, nghĩa là nó có thể lưu trữ những số nguyên lớn đến mức chỉ bị giới hạn bởi bộ nhớ của máy.

# Ví dụ về khả năng xử lý số nguyên lớn của Python
# Tính 100!
factorial_100 = 1
for i in range(1, 101):
    factorial_100 *= i

# Kết quả là một số rất lớn và Python xử lý một cách dễ dàng
print(f"100! = {factorial_100}")
# Output: 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Dưới đây là cài đặt các thuật toán chuyển đổi hệ đếm.

def to_base_10(num_str: str, base: int) -> int:
    """
    Chuyển đổi một số từ hệ cơ số `base` sang hệ thập phân.
    
    Args:
        num_str: Chuỗi biểu diễn số trong hệ `base`.
        base: Cơ số của hệ đếm ban đầu.
        
    Returns:
        Số nguyên trong hệ thập phân.
    """
    decimal_value = 0
    power = 0
    # Đảo ngược chuỗi để xử lý từ chữ số có trọng số thấp nhất
    for digit in reversed(num_str):
        # Chuyển chữ số (có thể là 0-9 hoặc A-F) thành giá trị số
        if '0' <= digit <= '9':
            val = int(digit)
        else:
            # Dành cho hệ 16 hoặc lớn hơn, A=10, B=11, ...
            val = ord(digit.upper()) - ord('A') + 10
        
        decimal_value += val * (base ** power)
        power += 1
    return decimal_value

def from_base_10(decimal_num: int, base: int) -> str:
    """
    Chuyển đổi một số từ hệ thập phân sang hệ cơ số `base`.
    
    Args:
        decimal_num: Số nguyên trong hệ thập phân.
        base: Cơ số của hệ đếm đích.
        
    Returns:
        Chuỗi biểu diễn số trong hệ `base`.
    """
    if decimal_num == 0:
        return "0"
        
    result_str = ""
    num = decimal_num
    while num > 0:
        remainder = num % base
        # Chuyển số dư thành ký tự tương ứng
        if remainder < 10:
            result_str += str(remainder)
        else:
            # Dành cho hệ 16 hoặc lớn hơn
            result_str += chr(ord('A') + remainder - 10)
        num //= base
        
    # Kết quả là chuỗi các số dư bị đảo ngược, cần đảo lại
    return result_str[::-1]

# Ví dụ sử dụng
print(f"(1101)_2 to base 10: {to_base_10('1101', 2)}")
print(f"(25)_10 to base 2: {from_base_10(25, 2)}")
print(f"(A1F)_16 to base 10: {to_base_10('A1F', 16)}")
print(f"(2591)_10 to base 16: {from_base_10(2591, 16)}")

Lưu ý: Python cũng cung cấp các hàm dựng sẵn tiện lợi như bin(), hex(), và int(string, base) để thực hiện các chuyển đổi này một cách nhanh chóng. Tuy nhiên, việc hiểu và tự cài đặt được thuật toán là rất quan trọng để có thể giải quyết các bài toán biến thể.

5. Trực quan hóa và gỡ lỗi với Thonny

Để hiểu sâu hơn về thuật toán chuyển đổi từ hệ 10 sang hệ b, ta có thể sử dụng trình gỡ lỗi (debugger) của Thonny.

  1. Sao chép hàm from_base_10 vào Thonny.
  2. Thêm một lời gọi hàm, ví dụ print(from_base_10(25, 2)).
  3. Đặt một điểm dừng (breakpoint) tại dòng while num > 0:.
  4. Chạy chương trình ở chế độ gỡ lỗi (Debug current script).
  5. Sử dụng nút “Step over” để đi qua từng vòng lặp. Quan sát trong cửa sổ “Variables” sự thay đổi của các biến num, remainder, và result_str. Ta sẽ thấy rõ num giảm dần như thế nào sau mỗi phép chia, và result_str được xây dựng dần từ các số dư.

Việc này giúp trực quan hóa quá trình thuật toán hoạt động và củng cố sự hiểu biết về logic của nó.

6. Bài tập vận dụng

6.1. Đề bài

Bài toán: Chuyển đổi hệ đếm tổng quát

Viết một chương trình cho phép chuyển đổi một số nguyên không âm N từ hệ cơ số b1 sang hệ cơ số b2.

  • Đầu vào (Input): Gồm một dòng duy nhất chứa 3 thông tin: chuỗi S biểu diễn số N trong hệ b1, và hai số nguyên b1, b2 (2 ≤ b1, b2 ≤ 16). Các chữ số lớn hơn 9 được biểu diễn bằng các ký tự in hoa ‘A’ đến ‘F’.
  • Đầu ra (Output): In ra màn hình chuỗi biểu diễn số N trong hệ cơ số b2.

Ví dụ:

InputOutput
1101 2 1013
25 10 211001
A1F 16 102591
2591 10 16A1F

6.2. Lời giải và phân tích

Phân tích thuật toán:

Để chuyển đổi một số từ hệ cơ số b1 sang b2, ta không cần xây dựng một thuật toán chuyển đổi trực tiếp phức tạp. Thay vào đó, ta có thể sử dụng hệ thập phân làm một hệ trung gian. Quy trình gồm 2 bước:

  1. Chuyển số ban đầu từ hệ b1 sang hệ thập phân (base 10).
  2. Chuyển số thập phân vừa nhận được sang hệ b2.

Phương pháp này tận dụng lại hai hàm đã được xây dựng ở phần 4, giúp cho mã nguồn trở nên rõ ràng và dễ quản lý.

Cài đặt chương trình:

def to_base_10(num_str: str, base: int) -> int:
    """
    Chuyển đổi một số từ hệ cơ số `base` sang hệ thập phân.
    """
    # Mã nguồn hàm này giữ nguyên như đã trình bày ở mục 4
    decimal_value = 0
    power = 0
    for digit in reversed(num_str):
        if '0' <= digit <= '9':
            val = int(digit)
        else:
            val = ord(digit.upper()) - ord('A') + 10
        
        decimal_value += val * (base ** power)
        power += 1
    return decimal_value

def from_base_10(decimal_num: int, base: int) -> str:
    """
    Chuyển đổi một số từ hệ thập phân sang hệ cơ số `base`.
    """
    # Mã nguồn hàm này giữ nguyên như đã trình bày ở mục 4
    if decimal_num == 0:
        return "0"
        
    result_str = ""
    num = decimal_num
    while num > 0:
        remainder = num % base
        if remainder < 10:
            result_str += str(remainder)
        else:
            result_str += chr(ord('A') + remainder - 10)
        num //= base
        
    return result_str[::-1]

def main():
    """
    Hàm chính đọc đầu vào và thực hiện chuyển đổi.
    """
    try:
        # Đọc dữ liệu từ một dòng duy nhất
        line = input().split()
        num_in_b1 = line[0]
        b1 = int(line[1])
        b2 = int(line[2])

        # Bước 1: Chuyển từ hệ b1 sang hệ 10
        decimal_representation = to_base_10(num_in_b1, b1)

        # Bước 2: Chuyển từ hệ 10 sang hệ b2
        result_in_b2 = from_base_10(decimal_representation, b2)

        # In kết quả
        print(result_in_b2)
        
    except (IOError, ValueError) as e:
        # Xử lý các lỗi có thể xảy ra khi đọc hoặc chuyển đổi dữ liệu
        print(f"Đầu vào không hợp lệ: {e}")

# Gọi hàm main để chạy chương trình
if __name__ == "__main__":
    main()

7. Đánh giá thuật toán và Mở rộng

7.1. Phân tích độ phức tạp

  • Hàm to_base_10: Thuật toán duyệt qua từng chữ số của chuỗi đầu vào. Nếu chuỗi có k chữ số, độ phức tạp là O(k).
  • Hàm from_base_10: Thuật toán lặp lại phép chia cho đến khi số ban đầu (giá trị là N) trở về 0. Số lần chia xấp xỉ logb(N). Do đó, độ phức tạp là O(log N).

Vì k cũng tỉ lệ với log N, nên độ phức tạp tổng thể của quá trình chuyển đổi là O(log N), trong đó N là giá trị của số cần chuyển đổi. Đây là một thuật toán rất hiệu quả.

7.2. Các trường hợp đặc biệt và biến thể

  • Cơ số lớn hơn 16: Thuật toán trên có thể dễ dàng mở rộng cho các hệ cơ số lớn hơn 16 bằng cách sử dụng thêm các ký tự khác (ví dụ: chữ cái thường) để biểu diễn các chữ số.
  • Số âm: Để xử lý số âm, ta có thể lưu lại dấu của số, thực hiện chuyển đổi trên giá trị tuyệt đối của nó, sau đó thêm dấu trừ vào kết quả cuối cùng.
  • Số không nguyên (số thực): Việc chuyển đổi phần thập phân của một số là một bài toán phức tạp hơn, đòi hỏi thuật toán nhân với cơ số và lấy phần nguyên, thay vì chia lấy phần dư. Nội dung này nằm ngoài phạm vi bài học cơ bản.

8. Tổng kết

Bài học đã giới thiệu các nguyên lý nền tảng về hệ đếm và cung cấp các thuật toán cốt lõi để chuyển đổi số giữa các hệ cơ số khác nhau. Một điểm nhấn quan trọng là khả năng xử lý số nguyên lớn một cách tự nhiên của Python, đây là một công cụ cực kỳ mạnh mẽ trong lập trình thi đấu, giúp người lập trình tập trung vào thuật toán mà không cần lo lắng về các vấn đề kỹ thuật liên quan đến tràn số.

Việc nắm vững các kỹ thuật này là một kỹ năng thiết yếu để giải quyết một lớp bài toán quan trọng trong các kỳ thi.

admin
admin
Bài viết: 151

Bài viết liên quan

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *