Giải mã theo phương pháp của Rôn

Bài toán giải mã theo phương pháp của Rôn

Các phương pháp mã hóa luôn có sức cuốn hút đặc biệt đối với Rôn. Xuất phát từ việc mọi thông tin đều được lưu trữ dưới dạng số, Rôn nghĩ rằng chỉ cần phát triển các phương pháp mã hóa số nguyên. Mới đây Rôn đề xuất một phương pháp mã hóa của riêng mình: mỗi số nguyên x được Rôn mã hóa thành số nguyên y bằng cách cộng vào x các chữ số của nó (ở hệ thập phân). Như vậy, nếu x = 12, ta sẽ có y = 12 + 1 + 2 = 15.

Mã hóa bao giờ cũng đi đôi với việc giải mã. Biết y = 15, ta phải tìm được số ban đầu x = 12.

Yêu cầu: Cho số nguyên dương y. Hãy xác định số ban đầu chưa được mã hóa. Dữ liệu đảm bảo có kết quả giải mã.

Dữ liệu: Vào từ file văn bản DECODE.INP gồm một dòng chứa số nguyên y (1 ≤ y ≤ 10⁹).

Kết quả: Đưa ra file văn bản DECODE.OUT một số nguyên – kết quả giải mã.

Ví dụ:

Thuật toán

Phương pháp mã hóa của Rôn là một phương pháp đơn giản để mã hóa các số nguyên dương thành các số nguyên khác bằng cách cộng vào chính nó tổng các chữ số của nó ở hệ thập phân.

Ví dụ, nếu chúng ta có số nguyên dương x = 12, thì ta có thể mã hóa nó thành số nguyên y bằng cách cộng 12 với tổng các chữ số của nó (tức là 1 + 2 = 3). Vì vậy, y sẽ bằng 15.

Phương pháp này đơn giản và dễ hiểu, và có thể được sử dụng để mã hóa các thông tin đơn giản như các số nguyên dương. Tuy nhiên, nó không được sử dụng trong các ứng dụng mã hóa thực tế, vì nó không đảm bảo tính bảo mật cao và dễ dàng bị giải mã.

Để giải mã số nguyên được mã hóa theo phương pháp của Rôn, ta cần tìm lại được số ban đầu trước khi bị mã hóa. Quá trình này có thể được thực hiện bằng cách lần lượt tách các chữ số của số đã mã hóa và trừ chúng đi từ số đã mã hóa cho đến khi không thể tách được nữa.

Cụ thể, để giải mã số nguyên y đã cho, ta thực hiện các bước sau:

• Khởi tạo biến x = y.
• Lặp lại cho đến khi x không còn chứa chữ số nào:
  • Tính tổng S các chữ số của x ở hệ thập phân.
  • Gán x = x – S.
• Kết quả cần tìm là giá trị của x sau khi kết thúc quá trình lặp.

Ví dụ, để giải mã y = 15, ta thực hiện các bước sau:

• Khởi tạo x = 15.
• Tính S = 1 + 5 = 6. Gán x = 15 – 6 = 9.
• Tính S = 9. Gán x = 9 – 9 = 0.
• Kết quả là x = 0, tức số ban đầu trước khi bị mã hóa là 0.

Độ phức tạp của thuật toán này là O(log y), vì số lần lặp lại tối đa là số chữ số của y.

Cài đặt bài toán với Python

with open('DECODE.INP', 'r') as f_in, open('DECODE.OUT', 'w') as f_out:
    y = int(f_in.readline().strip())  # Đọc số đã mã hóa từ file input

    x = y  # Khởi tạo giá trị ban đầu cho x
    while x > 0:  # Lặp lại cho đến khi không còn chữ số nào
        s = sum(int(digit) for digit in str(x))  # Tính tổng các chữ số của x
        x -= s  # Trừ tổng các chữ số này đi để tìm lại giá trị ban đầu

    f_out.write(str(x))  # Ghi giá trị ban đầu vào file output

Cài đặt bài toán với C++

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main() {
    ifstream infile("DECODE.INP");
    ofstream outfile("DECODE.OUT");
    int y;
    infile >> y; // đọc số đã mã hóa từ file input

    int x = y; // khởi tạo giá trị ban đầu cho x
    while (x > 0) { // lặp lại cho đến khi không còn chữ số nào
        int s = 0;
        string digits = to_string(x); // chuyển x sang chuỗi để tính tổng các chữ số
        for (char digit : digits) {
            s += digit - '0'; // tính tổng các chữ số của x
        }
        x -= s; // trừ tổng các chữ số này đi để tìm lại giá trị ban đầu
    }

    outfile << x; // ghi giá trị ban đầu vào file output
    return 0;
}